remarkRemark hypothesisHypothesis claimClaim Tensor Expander Chernoff
BoundsShih Yu Chang

# Tensor Expander Chernoff Bounds

Shih Yu Chang Department of Applied Data Science, San Jose State University,
San Jose, CA 95192, USA<EMAIL_ADDRESS>
###### Abstract

The Chernoff bound is an important inequality relation in probability theory.
The original version of the Chernoff bound is to give an exponential
decreasing bound on the tail distribution of sums of independent random
variables. Recent years, several works have been done by extending the
original version of the Chernoff bound to high-dimensional random objects,
e.g., random matrices, or/and to consider the relaxation that there is no
requirement of independent assumptions among random objects. In this work, we
generalize the matrix expander Chernoff bound studied by Garg et al. [8] to
_tensor expander Chernoff bounds_. Our main tool is to develop new tensor norm
inequalities based on log-majorization techniques. These new tensor norm
inequalities are used to bound the expectation of Ky Fan norm of the random
tensor exponential function, then _tensor expander Chernoff bounds_ can be
established. Compared with the matrix expander Chernoff bound, the _tensor
expander Chernoff bounds_ proved at this work contributes following aspects:
(1) the random objects dimensions are increased from matrices (two-dimensional
data array) to tensors (multidimensional data array); (2) this bound
generalizes the identity map of the random objects summation to any polynomial
function of the random objects summation; (3) Ky Fan norm, instead only the
maximum or the minimum eigenvalues, for the function of the random objects
summation is considered; (4) we remove the restriction about the summation of
all mapped random objects is zero, which is required in the matrix expander
Chernoff bound derivation.

###### keywords:

Random Tensors, Tail Bound, Ky Fan Norm, Log-Majorization, Graph.

15B52, 60B20, 11M50, 15A69

##  1 Introduction

In probability theory, the Chernoff bound provides the exponential decreasing
bound on tail distribution of sums of independent random variables. This bound
has various applications in science and engineering. For example, the Chernoff
bound is utilized in mathematical learning theory to prove that a learning
algorithm is probably approximately correct [15]. On the engineering side, the
Chernoff bound is also used to obtain tight bounds for packet routing problems
which reduce wireless communication congestion while routing packets in sparse
networks [14].

It is a tighter bound than the known first- or second-moment-based tail bounds
such as Markov’s inequality or Chebyshev’s inequality, which only yield power-
law bounds on tail distribution. Nevertheless, neither Markov’s inequality nor
Chebyshev’s inequality requires that the variates are independent, which is
necessary by the Chernoff bound [5]. Given $n$ independent and identically
distributed (i.i.d.) random variables $X_{1},X_{2},\cdots,X_{n}$ taking values
in $\\{0,1\\}$ with $\mathbb{E}[X_{i}]=q$ and $\epsilon>0$, Chernoff bound for
the version of $n$ i.i.d. random variables is

(1) $\displaystyle\mathrm{Pr}\left(\frac{1}{n}\sum\limits_{i=1}^{n}X_{i}\geq
q+\epsilon\right)\leq\exp(-n\mathbb{D}(q+\epsilon\parallel q)),$

where $\mathbb{D}(x\parallel y)\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}x\ln\frac{x}{y}+(1-x)\ln\frac{1-x}{1-y}$ is the Kullback–Leibler
divergence between Bernoulli distributed random variables with parameters $x$
and $y$ respectively.

There are various directions to generalize the Chernoff bound from Eq. (1),
one major direction is to increase the dimension of random objects from random
variables to random matrices. The works of Rudelson [21], Ahlswede-Winter [1]
and Tropp [23] demonstrated that a similar concentration bound is also valid
for matrix-valued random variables. If
$\mathbf{X}_{1},\mathbf{X}_{2},\cdots,\mathbf{X}_{n}$ are independent $m\times
m$ Hermitian complex random matrices with $\left\|\mathbf{X}_{i}\right\|\leq
1$ for $1\leq i\leq n$, where $\left\|\cdot\right\|$ is the spectral norm, we
have following Chernoff bound for the version of $n$ i.i.d. random matrices:

(2)
$\displaystyle\mathrm{Pr}\left(\left\|\frac{1}{n}\sum\limits_{i=1}^{n}\mathbf{X}_{i}-\mathbb{E}[\mathbf{X}]\right\|\geq\vartheta\right)\leq
m\exp(-\Omega n\vartheta^{2}),$

where $\Omega$ is a constant related to the matrix norm. This is also called
“Matrix Chernoff Bound” and is applied to many fields, e.g., spectral graph
theory, numerical linear algebra, machine learning and information theory
[24]. Recently, Shih Yu generalized matrix bounds to various tensors bounds,
e.g., Chernoff, Bennett, and Bernstein inequalities associated with tensors in
[3].

Another direction to extend from the basic Chernoff bound is to consider non-
independent assumptions for random variables. By Gillman [9] and its
refinement works [6, 20], they changed the independence assumption to Markov
dependence and we summarize their works as follows. We are given
$\mathfrak{G}$ as a regular $\lambda$-expander graph with vertex set
$\mathfrak{V}$, and $g:\mathfrak{V}\rightarrow\mathbb{C}$ as a bounded
function. Suppose $v_{1},v_{2}\cdots,v_{\kappa}$ is a stationary random walk
of length $\kappa$ on $\mathfrak{G}$, it is shown that:

(3)
$\displaystyle\mathrm{Pr}\left(\left\|\frac{1}{\kappa}\sum\limits_{j=1}^{\kappa}g(v_{i})-\mathbb{E}[g]\right\|\geq\vartheta\right)\leq
2\exp(-\Omega(1-\lambda)\kappa\vartheta^{2}).$

The value of $\lambda$ is also the second largest eigenvalue of the transition
matrix of the underlying graph $\mathfrak{G}$. The bound given in Eq. (3) is
named as “Expander Chernoff Bound”. It is natural to generalize Eq. (3) to
“Matrix Expander Chernoff Bound”. Wigderson and Xiao in [25] began first
attempt to obtain partial results of “Matrix Expander Chernoff Bound” and the
complete solution is given later by Garg et al. [8]. Their results can be
summarized by the following theorem.

######  Theorem 1.1.

Let $\mathfrak{G}=(\mathfrak{V},\mathfrak{E})$ be a regular graph whose
transition matrix has second largest eigenvalue as $\lambda$, and let
$g:\mathfrak{V}\rightarrow\mathbb{C}^{m\times m}$ be a function satisfy
following:

  1. 1.

For each $v\mathfrak{V}$, $g(v)$ is a Hermitian matrix with
$\left\|g(v)\right\|\leq 1$;

  2. 2.

$\sum\limits_{v\in\mathfrak{V}}g(v)=\mathbf{0}$.

Then, for a stationary random walk $v_{1},\cdots,v_{\kappa}$ with
$\epsilon\in(0,1)$, we have

$\displaystyle\mathrm{P}\left(\lambda_{g,\max}\left(\frac{1}{\kappa}\sum\limits_{j=1}^{\kappa}g(v_{j})\right)\geq\epsilon\right)$
$\displaystyle\leq$ $\displaystyle
m\exp(-\Omega(1-\lambda)\kappa\epsilon^{2}),$ (4)
$\displaystyle\mathrm{P}\left(\lambda_{g,\min}\left(\frac{1}{\kappa}\sum\limits_{j=1}^{\kappa}g(v_{j})\right)\leq-\epsilon\right)$
$\displaystyle\leq$ $\displaystyle
m\exp(-\Omega(1-\lambda)\kappa\epsilon^{2}),$

where $\lambda_{g,\max},(\lambda_{g,\min})$ is the largest (smallest)
eigenvalue of the summation of $\kappa$ matrices obtained by the mapping $g$.

In this work, we generalize matrix expander Chernoff bound to _tensor expander
Chernoff bounds_ by allowing more general norm for tensors, Ky Fan norm and
general convex function, instead identity function, of the tensors summand. We
first extend the setting of Hermitian matrices to Hermitian tensors in [12] by
utilizing majorization techniques to prove the following theorem 1.2, which
will play a crucial role in our proof of _tensor expander Chernoff bounds_.

######  Theorem 1.2.

Let $\mathcal{C}_{i}\in\mathbb{C}^{I_{1}\times\cdots\times I_{N}\times
I_{1}\times\cdots\times I_{N}}$ be positive Hermitian tensors for $1\leq i\leq
n$ with Hermitian rank $r$, $\left\|\cdot\right\|_{(k)}$ be a Ky Fan $k$-norm
with corresponding gauge function $\rho$. For any continuous function
$f:(0,\infty)\rightarrow[0,\infty)$ such that $x\rightarrow\log f(e^{x})$ is
convex on $\mathbb{R}$, we have

(5)
$\displaystyle\left\|f\left(\exp\left(\sum\limits_{i=1}^{n}\log\mathcal{C}_{i}\right)\right)\right\|_{(k)}$
$\displaystyle\leq$
$\displaystyle\exp\int_{-\infty}^{\infty}\log\left\|f\left(\left|\prod\limits_{i=1}^{n}\mathcal{C}_{i}^{1+\iota
t}\right|\right)\right\|_{(k)}\beta_{0}(t)dt,$

where $\iota$ is $\sqrt{-1}$ and $\beta_{0}(t)=\frac{\pi}{2(\cosh(\pi t)+1)}$.
For any continuous function $g(0,\infty)\rightarrow[0,\infty)$ such that
$x\rightarrow g(e^{x})$ is convex on $\mathbb{R}$, we have

(6)
$\displaystyle\left\|g\left(\exp\left(\sum\limits_{i=1}^{n}\log\mathcal{C}_{i}\right)\right)\right\|_{(k)}$
$\displaystyle\leq$
$\displaystyle\int_{-\infty}^{\infty}\left\|g\left(\left|\prod\limits_{i=1}^{n}\mathcal{C}_{i}^{1+\iota
t}\right|\right)\right\|_{(k)}\beta_{0}(t)dt.$

The main contribution of this work is the following _tensor expander Chernoff
bounds_.

######  Theorem 1.3.

Let $\mathfrak{G}=(\mathfrak{V},\mathfrak{E})$ be a regular undirected graph
whose transition matrix has second eigenvalue $\lambda$, and let
$g:\mathfrak{V}\rightarrow\in\mathbb{C}^{I_{1}\times\cdots\times I_{M}\times
I_{1}\times\cdots\times I_{M}}$ be a function. We assume following:

  1. 1.

For each $v\in\mathfrak{V}$, $g(v)$ is a Hermitian tensor;

  2. 2.

$\left\|g(v)\right\|\leq r$;

  3. 3.

A nonnegative coefficients polynomial raised by the power $s\geq 1$ as
$f:x\rightarrow(a_{0}+a_{1}x+a_{2}x^{2}+\cdots+a_{n}x^{n})^{s}$ satisfying
$f\left(\exp\left(t\sum\limits_{j=1}^{\kappa}g(v_{j})\right)\right)\succeq\exp\left(tf\left(\sum\limits_{j=1}^{\kappa}g(v_{j})\right)\right)$
almost surely;

  4. 4.

For $\tau\in[\infty,\infty]$, we have constants $C$ and $\sigma$ such that
$\beta_{0}(\tau)\leq\frac{C\exp(\frac{-\tau^{2}}{2\sigma^{2}})}{\sigma\sqrt{2\pi}}$.

Then, we have

$\displaystyle\mathrm{Pr}\left(\left\|f\left(\sum\limits_{j=1}^{\kappa}g(v_{j})\right)\right\|_{(k)}\geq\vartheta\right)\leq\min\limits_{t>0}\left[(n+1)^{(s-1)}e^{-\vartheta
t}\left(a_{0}k+C\left(k+\sqrt{\frac{\mathbb{I}_{1}^{M}-k}{k}}\right)\cdot\right.\right.~{}~{}~{}~{}~{}$
(7)
$\displaystyle\left.\left.\sum\limits_{l=1}^{n}a_{l}\exp(8\kappa\overline{\lambda}+2(\kappa+8\overline{\lambda})lsrt+2(\sigma(\kappa+8\overline{\lambda})lsr)^{2}t^{2})\right)\right],$

where $\mathbb{I}_{1}^{M}$ is a positive integer obtained from
$\prod\limits_{k=1}^{M}I_{k}$.

By comparing matrix expander Chernoff bound, the _tensor expander Chernoff
bounds_ derived at this paper makes following relaxation: (1) the random
objects dimensions are increased from matrices (2D data array) to tensors
(multidimensional data array); (2)this bound generalizes the identity map to
the power of polynomial functions as shown by the third assumption of the
function $f$ at Theorem 1.3; (3) Ky Fan norm of
$f\left(\sum\limits_{j=1}^{\kappa}g(v_{j})\right)$ is considered instead only
the maximum or the minimum eigenvalues of
$f\left(\sum\limits_{j=1}^{\kappa}g(v_{j})\right)$ being evaluated; (4) there
are no restriction for $\sum\limits_{v\in\mathfrak{V}}g(v)$, but this
summation is required to be a zero matrix in the matrix expander Chernoff
bound derivation 111We have another work [4] apply same majorization
techniques to build bounds for tail bounds for the summation of random tensors
under indepedent assumptions..

The paper is organized as follows. Preliminaries of tensors and basic
majorization notations are given in Section 2. In Section 3, multivariate
tensor norm inequalities are established and these inequalities will become
our main ingredients to prove _tensor expander Chernoff bounds_. Main theorem
1.3 is discussed and proved in Section 4. Finally, the conclusio and potential
future works are given in Section Section 5.

##  2 Fundamentals of Tensors and Majorization

The purpose of this section is to provide fundamental facts about tensors and
introduce notions about majorization.

###  2.1 Tensors Preliminaries

Throughout this work, scalars are represented by lower-case letters (e.g.,
$d$, $e$, $f$, $\ldots$), vectors by boldfaced lower-case letters (e.g.,
$\mathbf{d}$, $\mathbf{e}$, $\mathbf{f}$, $\ldots$), matrices by boldfaced
capitalized letters (e.g., $\mathbf{D}$, $\mathbf{E}$, $\mathbf{F}$,
$\ldots$), and tensors by calligraphic letters (e.g., $\mathcal{D}$,
$\mathcal{E}$, $\mathcal{F}$, $\ldots$), respectively. Tensors are multiarrays
of values which are higher-dimensional generalizations from vectors and
matrices. Given a positive integer $N$, let
$[N]\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}\\{1,2,\cdots,N\\}$. An
_order- $N$ tensor_ (or _$N$ -th order tensor_) denoted by
$\mathcal{X}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}(x_{i_{1},i_{2},\cdots,i_{N}})$, where $1\leq
i_{j}=1,2,\ldots,I_{j}$ for $j\in[N]$, is a multidimensional array containing
$\prod_{n=1}^{N}I_{n}$ entries. Let $\mathbb{C}^{I_{1}\times\cdots\times
I_{N}}$ and $\mathbb{R}^{I_{1}\times\cdots\times I_{N}}$ be the sets of the
order-$N$ $I_{1}\times\cdots\times I_{N}$ tensors over the complex field
$\mathbb{C}$ and the real field $\mathbb{R}$, respectively. For example,
$\mathcal{X}\in\mathbb{C}^{I_{1}\times\cdots\times I_{N}}$ is an order-$N$
multiarray, where the first, second, …, and $N$-th dimensions have $I_{1}$,
$I_{2}$, $\ldots$, and $I_{N}$ entries, respectively. Thus, each entry of
$\mathcal{X}$ can be represented by $x_{i_{1},\cdots,i_{N}}$. For example,
when $N=3$, $\mathcal{X}\in\mathbb{C}^{I_{1}\times I_{2}\times I_{3}}$ is a
third-order tensor containing entries $x_{i_{1},i_{2},i_{3}}$’s.

Without loss of generality, one can partition the dimensions of a tensor into
two groups, say $M$ and $N$ dimensions, separately. Thus, for two
order-($M$+$N$) tensors: $\mathcal{X}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}(x_{i_{1},\cdots,i_{M},j_{1},\cdots,j_{N}})\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times J_{1}\times\cdots\times J_{N}}$ and
$\mathcal{Y}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}(y_{i_{1},\cdots,i_{M},j_{1},\cdots,j_{N}})\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times J_{1}\times\cdots\times J_{N}}$, according to [16], the _tensor
addition_ $\mathcal{X}+\mathcal{Y}\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times J_{1}\times\cdots\times J_{N}}$ is given by

(8)
$\displaystyle(\mathcal{X}+\mathcal{Y})_{i_{1},\cdots,i_{M},j_{1}\times\cdots\times
j_{N}}$ $\displaystyle\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}$
$\displaystyle x_{i_{1},\cdots,i_{M},j_{1}\times\cdots\times j_{N}}$
$\displaystyle+y_{i_{1},\cdots,i_{M},j_{1}\times\cdots\times j_{N}}.$

On the other hand, for tensors $\mathcal{X}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}(x_{i_{1},\cdots,i_{M},j_{1},\cdots,j_{N}})\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times J_{1}\times\cdots\times J_{N}}$ and
$\mathcal{Y}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}(y_{j_{1},\cdots,j_{N},k_{1},\cdots,k_{L}})\in\mathbb{C}^{J_{1}\times\cdots\times
J_{N}\times K_{1}\times\cdots\times K_{L}}$, according to [16], the _Einstein
product_ (or simply referred to as _tensor product_ in this work)
$\mathcal{X}\star_{N}\mathcal{Y}\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times K_{1}\times\cdots\times K_{L}}$ is given by

(9)
$\displaystyle(\mathcal{X}\star_{N}\mathcal{Y})_{i_{1},\cdots,i_{M},k_{1}\times\cdots\times
k_{L}}\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}$
$\displaystyle\sum\limits_{j_{1},\cdots,j_{N}}x_{i_{1},\cdots,i_{M},j_{1},\cdots,j_{N}}y_{j_{1},\cdots,j_{N},k_{1},\cdots,k_{L}}.$

Note that we will often abbreviate a tensor product
$\mathcal{X}\star_{N}\mathcal{Y}$ to “$\mathcal{X}\hskip
1.42271pt\mathcal{Y}$” for notational simplicity in the rest of the paper.
This tensor product will be reduced to the standard matrix multiplication as
$L$ $=$ $M$ $=$ $N$ $=$ $1$. Other simplified situations can also be extended
as tensor–vector product ($M>1$, $N=1$, and $L=0$) and tensor–matrix product
($M>1$ and $N=L=1$). In analogy to matrix analysis, we define some basic
tensors and elementary tensor operations as follows.

######  Definition 2.1.

A tensor whose entries are all zero is called a _zero tensor_ , denoted by
$\mathcal{O}$.

######  Definition 2.2.

An _identity tensor_ $\mathcal{I}\in\mathbb{C}^{I_{1}\times\cdots\times
I_{N}\times J_{1}\times\cdots\times J_{N}}$ is defined by

(10) $\displaystyle(\mathcal{I})_{i_{1}\times\cdots\times i_{N}\times
j_{1}\times\cdots\times j_{N}}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\prod_{k=1}^{N}\delta_{i_{k},j_{k}},$

where $\delta_{i_{k},j_{k}}\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}1$ if
$i_{k}=j_{k}$; otherwise
$\delta_{i_{k},j_{k}}\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}0$.

In order to define _Hermitian_ tensor, the _conjugate transpose operation_ (or
_Hermitian adjoint_) of a tensor is specified as follows.

######  Definition 2.3.

Given a tensor $\mathcal{X}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}(x_{i_{1},\cdots,i_{M},j_{1},\cdots,j_{N}})\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times J_{1}\times\cdots\times J_{N}}$, its conjugate transpose, denoted
by $\mathcal{X}^{H}$, is defined by

(11)
$\displaystyle(\mathcal{X}^{H})_{j_{1},\cdots,j_{N},i_{1},\cdots,i_{M}}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\overline{x_{i_{1},\cdots,i_{M},j_{1},\cdots,j_{N}}},$

where the overline notion indicates the complex conjugate of the complex
number $x_{i_{1},\cdots,i_{M},j_{1},\cdots,j_{N}}$. If a tensor $\mathcal{X}$
satisfies $\mathcal{X}^{H}=\mathcal{X}$, then $\mathcal{X}$ is a _Hermitian
tensor_.

######  Definition 2.4.

Given a tensor $\mathcal{U}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}(u_{i_{1},\cdots,i_{M},i_{1},\cdots,i_{M}})\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times I_{1}\times\cdots\times I_{M}}$, if

(12)
$\displaystyle\mathcal{U}^{H}\star_{M}\mathcal{U}=\mathcal{U}\star_{M}\mathcal{U}^{H}=\mathcal{I}\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times I_{1}\times\cdots\times I_{M}},$

then $\mathcal{U}$ is a _unitary tensor_. In this work, the symbol
$\mathcal{U}$ is reserved for a unitary tensor.

Following definition is provided to define the inverse of a given tensor.

######  Definition 2.5.

Given a _square tensor_ $\mathcal{X}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}(x_{i_{1},\cdots,i_{M},j_{1},\cdots,j_{M}})\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times I_{1}\times\cdots\times I_{M}}$, if there exists
$\mathcal{X}\in\mathbb{C}^{I_{1}\times\cdots\times I_{M}\times
I_{1}\times\cdots\times I_{M}}$ such that

(13)
$\displaystyle\mathcal{X}\star_{M}\mathcal{X}=\mathcal{X}\star_{M}\mathcal{X}=\mathcal{I},$

then $\mathcal{X}$ is the _inverse_ of $\mathcal{X}$. We usually write
$\mathcal{X}\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}\mathcal{X}^{-1}$
thereby.

We also list other crucial tensor operations here. The _trace_ of a square
tensor is equivalent to the summation of all diagonal entries such that

(14) $\displaystyle\mathrm{Tr}(\mathcal{X})\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\sum\limits_{1\leq i_{j}\leq I_{j},\hskip
1.42271ptj\in[M]}\mathcal{X}_{i_{1},\cdots,i_{M},i_{1},\cdots,i_{M}}.$

The _inner product_ of two tensors $\mathcal{X}$,
$\mathcal{Y}\in\mathbb{C}^{I_{1}\times\cdots\times I_{M}\times
J_{1}\times\cdots\times J_{N}}$ is given by

(15)
$\displaystyle\langle\mathcal{X},\mathcal{Y}\rangle\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\mathrm{Tr}\left(\mathcal{X}^{H}\star_{M}\mathcal{Y}\right).$

According to Eq. (15), the _Frobenius norm_ of a tensor $\mathcal{X}$ is
defined by

(16)
$\displaystyle\left\|\mathcal{X}\right\|\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\sqrt{\langle\mathcal{X},\mathcal{X}\rangle}.$

From Theorem 5.2 in [19], every Hermitian tensor
$\mathcal{H}\in\mathbb{C}^{I_{1}\times\cdots\times I_{N}\times
I_{1}\times\cdots\times I_{N}}$ has following decomposition

(17) $\displaystyle\mathcal{H}$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{r}\lambda_{i}\mathcal{U}_{i}\otimes\mathcal{U}^{H}_{i},\mbox{
~{}with~{}~{}$\langle\mathcal{U}_{i},\mathcal{U}_{i}\rangle=1$ and
$\langle\mathcal{U}_{i},\mathcal{U}_{j}\rangle=0$ for $i\neq j$,}$

where $\lambda_{i}\in\mathbb{R}$ and $\otimes$ denotes for Kronecker product.
The values $\lambda_{i}$ are named as _Hermitian eigevalues_ , and the minimum
integer of $r$ to decompose a Hermitian tensor as in Eq. (17) is called
_Hermitian tensor rank_. A _postive Hermitian tensor_ is a Hermitian tensor
with all _Hermitian eigevalues_ are positive. A _nonnegative Hermitian tensor_
is a Hermitian tensor with all _Hermitian eigevalues_ are nonnegative. The
_Hermitian determinant_ , denoted as $\det\nolimits_{H}(\mathcal{A})$, is
defined as the product of $\lambda_{i}$ of the tensor $\mathcal{A}$.

###  2.2 Unitarily Invariant Tensor Norms

Let us represent the Hermitian eigenvalues of a Hermitian tensor
$\mathcal{H}\in\mathbb{C}^{I_{1}\times\cdots\times I_{N}\times
I_{1}\times\cdots\times I_{N}}$ in decreasing order by the vector
$\vec{\lambda}(\mathcal{H})=(\lambda_{1}(\mathcal{H}),\cdots,\lambda_{r}(\mathcal{H}))$,
where $r$ is the Hermitian rank of the tensor $\mathcal{H}$. We use
$\mathbb{R}_{\geq 0}(\mathbb{R}_{>0})$ to represent a set of nonnegative
(positive) real numbers. Let $\left\|\cdot\right\|_{\rho}$ be a unitarily
invariant tensor norm, i.e.,
$\left\|\mathcal{H}\star_{N}\mathcal{U}\right\|_{\rho}=\left\|\mathcal{U}\star_{N}\mathcal{H}\right\|_{\rho}=\left\|\mathcal{H}\right\|_{\rho}$,
where $\mathcal{U}$ is any unitary tensor. Let $\rho:\mathbb{R}_{\geq
0}^{r}\rightarrow\mathbb{R}_{\geq 0}$ be the corresponding gauge function that
satisfies H$\ddot{o}$lder’s inequality so that

(18)
$\displaystyle\left\|\mathcal{H}\right\|_{\rho}=\left\||\mathcal{H}|\right\|_{\rho}=\rho(\vec{\lambda}(|\mathcal{H}|)),$

where $|\mathcal{H}|\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\sqrt{\mathcal{H}^{H}\star_{N}\mathcal{H}}$. The bijective
correspondence between symmetric gauge functions on $\mathbb{R}_{\geq 0}^{r}$
and unitarily invariant norms is due to von Neumann [7].

Several popular norms can be treated as special cases of unitarily invariant
tensor norm. The first one is Ky Fan like $k$-norm [7] for tensors. For
$k\in\\{1,2,\cdots,r\\}$, the Ky Fan $k$-norm [7] for tensors
$\mathcal{H}\mathbb{C}^{I_{1}\times\cdots\times I_{N}\times
I_{1}\times\cdots\times I_{N}}$, denoted as
$\left\|\mathcal{H}\right\|_{(k)}$, is defined as:

(19)
$\displaystyle\left\|\mathcal{H}\right\|_{(k)}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\sum\limits_{i=1}^{k}\lambda_{i}(|\mathcal{H}|).$

If $k=1$, the Ky Fan $k$-norm for tensors is the tensor operator norm (or
spectral norm), denoted as $\left\|\mathcal{H}\right\|$. The second one is
Schatten $p$-norm for tensors, denoted as $\left\|\mathcal{H}\right\|_{p}$, is
defined as:

(20)
$\displaystyle\left\|\mathcal{H}\right\|_{p}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}(\mathrm{Tr}|\mathcal{H}|^{p})^{\frac{1}{p}},$

where $p\geq 1$. If $p=1$, it is the trace norm. The third one is $k$-trace
norm, denoted as $\mathrm{Tr}_{k}[\mathcal{H}]$, defined by [13]. It is

(21)
$\displaystyle\mathrm{Tr}_{k}[\mathcal{H}]\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\sum\limits_{1\leq i_{1}<i_{2}<\cdots i_{k}\leq
r}\lambda_{i_{1}}\lambda_{i_{1}}\cdots\lambda_{i_{k}}$

where $1\leq k\leq r$. If $k=1$, $\mathrm{Tr}_{k}[\mathcal{H}]$ is reduced as
trace norm. In our later derivation for multivariate tensor norm inequalities
in Section 3 and tensor expander bounds in Section 4, we will focus on Ky Fan
$k$-norm.

Following inequality is the extension of Hölder inequality to gauge function
$\rho$ which will be used by later majorization proof arguments.

######  Lemma 2.6.

For $n$ nonnegative real vectors with the dimension $r$, i.e.,
$\mathbf{b}_{i}=(b_{i_{1}},\cdots,b_{i_{r}})\in\mathbb{R}_{\geq 0}^{r}$, and
$\alpha>0$ with $\sum\limits_{i=1}^{n}\alpha_{i}=1$, we have

(22)
$\displaystyle\rho\left(\prod\limits_{i=1}^{n}b_{i_{1}}^{\alpha_{i}},\prod\limits_{i=1}^{n}b_{i_{2}}^{\alpha_{i}},\cdots,\prod\limits_{i=1}^{n}b_{i_{r}}^{\alpha_{i}}\right)\leq\prod\limits_{i=1}^{n}\rho^{\alpha_{i}}(\mathbf{b}_{i})$

Proof: This proof is based on mathematical induction. The base case for $n=2$
has been shown by Theorem IV.1.6 from [2].

We assume that Eq. (22) is true for $n=m$, where $m>2$. Let $\odot$ be the
component-wise product (Hadamard product) between two vectors. Then, we have

(23)
$\displaystyle\rho\left(\prod\limits_{i=1}^{m+1}b_{i_{1}}^{\alpha_{i}},\prod\limits_{i=1}^{m+1}b_{i_{2}}^{\alpha_{i}},\cdots,\prod\limits_{i=1}^{m+1}b_{i_{r}}^{\alpha_{i}}\right)=\rho\left(\odot_{i=1}^{m+1}\mathbf{b}_{i}^{\alpha_{i}}\right),$

where $\odot_{i=1}^{m+1}\mathbf{b}_{i}^{\alpha_{i}}$ is defined as
$\left(\prod\limits_{i=1}^{m+1}b_{i_{1}}^{\alpha_{i}},\prod\limits_{i=1}^{m+1}b_{i_{2}}^{\alpha_{i}},\cdots,\prod\limits_{i=1}^{m+1}b_{i_{r}}^{\alpha_{i}}\right)$
with $\mathbf{b}_{i}^{\alpha_{i}}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}(b_{i_{1}}^{\alpha_{i}},\cdots,b_{i_{r}}^{\alpha_{i}})$. Under such
notations, Eq. (23) can be bounded as

(24)
$\displaystyle\rho\left(\odot_{i=1}^{m+1}\mathbf{b}_{i}^{\alpha_{i}}\right)$
$\displaystyle=$
$\displaystyle\rho\left(\left(\odot_{i=1}^{m}\mathbf{b}_{i}^{\frac{\alpha_{i}}{\sum\limits_{j=1}^{m}\alpha_{j}}}\right)^{\sum\limits_{j=1}^{m}\alpha_{j}}\odot\mathbf{b}_{m+1}^{\alpha_{m+1}}\right)$
$\displaystyle\leq$
$\displaystyle\left[\rho^{\sum\limits_{j=1}^{m}\alpha_{j}}\left(\odot_{i=1}^{m}\mathbf{b}_{i}^{\frac{\alpha_{i}}{\sum\limits_{j=1}^{m}\alpha_{j}}}\right)\right]\cdot\rho^{\alpha_{m+1}}(\mathbf{b}_{m+1})\leq\prod\limits_{i=1}^{m+1}\rho^{\alpha_{i}}(\mathbf{b}_{i}).$

By mathematical induction, this lemma is proved. $\hfill\Box$

###  2.3 Antisymmetric Tensor Product

Let $\mathfrak{H}$ be a space of Hermitian tensors with Hermitian rank $r$.
Two tensors $\mathcal{C},\mathcal{B}\in\mathfrak{H}$ is said
$\mathcal{C}\geq\mathcal{B}$ if $\mathcal{C}-\mathcal{B}$ is a nonnegative
Hermitian tensor. For any $k\in\\{1,2,\cdots,r\\}$, let $\mathfrak{H}^{\otimes
k}$ be the $k$-th tensor power of the tensor space $\mathfrak{H}$ and let
$\mathfrak{H}^{\wedge k}$ be the antisymmetric subspace of
$\mathfrak{H}^{\otimes k}$. The $k$-th antisymmetric tensor power,
$\wedge^{k}:\mathcal{C}\rightarrow\mathcal{C}^{\wedge k}$, maps any Hermitian
tensor $\mathcal{C}$ to the restriction of $\mathcal{C}^{\otimes
k}\in\mathfrak{H}^{\otimes k}$ to the antisymmetric subspace
$\mathfrak{H}^{\wedge k}$ of $\mathfrak{H}^{\otimes k}$. Following lemma
summarizes several useful properties of such antisymmetric tensor products.

######  Lemma 2.7.

Let
$\mathcal{C},\mathcal{B},\mathcal{C},\mathcal{D}\in\mathbb{C}^{I_{1}\times\cdots\times
I_{N}\times I_{1}\times\cdots\times I_{N}}$ be Hermitian tensors from
$\mathfrak{H}$ with Hermitian rank $r$. For any $k\in\\{1,2,\cdots,r\\}$, we
have

  1. [1]

$(\mathcal{C}^{\wedge k})^{H}=(\mathcal{C}^{H})^{\wedge k}$,.

  2. [2]

$(\mathcal{C}^{\wedge k})\star_{N}(\mathcal{B}^{\wedge
k})=(\mathcal{C}\star_{N}\mathcal{B})^{\wedge k}$.

  3. [3]

If
$\lim\limits_{i\rightarrow\infty}\left\|\mathcal{C}_{i}-\mathcal{C}\right\|\rightarrow
0$ , then $\lim\limits_{i\rightarrow\infty}\left\|\mathcal{C}^{\wedge
k}_{i}-\mathcal{C}^{\wedge k}\right\|\rightarrow 0$.

  4. [4]

If $\mathcal{C}\geq\mathcal{O}$ (zero tensor), then $\mathcal{C}^{\wedge
k}\geq\mathcal{O}$ and $(\mathcal{C}^{p})^{\wedge k}=(\mathcal{C}^{\wedge
k})^{p}$ for all $p\in\mathbb{R}_{\geq 0}$.

  5. [5]

$|\mathcal{C}|^{\wedge k}=|\mathcal{C}^{\wedge k}|$.

  6. [6]

If $\mathcal{D}\geq\mathcal{O}$ and $\mathcal{D}$ is invertibale,
$(\mathcal{D}^{z})^{\wedge k}=(\mathcal{D}^{\wedge k})^{z}$ for all
$z\in\mathbb{C}$.

  7. [7]

$\left\|\mathcal{C}^{\wedge
k}\right\|=\prod\limits_{i=1}^{k}\lambda_{i}(|\mathcal{C}|)$.

Proof: Facts [1] and [2] are the restrictions of the associated relations
$(\mathcal{C}^{H})^{\otimes k}=(\mathcal{C}^{\otimes k})^{H}$ and
$(\mathcal{C}\star_{N}\mathcal{B})^{\otimes k}=(\mathcal{C}^{\otimes
k})\star_{N}(\mathcal{B}^{\otimes k})$ to $\mathfrak{H}^{\wedge k}$. The fact
[3] is true since, if
$\lim\limits_{i\rightarrow\infty}\left\|\mathcal{C}_{i}-\mathcal{C}\right\|\rightarrow
0$, we have $\lim\limits_{i\rightarrow\infty}\left\|\mathcal{C}^{\otimes
k}_{i}-\mathcal{C}^{\otimes k}\right\|\rightarrow 0$ and the asscoaited
restrictions of $\mathcal{C}_{i}^{\otimes k},\mathcal{C}^{\otimes k}$ to the
antisymmetric subspace $\mathfrak{H}^{k}$.

For the fact [4], if $\mathcal{C}\geq\mathcal{O}$, then we have
$\mathcal{C}^{\wedge k}=((\mathcal{C}^{1/2})^{\wedge
k})^{H}\star_{N}((\mathcal{C}^{1/2})^{\wedge k})\geq\mathcal{O}$ from facts
[1] and [2]. If $p$ is ratonal, we have $(\mathcal{C}^{p})^{\wedge
k}=(\mathcal{C}^{\wedge k})^{p}$ from the fact [2], and the equality
$(\mathcal{C}^{p})^{\wedge k}=(\mathcal{C}^{\wedge k})^{p}$ is also true for
any $p>0$ if we apply the fact [3] to approximate any irrelational numbers by
rational numbers.

Because we have

(25) $\displaystyle|\mathcal{C}|^{\wedge
k}=\left(\sqrt{\mathcal{C}^{H}\mathcal{C}}\right)^{\wedge
k}=\sqrt{(\mathcal{C}^{\wedge k})^{H}\mathcal{C}^{\wedge
k}}=|\mathcal{C}^{\wedge k}|,$

from facts [1], [2] and [4], so the fact [5] is valid.

For the fact [6], if $z<0$, the fact [6] is true for all $z\in\mathbb{R}$ by
applying the fact [4] to $\mathcal{D}^{-1}$. Since we can apply the definition
$\mathcal{D}^{z}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\exp(z\ln\mathcal{D})$ to have

(26) $\displaystyle\mathcal{C}^{p}$ $\displaystyle=$
$\displaystyle\mathcal{D}^{z}~{}~{}\leftrightarrow~{}~{}\mathcal{C}=\exp\left(\frac{z}{p}\ln\mathcal{D}\right),$

where $\mathcal{C}\geq\mathcal{O}$. The general case of any $z\in\mathbb{C}$
is also true by applying the fact [4] to
$\mathcal{C}=\exp(\frac{z}{p}\ln\mathcal{D})$.

For the fact [7] proof, it is enough to prove the case that
$\mathcal{C}\geq\mathcal{O}$ due to the fact [5]. Then, there exisits a set of
orthogonal tensors $\\{\mathcal{U}_{1},\cdots,\mathcal{U}_{r}\\}$ such that
$\mathcal{C}\star_{N}\mathcal{U}_{i}=\lambda_{i}\mathcal{U}_{i}$ for $1\leq
i\leq r$. We then have

(27) $\displaystyle\mathcal{C}^{\wedge
k}\left(\mathcal{U}_{i_{1}}\wedge\cdots\wedge\mathcal{U}_{i_{k}}\right)$
$\displaystyle=$
$\displaystyle\mathcal{C}\star_{N}\mathcal{U}_{i_{1}}\wedge\cdots\wedge\mathcal{C}\star_{N}\mathcal{U}_{i_{k}}$
$\displaystyle=$
$\displaystyle\left(\prod\limits_{i=1}^{k}\lambda_{i}(|\mathcal{C}|)\right)\mathcal{U}_{i_{1}}\wedge\cdots\wedge\mathcal{U}_{i_{k}}.$

Hence, $\left\|\mathcal{C}^{\wedge
k}\right\|=\prod\limits_{i=1}^{k}\lambda_{i}(|\mathcal{C}|)$. $\hfill\Box$

###  2.4 Majorization

In this subsection, we will discuss majorization and several lemmas about
majorization which will be used at later proofs.

Let
$\mathbf{x}=[x_{1},\cdots,x_{r}]\in\mathbb{R}^{r},\mathbf{y}=[y_{1},\cdots,y_{r}]\in\mathbb{R}^{r}$
be two vectors with following orders among entries $x_{1}\geq\cdots\geq x_{r}$
and $y_{1}\geq\cdots\geq y_{r}$, _weak majorization_ between vectors
$\mathbf{x},\mathbf{y}$, represented by $\mathbf{x}\prec_{w}\mathbf{y}$,
requires following relation for vectors $\mathbf{x},\mathbf{y}$:

(28) $\displaystyle\sum\limits_{i=1}^{k}x_{i}\leq\sum\limits_{i=1}^{k}y_{i},$

where $k\in\\{1,2,\cdots,r\\}$. _Majorization_ between vectors
$\mathbf{x},\mathbf{y}$, indicated by $\mathbf{x}\prec\mathbf{y}$, requires
following relation for vectors $\mathbf{x},\mathbf{y}$:

$\displaystyle\sum\limits_{i=1}^{k}x_{i}$ $\displaystyle\leq$
$\displaystyle\sum\limits_{i=1}^{k}y_{i},~{}~{}\mbox{for $1\leq k<r$;}$ (29)
$\displaystyle\sum\limits_{i=1}^{r}x_{i}$ $\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{r}y_{i},~{}~{}\mbox{for $k=r$.}$

For $\mathbf{x},\mathbf{y}\in\mathbb{R}^{r}_{\geq 0}$ such that
$x_{1}\geq\cdots\geq x_{r}$ and $y_{1}\geq\cdots\geq y_{r}$, _weak log
majorization_ between vectors $\mathbf{x},\mathbf{y}$, represented by
$\mathbf{x}\prec_{w\log}\mathbf{y}$, requires following relation for vectors
$\mathbf{x},\mathbf{y}$:

(30)
$\displaystyle\prod\limits_{i=1}^{k}x_{i}\leq\prod\limits_{i=1}^{k}y_{i},$

where $k\in\\{1,2,\cdots,r\\}$, and _log majorization_ between vectors
$\mathbf{x},\mathbf{y}$, represented by $\mathbf{x}\prec_{\log}\mathbf{y}$,
requires equality for $k=r$ in Eq. (30). If $f$ is a single variable function,
$f(\mathbf{x})$ represents a vector of $[f(x_{1}),\cdots,f(x_{r})]$. From
Lemma 1 in [12], we have

######  Lemma 2.8.

(1) For any convex function $f:[0,\infty)\rightarrow[0,\infty)$, if we have
$\mathbf{x}\prec\mathbf{y}$, then $f(\mathbf{x})\prec_{w}f(\mathbf{y})$.
(2) For any convex function and non-decreasing
$f:[0,\infty)\rightarrow[0,\infty)$, if we have
$\mathbf{x}\prec_{w}\mathbf{y}$, then $f(\mathbf{x})\prec_{w}f(\mathbf{y})$.

Another lemma is from Lemma 12 in [12], we have

######  Lemma 2.9.

Let $\mathbf{x},\mathbf{y}\in\mathbb{R}^{r}_{\geq 0}$ such that
$x_{1}\geq\cdots\geq x_{r}$ and $y_{1}\geq\cdots\geq y_{r}$ with
$\mathbf{x}\prec_{\log}\mathbf{y}$. Also let
$\mathbf{y}_{i}=[y_{i;1},\cdots,y_{i;r}]\in\mathbb{R}^{r}_{\geq 0}$ be a
sequence of vectors such that $y_{i;1}\geq\cdots\geq y_{i;r}>0$ and
$\mathbf{y}_{i}\rightarrow\mathbf{y}$ as $i\rightarrow\infty$. Then, there
exists $i_{0}\in\mathbb{N}$ and
$\mathbf{x}_{i}=[x_{i;1},\cdots,x_{i;r}]\in\mathbb{R}^{r}_{\geq 0}$ for $i\geq
i_{0}$ such that $x_{i;1}\geq\cdots\geq x_{i;r}>0$,
$\mathbf{x}_{i}\rightarrow\mathbf{x}$ as $i\rightarrow\infty$, and

(31) $\displaystyle\mathbf{x}_{i}\prec_{\log}\mathbf{y}_{i}\mbox{~{}~{}for
$i\geq i_{0}$.}$

For any function $f$ on $\mathbb{R}_{\geq 0}$, the term $f(\mathbf{x})$ is
defined as $f(\mathbf{x})\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}(f(x_{1}),\cdots,f(x_{r}))$ with conventions $e^{-\infty}=0$ and
$\log 0=-\infty$.

##  3 Multivariate Tensor Norm Inequalities

In this section, we will develop several theorems about majorization in
Section 3.1, and log majorization with integral average in Section 3.2. These
majorization related theorems will provide us tools in deriving bounds for Ky
Fan $k$-norms of multivariate tensors in Section 3.3.

###  3.1 Majorization wtih Integral Average

Let $\Omega$ be a $\sigma$-compact metric space and $\nu$ a probability
measure on the Borel $\sigma$-field of $\Omega$. Let
$\mathcal{C},\mathcal{D}_{\tau}\in\mathbb{C}^{I_{1}\times\cdots\times
I_{N}\times I_{1}\times\cdots\times I_{N}}$ be Hermitian tensors with
Hermitian rank $r$. We further assume that tensors
$\mathcal{C},\mathcal{D}_{\tau}$ are uniformly bounded in their norm for
$\tau\in\Omega$. Let $\tau\in\Omega\rightarrow\mathcal{D}_{\tau}$ be a
continuous function such that
$\sup\\{\left\|D_{\tau}\right\|:\tau\in\Omega\\}<\infty$. For notational
convenience, we define the following relation:

(32)
$\displaystyle\left[\int_{\Omega}\lambda_{1}(\mathcal{D}_{\tau})d\nu(\tau),\cdots,\int_{\Omega}\lambda_{r}(\mathcal{D}_{\tau})d\nu(\tau)\right]\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\int_{\Omega^{r}}\vec{\lambda}(\mathcal{D}_{\tau})d\nu^{r}(\tau).$

If $f$ is a single variable function, the notation $f(\mathcal{C})$ represents
a tensor function with respect to the tensor $\mathcal{C}$. We want to prove
the following theorem about weak majorization of the integral average.

######  Theorem 3.1.

Let $\Omega,\nu,\mathcal{C},\mathcal{D}_{\tau}$ be defined as the beginning
part of Section 3.1, and $f:\mathbb{R}\rightarrow[0,\infty)$ be a non-
decreasing convex function, we have following two equivalent statements:

(33)
$\displaystyle\vec{\lambda}(\mathcal{C})\prec_{w}\int_{\Omega^{r}}\vec{\lambda}(\mathcal{D}_{\tau})d\nu^{r}(\tau)\Longleftrightarrow\left\|f(\mathcal{C})\right\|_{(k)}\leq\int_{\Omega}\left\|f(\mathcal{D}_{\tau})\right\|_{(k)}d\nu(\tau),$

where $\left\|\cdot\right\|_{(k)}$ is the Ky Fan $k$-norm defined by Eq. (19).

Proof: We assume that the left statement of Eq. (33) is true and the function
$f$ is a non-decreasing convex function. From Lemma 2.8, we have

(34)
$\displaystyle\vec{\lambda}(f(\mathcal{C}))=f(\vec{\lambda}(\mathcal{C}))\prec_{w}f\left(\int_{\Omega^{r}}\vec{\lambda}(\mathcal{D}_{\tau})d\nu^{r}(\tau)\right).$

From the convexity of $f$, we also have

(35) $\displaystyle
f\left(\int_{\Omega^{r}}\vec{\lambda}(\mathcal{D}_{\tau})d\nu^{r}(\tau)\right)\leq\int_{\Omega^{r}}f(\vec{\lambda}(\mathcal{D}_{\tau}))d\nu^{r}(\tau)=\int_{\Omega^{r}}\vec{\lambda}(f(\mathcal{D}_{\tau}))d\nu^{r}(\tau).$

Then, we obtain
$\vec{\lambda}(f(\mathcal{C}))\prec_{w}\int_{\Omega^{r}}\vec{\lambda}(f(\mathcal{D}_{\tau}))d\nu^{r}(\tau)$.
By applying Lemma 4.4.2 in [11] to both sides of
$\vec{\lambda}(f(\mathcal{C}))\prec_{w}\int_{\Omega^{r}}\vec{\lambda}(f(\mathcal{D}_{\tau}))d\nu^{r}(\tau)$
with gauge function $\rho$ of Ky Fan $k$-norm, we obtain

(36) $\displaystyle\left\|f(\mathcal{C})\right\|_{(k)}$ $\displaystyle\leq$
$\displaystyle\rho\left(\int_{\Omega^{r}}\vec{\lambda}(f(\mathcal{D}_{\tau}))d\nu^{r}(\tau)\right)$
$\displaystyle\leq$
$\displaystyle\int_{\Omega}\rho(\vec{\lambda}(f(\mathcal{D}_{\tau})))d\nu(\tau)=\int_{\Omega}\left\|f(\mathcal{D}_{\tau})\right\|_{(k)}d\nu(\tau).$

Therefore, the right statement of Eq. (33) is true from the left statement.

On the other hand, if the right statement of Eq. (33) is true, we select a
function $f\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}\max\\{x+c,0\\}$,
where $c$ is a postive real constant satisfying
$\mathcal{C}+c\mathcal{I}\geq\mathcal{O}$,
$\mathcal{D}_{\tau}+c\mathcal{I}\geq\mathcal{O}$ for all $\tau\in\Omega$, and
tensors $\mathcal{C}+c\mathcal{I},\mathcal{D}_{\tau}+c\mathcal{I}$ having
Hermitian rank $r$. If the Ky Fan norm $k$-norm at the right statement of Eq.
(33) is applied, we have

(37)
$\displaystyle\sum\limits_{i=1}^{k}(\lambda_{i}(\mathcal{C})+c)\leq\sum\limits_{i=1}^{k}\int_{\Omega}(\lambda_{i}(\mathcal{D}_{\tau})+c)d\nu(\tau).$

Hence,
$\sum\limits_{i=1}^{k}\lambda_{i}(\mathcal{C})\leq\sum\limits_{i=1}^{k}\int_{\Omega}\lambda_{i}(\mathcal{D}_{\tau})d\nu(\tau)$,
this is the left statement of Eq. (33). $\hfill\Box$

Next theorem will provide a stronger version of Theorem 3.1 by enhancing weak
majorization to majorization.

######  Theorem 3.2.

Let $\Omega,\nu,\mathcal{C},\mathcal{D}_{\tau}$ be defined as the beginning
part of Section 3.1, and $f:\mathbb{R}\rightarrow[0,\infty)$ be a convex
function, we have following two equivalent statements:

(38)
$\displaystyle\vec{\lambda}(\mathcal{C})\prec\int_{\Omega^{r}}\vec{\lambda}(\mathcal{D}_{\tau})d\nu^{r}(\tau)\Longleftrightarrow\left\|f(\mathcal{C})\right\|_{(k)}\leq\int_{\Omega}\left\|f(\mathcal{D}_{\tau})\right\|_{(k)}d\nu(\tau).$

Proof: We assume that the left statement of Eq. (38) is true and the function
$f$ is a convex function. Again, from Lemma 2.8, we have

(39)
$\displaystyle\vec{\lambda}(f(\mathcal{C}))=f(\vec{\lambda}(\mathcal{C}))\prec_{w}f\left(\left(\int_{\Omega^{r}}\vec{\lambda}(\mathcal{D}_{\tau})d\nu^{r}(\tau)\right)\right)\leq\int_{\Omega^{r}}f(\vec{\lambda}(\mathcal{D}_{\tau}))d\nu^{r}(\tau),$

then,

(40) $\displaystyle\left\|f(\mathcal{C})\right\|_{(k)}$ $\displaystyle\leq$
$\displaystyle\rho\left(\int_{\Omega^{r}}f(\vec{\lambda}(\mathcal{D}_{\tau}))d\nu^{r}(\tau)\right)$
$\displaystyle\leq$
$\displaystyle\int_{\Omega}\rho\left(f(\vec{\lambda}(\mathcal{D}_{\tau}))\right)d\nu(\tau)=\int_{\Omega}\left\|f(\mathcal{D}_{\tau})\right\|_{(k)}d\nu(\tau),$

where $\rho$ is the gauge function of Ky Fan $k$-norm. This proves the right
statement of Eq. (38).

Now, we assume that the right statement of Eq. (38) is true. From Theorem 3.1,
we already have
$\vec{\lambda}(\mathcal{C})\prec_{w}\int_{\Omega^{r}}\vec{\lambda}(\mathcal{D}_{\tau})d\nu^{r}(\tau)$.
It is enough to prove
$\sum\limits_{i=1}^{r}\lambda_{i}(\mathcal{C})\geq\int_{\Omega}\sum\limits_{i=1}^{r}\lambda_{i}(\mathcal{D}_{\tau})d\nu(\tau)$.
We define a function $f\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\max\\{c-x,0\\}$, where $c$ is a postive real constant satisfying
$\mathcal{C}\leq c\mathcal{I}$, $\mathcal{D}_{\tau}\leq c\mathcal{I}$ for all
$\tau\in\Omega$ and tensors
$c\mathcal{I}-\mathcal{C},c\mathcal{I}-\mathcal{D}_{\tau}$ having Hermitian
rank $r$. If the trace norm is applied, i.e., the sum of the absolute value of
all eigenvalues of a Hermitian tensor, then the right statement of Eq. (38)
becomes

(41)
$\displaystyle\sum\limits_{i=1}^{r}\lambda_{i}\left(c\mathcal{I}-\mathcal{C}\right)\leq\int_{\Omega}\sum\limits_{i=1}^{r}\lambda_{i}\left(c\mathcal{I}-\mathcal{D}_{\tau}\right)d\nu(\tau).$

The desired inequality
$\sum\limits_{i=1}^{r}\lambda_{i}(\mathcal{C})\geq\int_{\Omega}\sum\limits_{i=1}^{r}\lambda_{i}(\mathcal{D}_{\tau})d\nu(\tau)$
is established. $\hfill\Box$

###  3.2 Log-Majorization wtih Integral Average

The purpose of this section is to consider log-majorization issues for Ky Fan
$k$-norm of Hermitian tensors. In this section, let
$\mathcal{C},\mathcal{D}_{\tau}\in\mathbb{C}^{I_{1}\times\cdots\times
I_{N}\times I_{1}\times\cdots\times I_{N}}$ be nonnegative Hermitian tensors
with Hermitian rank $r$, i,e, all Hermitian eigenvalues are positive, and keep
other notations with the same definitions as at the beginning of the Section
3.1. For notational convenience, we define the following relation for
logarithm vector:

(42)
$\displaystyle\left[\int_{\Omega}\log\lambda_{1}(\mathcal{D}_{\tau})d\nu(\tau),\cdots,\int_{\Omega}\log\lambda_{r}(\mathcal{D}_{\tau})d\nu(\tau)\right]\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\int_{\Omega^{r}}\log\vec{\lambda}(\mathcal{D}_{\tau})d\nu^{r}(\tau).$

Following theorem is used to build the relationship between weak log-
majorization of eigenvalues and Ky Fan $k$-norm.

######  Theorem 3.3.

Let $\mathcal{C},\mathcal{D}_{\tau}$ be nonnegative Hermitian tensors,
$f:(0,\infty)\rightarrow[0,\infty)$ be a continous function such that the
mapping $x\rightarrow\log f(e^{x})$ is convex on $\mathbb{R}$, and
$g:(0,\infty)\rightarrow[0,\infty)$ be a continous function such that the
mapping $x\rightarrow g(e^{x})$ is convex on $\mathbb{R}$ , then we have
following three equivalent statements:

(43) $\displaystyle\vec{\lambda}(\mathcal{C})$ $\displaystyle\prec_{w\log}$
$\displaystyle\exp\int_{\Omega^{r}}\log\vec{\lambda}(\mathcal{D}_{\tau})d\nu^{r}(\tau);$
(44) $\displaystyle\left\|f(\mathcal{C})\right\|_{(k)}$ $\displaystyle\leq$
$\displaystyle\exp\int_{\Omega}\log\left\|f(\mathcal{D}_{\tau})\right\|_{(k)}d\nu(\tau);$
(45) $\displaystyle\left\|g(\mathcal{C})\right\|_{(k)}$ $\displaystyle\leq$
$\displaystyle\int_{\Omega}\left\|g(\mathcal{D}_{\tau})\right\|_{(k)}d\nu(\tau).$

Proof: The roadmap of this proof is to prove equivalent statements between Eq.
(43) and Eq. (44) first, followed by equivalent statements between Eq. (43)
and Eq. (45).

Eq. (43) $\Longrightarrow$ Eq. (44)

There are two cases to be discussed in this part of proof:
$\mathcal{C},\mathcal{D}_{\tau}$ are positive Hermitian tensors, and
$\mathcal{C},\mathcal{D}_{\tau}$ are nonnegative Hermitian tensors. We
consider the case that $\mathcal{C},\mathcal{D}_{\tau}$ are positive Hermitian
tensors first.

Since $\mathcal{D}_{\tau}$ are positive, we can find $\varepsilon>0$ such that
$\mathcal{D}_{\tau}\geq\varepsilon\mathcal{I}$ for all $\tau\in\Omega$. From
Eq. (43), the convexity of $\log f(e^{x})$ and Lemma 2.8, we have

(46)
$\displaystyle\vec{\lambda}\left(f(\mathcal{C})\right)=f\left(\exp\left(\log\vec{\lambda}(\mathcal{C})\right)\right)$
$\displaystyle\prec_{w}$ $\displaystyle
f\left(\exp\int_{\Omega^{r}}\log\vec{\lambda}(\mathcal{D}_{\tau})d\nu^{r}(\tau)\right)$
$\displaystyle\leq$ $\displaystyle\exp\left(\int_{\Omega^{r}}\log
f\left(\vec{\lambda}(\mathcal{D}_{\tau})\right)d\nu^{r}(\tau)\right).$

Then, from Eq. (18), we obtain

(47) $\displaystyle\left\|f(\mathcal{C})\right\|_{\rho}$ $\displaystyle\leq$
$\displaystyle\rho\left(\exp\left(\int_{\Omega^{r}}\log
f\left(\vec{\lambda}(\mathcal{D}_{\tau})\right)d\nu^{r}(\tau)\right)\right).$

From the function $f$ properties, we can assume that $f(x)>0$ for any $x>0$.
Then, we have following bounded and continous maps on $\Omega$:
$\tau\rightarrow\log f(\lambda_{i}(\mathcal{D}_{\tau}))$ for
$i\in\\{1,2,\cdots,r\\}$, and
$\tau\rightarrow\log\left\|f(\mathcal{D}_{\tau})\right\|_{(k)}$. Because we
have $\nu(\Omega)=1$ and $\sigma$-compactness of $\Omega$, we have
$\tau_{k}^{(n)}\in\Omega$ and $\alpha_{k}^{(n)}$ for $k\in\\{1,2,\cdots,n\\}$
and $n\in\mathbb{N}$ with $\sum\limits_{k=1}^{n}\alpha_{k}^{(n)}=1$ such that

(48) $\displaystyle\int_{\Omega}\log
f(\lambda_{i}(\mathcal{D}_{\tau}))d\nu(\tau)=\lim\limits_{n\rightarrow\infty}\sum\limits_{k=1}^{n}\alpha_{k}^{(n)}\log
f(\lambda_{i}(\mathcal{D}_{\tau_{k}^{(n)}})),\mbox{for $i\in\\{1,2,\cdots
r\\}$};$

and

(49)
$\displaystyle\int_{\Omega}\log\left\|f(\mathcal{D}_{\tau})\right\|_{(k)}d\nu(\tau)=\lim\limits_{n\rightarrow\infty}\sum\limits_{k=1}^{n}\alpha_{k}^{(n)}\log\left\|f(\mathcal{D}_{\tau_{k}^{(n)}})\right\|_{(k)}.$

By taking the exponential at both sides of Eq. (48) and apply the gauge
function $\rho$, we have

(50) $\displaystyle\rho\left(\exp\int_{\Omega^{r}}\log
f(\vec{\lambda}(\mathcal{D}_{\tau}))d\nu^{r}(\tau)\right)=\lim\limits_{n\rightarrow\infty}\rho\left(\prod\limits_{k=1}^{n}f\left(\vec{\lambda}\left(\mathcal{D}_{\tau_{k}^{(n)}}\right)\right)^{\alpha_{k}^{(n)}}\right).$

Similarly, by taking the exponential at both sides of Eq. (49), we have

(51)
$\displaystyle\exp\left(\int_{\Omega}\log\left\|f(\mathcal{D}_{\tau})\right\|_{(k)}d\nu(\tau)\right)=\lim\limits_{n\rightarrow\infty}\prod\limits_{k=1}^{n}\left\|f\left(\mathcal{D}_{\tau_{k}^{(n)}}\right)\right\|^{\alpha_{k}^{(n)}}_{(k)}.$

From Lemma 2.6, we have

(52)
$\displaystyle\rho\left(\prod\limits_{k=1}^{n}f\left(\vec{\lambda}\left(\mathcal{D}_{\tau_{k}^{(n)}}\right)\right)^{\alpha_{k}^{(n)}}\right)$
$\displaystyle\leq$
$\displaystyle\prod\limits_{k=1}^{n}\rho^{\alpha_{k}^{(n)}}\left(f\left(\vec{\lambda}\left(\mathcal{D}_{\tau_{k}^{(n)}}\right)\right)\right)$
$\displaystyle=$
$\displaystyle\prod\limits_{k=1}^{n}\rho^{\alpha_{k}^{(n)}}\left(\vec{\lambda}\left(f\left(\mathcal{D}_{\tau_{k}^{(n)}}\right)\right)\right)$
$\displaystyle=$
$\displaystyle\prod\limits_{k=1}^{n}\left\|f\left(\mathcal{D}_{\tau_{k}^{(n)}}\right)\right\|_{(k)}^{\alpha_{k}^{(n)}}$

From Eqs. (50), (51) and (52), we have

(53) $\displaystyle\rho\left(\exp\int_{\Omega^{r}}\log
f(\vec{\lambda}(\mathcal{D}_{\tau}))d\nu^{r}(\tau)\right)\leq\exp\int_{\Omega}\log\left\|f(\mathcal{D}_{\tau})\right\|_{(k)}d\nu(\tau).$

Then, Eq. (44) is proved from Eqs. (47) and (53).

Next, we consider that $\mathcal{C},\mathcal{D}_{\tau}$ are nonnegative
Hermitian tensors. For any $\delta>0$, we have following log-majorization
relation:

(54)
$\displaystyle\prod\limits_{i=1}^{k}\left(\lambda_{i}(\mathcal{C})+\epsilon_{\delta}\right)$
$\displaystyle\leq$
$\displaystyle\prod\limits_{i=1}^{k}\exp\int_{\Omega}\log\left(\lambda_{i}(\mathcal{D}_{\tau})+\delta\right)d\nu(\tau),$

where $\delta>\epsilon_{\delta}>0$ and $k\in\\{1,2,\cdots r\\}$. Then, we can
apply the previous case result about positive Hermitian tensors to positive
Hermitian tensors $\mathcal{C}+\epsilon_{\delta}\mathcal{I}$ and
$\mathcal{D}_{\tau}+\delta\mathcal{I}$, and get

(55)
$\displaystyle\left\|f(\mathcal{C})+\epsilon_{\delta}\mathcal{I}\right\|_{(k)}$
$\displaystyle\leq$
$\displaystyle\exp\int_{\Omega}\log\left\|f(\mathcal{D}_{\tau})+\delta\mathcal{I}\right\|_{(k)}d\nu(\tau)$

As $\delta\rightarrow 0$, Eq. (55) will give us Eq. (44) for nonnegative
Hermitian tensors by the monotone convergence theorem.

Eq. (43) $\Longleftarrow$ Eq. (44)

We consider positive Hermitian tensors at first phase by assuming that
$\mathcal{D}_{\tau}$ are positive Hermitian for all $\tau\in\Omega$. We may
also assume that the tensor $\mathcal{C}$ is a positive Hermitian tensor.
Since if this is a nonnegative Hermitian tensor, i.e., some $\lambda_{i}=0$,
we always have following inequality valid:

(56)
$\displaystyle\prod\limits_{i=1}^{k}\lambda_{i}(\mathcal{C})\leq\prod\limits_{i=1}^{k}\exp\int_{\Omega}\log\lambda_{i}(\mathcal{D}_{\tau})d\nu(\tau)$

If we apply $f(x)=x^{p}$ for $p>0$ and $\left\|\cdot\right\|_{(k)}$ as Ky Fan
$k$-norm in Eq. (44), we have

(57)
$\displaystyle\log\sum\limits_{i=1}^{k}\lambda^{p}_{i}\left(\mathcal{C}\right)\leq\int_{\Omega}\log\sum\limits_{i=1}^{k}\lambda_{i}^{p}\left(\mathcal{D}_{\tau}\right)d\nu(\tau).$

If we add $\log\frac{1}{k}$ and multiply $\frac{1}{p}$ at both sides of Eq.
(57), we have

(58)
$\displaystyle\frac{1}{p}\log\left(\frac{1}{k}\sum\limits_{i=1}^{k}\lambda^{p}_{i}\left(\mathcal{C}\right)\right)\leq\int_{\Omega}\frac{1}{p}\log\left(\frac{1}{k}\sum\limits_{i=1}^{k}\lambda_{i}^{p}\left(\mathcal{D}_{\tau}\right)\right)d\nu(\tau).$

From L’Hopital’s Rule, if $p\rightarrow 0$, we have

(59)
$\displaystyle\frac{1}{p}\log\left(\frac{1}{k}\sum\limits_{i=1}^{k}\lambda^{p}_{i}\left(\mathcal{C}\right)\right)\rightarrow\frac{1}{k}\sum\limits_{i=1}^{k}\log\lambda_{i}(\mathcal{C}),$

and

(60)
$\displaystyle\frac{1}{p}\log\left(\frac{1}{k}\sum\limits_{i=1}^{k}\lambda^{p}_{i}\left(\mathcal{D}_{\tau}\right)\right)\rightarrow\frac{1}{k}\sum\limits_{i=1}^{k}\log\lambda_{i}(\mathcal{D}_{\tau}),$

where $\tau\in\Omega$. Appling Eqs. (59) and (60) into Eq. (58) and taking
$p\rightarrow 0$, we have

(61)
$\displaystyle\sum\limits_{i=1}^{k}\lambda_{i}(\mathcal{C})\leq\int_{\Omega}\sum\limits_{i=1}^{k}\log\lambda_{i}(\mathcal{D}_{\tau})d\nu(\tau).$

Therefore, Eq. (43) is true for positive Hermitian tensors.

For nonnegative Hermitian tensors $\mathcal{D}_{\tau}$, since Eq. (44) is
valid for $\mathcal{D}_{\tau}+\delta\mathcal{I}$ for any $\delta>0$, we can
apply the previous case result about positive Hermitian tensors to
$\mathcal{D}_{\tau}+\delta\mathcal{I}$ and obtain

(62)
$\displaystyle\prod\limits_{i=1}^{k}\lambda_{i}(\mathcal{C})\leq\prod\limits_{i=1}^{k}\exp\int_{\Omega}\log\left(\lambda_{i}(\mathcal{D}_{\tau})+\delta\right)d\nu(\tau),$

where $k\in\\{1,2,\cdots,r\\}$. Eq. (43) is still true for nonnegative
Hermitian tensors as $\delta\rightarrow 0$.

Eq. (43) $\Longrightarrow$ Eq. (45)

If $\mathcal{C},\mathcal{D}_{\tau}$ are positive Hermitian tensors, and
$\mathcal{D}_{\tau}\geq\delta\mathcal{I}$ for all $\tau\in\Omega$. From Eq.
(43), we have

(63)
$\displaystyle\vec{\lambda}(\log\mathcal{C})=\log\vec{\lambda}(\mathcal{C})\prec_{w}\int_{\Omega^{r}}\log\vec{\lambda}(\mathcal{D}_{\tau})d\nu^{r}(\tau)=\int_{\Omega^{r}}\vec{\lambda}(\log\mathcal{D}_{\tau})d\nu^{r}(\tau).$

If we apply Theorem 3.1 to $\log\mathcal{C}$, $\log\mathcal{D}_{\tau}$ with
function $f(x)=g(e^{x})$, where $g$ is used in Eq. (45), Eq. (45) is implied.

If $\mathcal{C},\mathcal{D}_{\tau}$ are nonnegative Hermitian tensors and any
$\delta>0$, we can find $\epsilon_{\delta}\in(0,\delta)$ to satisfy following:

(64)
$\displaystyle\prod\limits_{i=1}^{k}\left(\lambda_{i}(\mathcal{C})+\epsilon_{\delta}\right)\leq\prod\limits_{i=1}^{k}\exp\int_{\Omega}\log\left(\lambda_{i}(\mathcal{D}_{\tau})+\delta\right)d\nu(\tau).$

Then, from positive Hermitian tensor case, we have

(65)
$\displaystyle\left\|g(\mathcal{C}+\epsilon_{\delta}\mathcal{I})\right\|_{(k)}\leq\int_{\Omega}\left\|g(\mathcal{D}_{\tau}+\delta\mathcal{I})\right\|_{(k)}d\nu(\tau).$

Eq. (45) is obtained by taking $\delta\rightarrow 0$ in Eq. (65).

Eq. (43) $\Longleftarrow$ Eq. (45)

For $k\in\\{1,2,\cdots,r\\}$, if we apply $g(x)=\log(\delta+x)$, where
$\delta>0$, and Ky Fan $k$-norm in Eq. (45), we have

(66)
$\displaystyle\sum\limits_{i=1}^{k}\log\left(\delta+\lambda_{i}\left(\mathcal{C}\right)\right)\leq\sum\limits_{i=1}^{k}\int_{\Omega}\log\left(\delta+\lambda_{i}(\mathcal{D}_{\tau})\right)d\nu(\tau).$

Then, we have following as $\delta\rightarrow 0$:

(67)
$\displaystyle\sum\limits_{i=1}^{k}\log\lambda_{i}\left(\mathcal{C}\right)\leq\sum\limits_{i=1}^{k}\int_{\Omega}\log\lambda_{i}(\mathcal{D}_{\tau})d\nu(\tau).$

Therefore, Eq. (43) ccan be derived from Eq. (45). $\hfill\Box$

Next theorem will extend Theorem 3.3 to non-weak version.

######  Theorem 3.4.

Let $\mathcal{C},\mathcal{D}_{\tau}$ be nonnegative Hermitian tensors with
$\int_{\Omega}\left\|\mathcal{D}_{\tau}^{-p}\right\|_{\rho}d\nu(\tau)<\infty$
for any $p>0$, $f:(0,\infty)\rightarrow[0,\infty)$ be a continous function
such that the mapping $x\rightarrow\log f(e^{x})$ is convex on $\mathbb{R}$,
and $g:(0,\infty)\rightarrow[0,\infty)$ be a continous function such that the
mapping $x\rightarrow g(e^{x})$ is convex on $\mathbb{R}$ , then we have
following three equivalent statements:

(68) $\displaystyle\vec{\lambda}(\mathcal{C})$ $\displaystyle\prec_{\log}$
$\displaystyle\exp\int_{\Omega^{r}}\log\vec{\lambda}(\mathcal{D}_{\tau})d\nu^{r}(\tau);$
(69) $\displaystyle\left\|f(\mathcal{C})\right\|_{(k)}$ $\displaystyle\leq$
$\displaystyle\exp\int_{\Omega}\log\left\|f(\mathcal{D}_{\tau})\right\|_{(k)}d\nu(\tau);$
(70) $\displaystyle\left\|g(\mathcal{C})\right\|_{(k)}$ $\displaystyle\leq$
$\displaystyle\int_{\Omega}\left\|g(\mathcal{D}_{\tau})\right\|_{(k)}d\nu(\tau).$

Proof:

The proof plan is similar to the proof in Theorem 3.3.

Eq. (68) $\Longrightarrow$ Eq. (69)

First, we assume that $\mathcal{C},\mathcal{D}_{\tau}$ are postiive Hermitian
tensors with $\mathcal{D}_{\tau}\geq\delta\mathcal{I}$ for all
$\tau\in\Omega$. The corresponding part of the proof in Theorem 3.3 about
positive Hermitian tensors $\mathcal{C},\mathcal{D}_{\tau}$ can be applied
here.

For case that $\mathcal{C},\mathcal{D}_{\tau}$ are nonnegative Hermitian
tensors, we have

(71)
$\displaystyle\prod\limits_{i=1}^{k}\lambda_{i}(\mathcal{C})\leq\prod\limits_{i=1}^{k}\exp\int_{\Omega}\log\left(\lambda_{i}(\mathcal{D}_{\tau})+\delta_{n}\right)d\nu(\tau),$

where $\delta_{n}>0$ and $\delta_{n}\rightarrow 0$. Because
$\int_{\Omega^{r}}\log\left(\vec{\lambda}(\mathcal{D}_{\tau})+\delta_{n}\right)d\nu^{r}(\tau)\rightarrow\int_{\Omega^{r}}\log\vec{\lambda}(\mathcal{D}_{\tau})d\nu^{r}(\tau)$
as $n\rightarrow\infty$, from Lemma 2.9, we can find $\mathbf{a}^{(n)}$ with
$n\geq n_{0}$ such that $a^{(n)}_{1}\geq\cdots\geq a^{(n)}_{r}>0$,
$\mathbf{a}^{(n)}\rightarrow\vec{\lambda}(\mathcal{C})$ and
$\mathbf{a}^{(n)}\prec_{\log}\exp\int_{\Omega^{r}}\log\vec{\lambda}\left(\mathcal{D}_{\tau}+\delta_{n}\mathcal{I}\right)d\nu^{r}(\tau)$

Selecting $\mathcal{C}^{(n)}$ with
$\vec{\lambda}(\mathcal{C}^{(n)})=\mathbf{a}^{(n)}$ and applying positive
Hermitian tensors case to $\mathcal{C}^{(n)}$ and
$\mathcal{D}_{\tau}+\delta_{n}\mathcal{I}$, we obtain

(72)
$\displaystyle\left\|f(\mathcal{C}^{(n)})\right\|_{(k)}\leq\exp\int_{\Omega}\log\left\|f(\mathcal{D}_{\tau}+\delta_{n}\mathcal{I})\right\|_{(k)}d\nu(\tau)$

where $n\geq n_{0}$.

There are two situations for the function $f$ near $0$: $f(0^{+})<\infty$ and
$f(0^{+})=\infty$. For the case with $f(0^{+})<\infty$, we have

(73)
$\displaystyle\left\|f(\mathcal{C}^{(n)})\right\|_{(k)}=\rho(f(\mathbf{a}^{(n)}))\rightarrow\rho(f(\vec{\lambda}(\mathcal{C})))=\left\|f(\mathcal{C})\right\|_{(k)},$

and

(74)
$\displaystyle\left\|f(\mathcal{D}_{\tau}+\delta_{n}\mathcal{I})\right\|_{(k)}\rightarrow\left\|f(\mathcal{D}_{\tau})\right\|_{(k)},$

where $\tau\in\Omega$ and $n\rightarrow\infty$. From Fatou–Lebesgue theorem,
we then have

(75)
$\displaystyle\limsup\limits_{n\rightarrow\infty}\int_{\Omega}\log\left\|f(\mathcal{D}_{\tau}+\delta_{n}\mathcal{I})\right\|_{(k)}d\nu(\tau)\leq\int_{\Omega}\log\left\|f(\mathcal{D}_{\tau})\right\|_{(k)}.$

By taking $n\rightarrow\infty$ in Eq. (72) and using Eqs. (73), (74), (75), we
have Eq. (69) for case that $f(0^{+})<\infty$.

For the case with $f(0^{+})=\infty$, we assume that
$\int_{\Omega}\log\left\|f(\mathcal{D}_{\tau})\right\|_{(k)}d\nu(\tau)<\infty$
(since the inequality in Eq. (69) is always true for
$\int_{\Omega}\log\left\|f(\mathcal{D}_{\tau})\right\|_{(k)}d\nu(\tau)=\infty$).
Since $f$ is decreasing on $(0,\epsilon)$ for some $\epsilon>0$. We claim that
the following relation is valid: there are two constants $a,b>0$ such that

(76) $\displaystyle
a\leq\left\|f(\mathcal{D}_{\tau}+\delta_{n}\mathcal{I})\right\|_{(k)}\leq\left\|f(\mathcal{D}_{\tau})\right\|_{(k)}+b,$

for all $\tau\in\Omega$ and $n\geq n_{0}$. If Eq. (76) is valid and
$\int_{\Omega}\log\left\|f(\mathcal{D}_{\tau})\right\|_{(k)}d\nu(\tau)<\infty$,
from Lebesgue’s dominated convergence theorem, we also have Eq. (69) for case
that $f(0^{+})=\infty$ by taking $n\rightarrow\infty$ in Eq. (72).

Now, we want to prove the claim shown by Eq. (76). By the uniform boundedness
of tensors $\mathcal{D}_{\tau}$, there is a constant $\chi>0$ such that

(77) $\displaystyle
0<\mathcal{D}_{\tau}+\delta_{n}\mathcal{I}\leq\chi\mathcal{I},$

where $\tau\in\Omega$ and $n\geq n_{0}$. From Eq. (17), we have

(78) $\displaystyle f(\mathcal{D}_{\tau}+\delta_{n}\mathcal{I})$
$\displaystyle=$ $\displaystyle\sum\limits_{i^{\prime},\mbox{s.t.
$\lambda_{i^{\prime}}(\mathcal{D}_{\tau})+\delta_{n}<\epsilon$}}f(\lambda_{i^{\prime}}(\mathcal{D}_{\tau})+\delta_{n})\mathcal{U}_{i^{\prime}}\otimes\mathcal{U}^{H}_{i^{\prime}}+$
$\displaystyle\sum\limits_{j^{\prime},\mbox{s.t.
$\lambda_{j^{\prime}}(\mathcal{D}_{\tau})+\delta_{n}\geq\epsilon$}}f(\lambda_{j^{\prime}}(\mathcal{D}_{\tau})+\delta_{n})\mathcal{U}_{j^{\prime}}\otimes\mathcal{U}^{H}_{j^{\prime}}$
$\displaystyle\leq$ $\displaystyle\sum\limits_{i^{\prime},\mbox{s.t.
$\lambda_{i^{\prime}}(\mathcal{D}_{\tau})+\delta_{n}<\epsilon$}}f(\lambda_{i^{\prime}}(\mathcal{D}_{\tau}))\mathcal{U}_{i^{\prime}}\otimes\mathcal{U}^{H}_{i^{\prime}}+$
$\displaystyle\sum\limits_{j^{\prime},\mbox{s.t.
$\lambda_{j^{\prime}}(\mathcal{D}_{\tau})+\delta_{n}\geq\epsilon$}}f(\lambda_{j^{\prime}}(\mathcal{D}_{\tau})+\delta_{n})\mathcal{U}_{j^{\prime}}\otimes\mathcal{U}^{H}_{j^{\prime}}$
$\displaystyle\leq$ $\displaystyle
f(\mathcal{D}_{\tau})+\sum\limits_{j^{\prime},\mbox{s.t.
$\lambda_{j^{\prime}}(\mathcal{D}_{\tau})+\delta_{n}\geq\epsilon$}}f(\lambda_{j^{\prime}}(\mathcal{D}_{\tau})+\delta_{n})\mathcal{U}_{j^{\prime}}\otimes\mathcal{U}^{H}_{j^{\prime}}.$

Therefore, the claim in Eq. (76) follows by the triangle inequality for
$\left\|\cdot\right\|_{(k)}$ and
$f(\lambda_{j^{\prime}}(\mathcal{D}_{\tau})+\delta_{n})<\infty$ for
$\lambda_{j^{\prime}}(\mathcal{D}_{\tau})+\delta_{n}\geq\epsilon$.

Eq. (68) $\Longleftarrow$ Eq. (69)

The weak majorization relation

(79)
$\displaystyle\prod\limits_{i=1}^{k}\lambda_{i}(\mathcal{C})\leq\prod\limits_{i=1}^{k}\exp\int_{\Omega}\log\lambda_{i}(\mathcal{D}_{\tau})d\nu(\tau),$

is valid for $k<r$ from Eq. (43) $\Longrightarrow$ Eq. (44) in Theorem 3.3. We
wish to prove that Eq. (79) becomes equal for $k=r$. It is equivalent to prove
that

(80)
$\displaystyle\log\det\nolimits_{H}(\mathcal{C})\geq\int_{\Omega}\log\det\nolimits_{H}(\mathcal{D}_{\tau})d\nu(\tau),$

where $\det\nolimits_{H}(\cdot)$ is the _Hermitian determinant_. We can assume
that
$\int_{\Omega}\log\det\nolimits_{H}(\mathcal{D}_{\tau})d\nu(\tau)\geq-\infty$
since Eq. (80) is true for
$\int_{\Omega}\log\det\nolimits_{H}(\mathcal{D}_{\tau})d\nu(\tau)=-\infty$.
Then, $\mathcal{D}_{\tau}$ are positive Hermitian tensors.

If we scale tensors $\mathcal{C},\mathcal{D}_{\tau}$ as
$a\mathcal{C},a\mathcal{D}_{\tau}$ by some $a>0$, we can assume
$\mathcal{D}_{\tau}\leq\mathcal{I}$ and $\lambda_{i}(\mathcal{D}_{\tau})\leq
1$ for all $\tau\in\Omega$ and $i\in\\{1,2,\cdots,r\\}$. Then for any $p>0$,
we have

(81)
$\displaystyle\frac{1}{r}\left\|\mathcal{D}_{\tau}^{-p}\right\|_{1}\leq\lambda^{-p}_{r}(\mathcal{D}_{\tau})\leq(\det\nolimits_{H}(\mathcal{D}_{\tau}))^{-p},$

where $\left\|\cdot\right\|_{1}$ represents the tensor trace norm, and

(82)
$\displaystyle\frac{1}{p}\log\left(\frac{\left\|\mathcal{D}^{-p}_{\tau}\right\|_{1}}{r}\right)\leq-\log\det\nolimits_{H}(\mathcal{D}_{\tau}).$

If we use tensor trace norm as unitarily invariant tensor norm and
$f(x)=x^{-p}$ for any $p>0$ in Eq. (69), we obtain

(83)
$\displaystyle\log\left\|\mathcal{C}^{-p}\right\|_{1}\leq\int_{\Omega}\log\left\|\mathcal{D}^{-p}_{\tau}\right\|_{1}d\nu(\tau).$

By adding $\log\frac{1}{r}$ and multiplying $\frac{1}{p}$ for both sides of
Eq. (83), we have

(84)
$\displaystyle\frac{1}{p}\log\left(\frac{\left\|\mathcal{C}^{-p}\right\|_{1}}{r}\right)\leq\int_{\Omega}\frac{1}{p}\log\left(\frac{\left\|\mathcal{D}_{\tau}^{-p}\right\|_{1}}{r}\right)d\nu(\tau)$

Similar to Eqs. (59) and (60), we have following two relations as
$p\rightarrow 0$:

(85)
$\displaystyle\frac{1}{p}\log\left(\frac{\left\|\mathcal{C}^{-p}\right\|_{1}}{r}\right)\rightarrow\frac{-\log\det\nolimits_{H}(\mathcal{C})}{r},$

and

(86)
$\displaystyle\frac{1}{p}\log\left(\frac{\left\|\mathcal{D}_{\tau}^{-p}\right\|_{1}}{r}\right)\rightarrow\frac{-\log\det\nolimits_{H}(\mathcal{D}_{\tau})}{r}.$

From Eq. (82) and Lebesgue’s dominated convergence theorem, we have

(87) $\displaystyle\lim\limits_{p\rightarrow
0}\int_{\Omega}\frac{1}{p}\log\left(\frac{\left\|\mathcal{D}_{\tau}^{-p}\right\|_{1}}{r}\right)d\nu(\tau)=\frac{-1}{r}\int_{\Omega}\log\det\nolimits_{H}(\mathcal{D}_{\tau})\nu(\tau)$

Finally, we have Eq. (80) from Eqs. (84) and (87).

Eq. (68) $\Longrightarrow$ Eq. (70)

First, we assume that $\mathcal{C},\mathcal{D}_{\tau}$ are positive Hermitian
tensors and $\mathcal{D}_{\tau}\geq\delta\mathcal{I}$ for $\tau\in\Omega$.
From Eq. (68), we can apply Theorem 3.2 to
$\log\mathcal{C},\log\mathcal{D}_{\tau}$ and $f(x)=g(e^{x})$ to obtain Eq.
(70).

For $\mathcal{C},\mathcal{D}_{\tau}$ are nonnegative Hermitian tensors, we can
choose $\mathbf{a}^{(n)}$ and corresponding $\mathcal{C}^{(n)}$ for $n\geq
n_{0}$ given $\delta_{n}\rightarrow 0$ with $\delta_{n}>0$ as the proof in Eq.
(68) $\Longrightarrow$ Eq. (69). Since tensors
$\mathcal{C}^{(n)},\mathcal{D}_{\tau}+\delta_{n}\mathcal{I}$ are postive
Hermitian tensors, we then have

(88)
$\displaystyle\left\|g(\mathcal{C}^{(n)})\right\|_{(k)}\leq\int_{\Omega}\left\|g(\mathcal{D}_{\tau}+\delta_{n}\mathcal{I})\right\|_{(k)}d\nu(\tau).$

If $g(0^{+})<\infty$, Eq. (70) is obtained from Eq. (88) by taking
$n\rightarrow\infty$. On the other hand, if $g(0^{+})=\infty$, we can apply
the argument similar to the portion about $f(0^{+})=\infty$ in the proof for
Eq. (68) $\Longrightarrow$ Eq. (69) to get $a,b>0$ such that

(89) $\displaystyle
a\leq\left\|g(\mathcal{D}_{\tau}+\delta_{n}\mathcal{I})\right\|_{\rho}\leq\left\|g(\mathcal{D}_{\tau})\right\|_{\rho}+b,$

for all $\tau\in\Omega$ and $n\geq n_{0}$. Since the case that
$\int_{\Omega}\left\|g(\mathcal{D}_{\tau})\right\|_{(k)}d\nu(\tau)=\infty$
will have Eq. (70), we only consider the case that
$\int_{\Omega}\left\|g(\mathcal{D}_{\tau})\right\|_{(k)}d\nu(\tau)<\infty$.
Then, we have Eq. (70) from Eqs. (88), (89) and Lebesgue’s dominated
convergence theorem.

Eq. (68) $\Longleftarrow$ Eq. (70)

The weak majorization relation

(90)
$\displaystyle\sum\limits_{i=1}^{k}\log\lambda_{i}(\mathcal{C})\leq\sum\limits_{i=1}^{k}\int_{\Omega}\log\lambda_{i}(\mathcal{D}_{\tau})d\nu(\tau)$

is true from the implication from Eq. (45) to Eq. (43) in Theorem 3.3. We have
to show that this relation becomes identity for $k=r$. If we apply
$\left\|\cdot\right\|_{\rho}=\left\|\cdot\right\|_{1}$ and $g(x)=x^{-p}$ for
any $p>0$ in Eq. (70), we have

(91)
$\displaystyle\frac{1}{p}\log\left(\frac{\left\|\mathcal{C}^{-p}\right\|_{1}}{r}\right)\leq\frac{1}{p}\log\int_{\Omega}\frac{\left\|\mathcal{D}_{\tau}^{-p}\right\|_{1}}{r}d\nu(\tau).$

Then, we will get

(92) $\displaystyle\frac{-\log\det\nolimits_{H}(\mathcal{C})}{r}$
$\displaystyle=$ $\displaystyle\lim\limits_{p\rightarrow
0}\frac{1}{p}\log\left(\frac{\left\|\mathcal{C}^{-p}\right\|_{1}}{r}\right)$
$\displaystyle\leq$ $\displaystyle\lim\limits_{p\rightarrow
0}\frac{1}{p}\log\left(\int_{\Omega}\frac{\left\|\mathcal{D}_{\tau}^{-p}\right\|_{1}}{r}d\nu(\tau)\right)=_{1}\frac{-\int_{\Omega}\log\det\nolimits_{H}(\mathcal{D}_{\tau})d\nu(\tau)}{r},$

which will proves the identity for Eq. (90) when $k=r$. The equality in
$=_{1}$ will be proved by the following Lemma 3.5. $\hfill\Box$

######  Lemma 3.5.

Let $\mathcal{D}_{\tau}$ be nonnegative Hermitian tensors with
$\int_{\Omega}\left\|\mathcal{D}_{\tau}^{-p}\right\|_{1}d\nu(\tau)<\infty$ for
any $p>0$, then we have

(93) $\displaystyle\lim\limits_{p\rightarrow
0}\left(\frac{1}{p}\log\int_{\Omega}\frac{\left\|\mathcal{D}_{\tau}^{-p}\right\|_{1}}{r}d\nu(\tau)\right)$
$\displaystyle=$
$\displaystyle-\frac{\int_{\Omega}\log\det\nolimits_{H}(\mathcal{D}_{\tau})d\nu(\tau)}{r}$

Proof: Because
$\int_{\Omega}\left\|\mathcal{D}_{\tau}^{-p}\right\|_{\rho}d\nu(\tau)<\infty$,
we have that $\mathcal{D}_{\tau}$ are positive Hermitian tensors for $\tau$
almost everywhere in $\Omega$. Then, we have

(94) $\displaystyle\lim\limits_{p\rightarrow
0}\left(\frac{1}{p}\log\int_{\Omega}\frac{\left\|\mathcal{D}_{\tau}^{-p}\right\|_{1}}{r}d\nu(\tau)\right)$
$\displaystyle=_{1}$ $\displaystyle\lim\limits_{p\rightarrow
0}\frac{\int_{\Omega}\frac{-\sum\limits_{i=1}^{r}\log\lambda_{i}(\mathcal{D}_{\tau})}{r}d\nu(\tau)}{\int_{\Omega}\frac{\left\|\mathcal{D}_{\tau}^{-p}\right\|_{1}}{r}d\nu(\tau)}$
$\displaystyle=$
$\displaystyle\frac{-1}{r}\int_{\Omega}\sum\limits_{i=1}^{r}\log\lambda_{i}(\mathcal{D}_{\tau})d\nu(\tau)$
$\displaystyle=_{2}$
$\displaystyle\frac{-1}{r}\int_{\Omega}\log\det\nolimits_{H}(\mathcal{D}_{\tau})d\nu(\tau),$

where $=_{1}$ is from L’Hopital’s rule, and $=_{2}$ is obtained from
$\det\nolimits_{H}$ definition. $\hfill\Box$

###  3.3 Multivaraite Tensor Norm Inequalities

In this section, we will apply derived majorization inequalities for tensors
to multivaraite tensor norm inequalities which will be used to derive tensor
expander bounds. We will begin to present a Lie-Trotter product formula for
tensors.

######  Lemma 3.6.

Let $m\in\mathbb{N}$ and $(\mathcal{L}_{k})_{k=1}^{m}$ be a finite sequence of
bounded tensors with dimensions
$\mathcal{L}_{k}\in\mathbb{C}^{I_{1}\times\cdots\times I_{M}\times
I_{1}\times\cdots\times I_{M}}$, then we have

(95)
$\displaystyle\lim_{n\rightarrow\infty}\left(\prod_{k=1}^{m}\exp(\frac{\mathcal{L}_{k}}{n})\right)^{n}$
$\displaystyle=$ $\displaystyle\exp\left(\sum_{k=1}^{m}\mathcal{L}_{k}\right)$

Proof:

We will prove the case for $m=2$, and the general value of $m$ can be obtained
by mathematical induction. Let $\mathcal{L}_{1},\mathcal{L}_{2}$ be bounded
tensors act on some Hilbert space. Define
$\mathcal{C}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\exp((\mathcal{L}_{1}+\mathcal{L}_{2})/n)$, and
$\mathcal{D}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\exp(\mathcal{L}_{1}/n)\star_{M}\exp(\mathcal{L}_{2}/n)$. Note we
have following estimates for the norm of tensors $\mathcal{C},\mathcal{D}$:

(96)
$\displaystyle\left\|\mathcal{C}\right\|,\left\|\mathcal{D}\right\|\leq\exp\left(\frac{\left\|\mathcal{L}_{1}\right\|+\left\|\mathcal{L}_{2}\right\|}{n}\right)=\left[\exp\left(\left\|\mathcal{L}_{1}\right\|+\left\|\mathcal{L}_{2}\right\|\right)\right]^{1/n}.$

From the Cauchy-Product formula, the tensor $\mathcal{D}$ can be expressed as:

(97) $\displaystyle\mathcal{D}$ $\displaystyle=$
$\displaystyle\exp(\mathcal{L}_{1}/n)\star_{M}\exp(\mathcal{L}_{2}/n)=\sum_{i=0}^{\infty}\frac{(\mathcal{L}_{1}/n)^{i}}{i!}\star_{M}\sum_{j=0}^{\infty}\frac{(\mathcal{L}_{2}/n)^{j}}{j!}$
$\displaystyle=$
$\displaystyle\sum_{l=0}^{\infty}n^{-l}\sum_{i=0}^{l}\frac{\mathcal{L}_{1}^{i}}{i!}\star_{M}\frac{\mathcal{L}_{2}^{l-i}}{(l-i)!},$

then we can bound the norm of $\mathcal{C}-\mathcal{D}$ as

(98) $\displaystyle\left\|\mathcal{C}-\mathcal{D}\right\|$ $\displaystyle=$
$\displaystyle\left\|\sum_{i=0}^{\infty}\frac{\left([\mathcal{L}_{1}+\mathcal{L}_{2}]/n\right)^{i}}{i!}-\sum_{l=0}^{\infty}n^{-l}\sum_{i=0}^{l}\frac{\mathcal{L}_{1}^{i}}{i!}\star_{M}\frac{\mathcal{L}_{2}^{l-i}}{(l-i)!}\right\|$
$\displaystyle=$
$\displaystyle\left\|\sum_{i=2}^{\infty}k^{-i}\frac{\left([\mathcal{L}_{1}+\mathcal{L}_{2}]\right)^{i}}{i!}-\sum_{m=l}^{\infty}n^{-l}\sum_{i=0}^{l}\frac{\mathcal{L}_{1}^{i}}{i!}\star_{M}\frac{\mathcal{L}_{2}^{l-i}}{(l-i)!}\right\|$
$\displaystyle\leq$
$\displaystyle\frac{1}{k^{2}}\left[\exp(\left\|\mathcal{L}_{1}\right\|+\left\|\mathcal{L}_{2}\right\|)+\sum_{l=2}^{\infty}n^{-l}\sum_{i=0}^{l}\frac{\left\|\mathcal{L}_{1}\right\|^{i}}{i!}\cdot\frac{\left\|\mathcal{L}_{2}\right\|^{l-i}}{(l-i)!}\right]$
$\displaystyle=$
$\displaystyle\frac{1}{n^{2}}\left[\exp\left(\left\|\mathcal{L}_{1}\right\|+\left\|\mathcal{L}_{2}\right\|\right)+\sum_{l=2}^{\infty}n^{-l}\frac{(\left\|\mathcal{L}_{1}\right\|+\left\|\mathcal{L}_{2}\right\|)^{l}}{l!}\right]$
$\displaystyle\leq$
$\displaystyle\frac{2\exp\left(\left\|\mathcal{L}_{1}\right\|+\left\|\mathcal{L}_{2}\right\|\right)}{n^{2}}.$

For the difference between the higher power of $\mathcal{C}$ and
$\mathcal{D}$, we can bound them as

(99) $\displaystyle\left\|\mathcal{C}^{n}-\mathcal{D}^{n}\right\|$
$\displaystyle=$
$\displaystyle\left\|\sum_{l=0}^{n-1}\mathcal{C}^{m}(\mathcal{C}-\mathcal{D})\mathcal{C}^{n-l-1}\right\|$
$\displaystyle\leq_{1}$
$\displaystyle\exp(\left\|\mathcal{L}_{1}\right\|+\left\|\mathcal{L}_{2}\right\|)\cdot
n\cdot\left\|\mathcal{L}_{1}-\mathcal{L}_{2}\right\|,$

where the inequality $\leq_{1}$ uses the following fact

(100)
$\displaystyle\left\|\mathcal{C}\right\|^{l}\left\|\mathcal{D}\right\|^{n-l-1}\leq\exp\left(\left\|\mathcal{L}_{1}\right\|+\left\|\mathcal{L}_{2}\right\|\right)^{\frac{n-1}{n}}\leq\exp\left(\left\|\mathcal{L}_{1}\right\|+\left\|\mathcal{L}_{2}\right\|\right),$

based on Eq. (96). By combining with Eq. (98), we have the following bound

(101) $\displaystyle\left\|\mathcal{C}^{n}-\mathcal{D}^{n}\right\|$
$\displaystyle\leq$
$\displaystyle\frac{2\exp\left(2\left\|\mathcal{L}_{1}\right\|+2\left\|\mathcal{L}_{2}\right\|\right)}{n}.$

Then this lemma is proved when $n$ goes to infity. $\hfill\Box$

######  Theorem 3.7.

Let $\mathcal{C}_{i}\in\mathbb{C}^{I_{1}\times\cdots\times I_{N}\times
I_{1}\times\cdots\times I_{N}}$ be positive Hermitian tensors for $1\leq i\leq
n$ with Hermitian rank $r$, $\left\|\cdot\right\|_{(k)}$ be Ky Fan $k$-norm.
For any continous function $f:(0,\infty)\rightarrow[0,\infty)$ such that
$x\rightarrow\log f(e^{x})$ is convex on $\mathbb{R}$, we have

(102)
$\displaystyle\left\|f\left(\exp\left(\sum\limits_{i=1}^{n}\log\mathcal{C}_{i}\right)\right)\right\|_{(k)}$
$\displaystyle\leq$
$\displaystyle\exp\int_{-\infty}^{\infty}\log\left\|f\left(\left|\prod\limits_{i=1}^{n}\mathcal{C}_{i}^{1+\iota
t}\right|\right)\right\|_{(k)}\beta_{0}(t)dt,$

where $\beta_{0}(t)=\frac{\pi}{2(\cosh(\pi t)+1)}$.

For any continous function $g(0,\infty)\rightarrow[0,\infty)$ such that
$x\rightarrow g(e^{x})$ is convex on $\mathbb{R}$, we have

(103)
$\displaystyle\left\|g\left(\exp\left(\sum\limits_{i=1}^{n}\log\mathcal{C}_{i}\right)\right)\right\|_{(k)}$
$\displaystyle\leq$
$\displaystyle\int_{-\infty}^{\infty}\left\|g\left(\left|\prod\limits_{i=1}^{n}\mathcal{C}_{i}^{1+\iota
t}\right|\right)\right\|_{(k)}\beta_{0}(t)dt.$

Proof: From Hirschman interpolation theorem [22] and $\theta\in[0,1]$ and
setting $\sqrt{-1}$ as $\iota$, we have

(104)
$\displaystyle\log\left|h(\theta)\right|\leq\int_{-\infty}^{\infty}\log\left|h(\iota
t)\right|^{1-\theta}\beta_{1-\theta}(t)dt+\int_{-\infty}^{\infty}\log\left|h(1+\iota
t)\right|^{\theta}\beta_{\theta}(t)dt,$

where $h(z)$ be uniformly bounded on $S\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\\{z\in\mathbb{C}:0\leq\Re(z)\leq 1\\}$ and holomorphic on $S$. The
term $\beta_{\theta}(t)$ is defined as :

(105) $\displaystyle\beta_{\theta}(t)\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\frac{\sin(\pi\theta)}{2\theta(\cos(\pi t)+\cos(\pi\theta))}.$

Let $H(z)$ be a uniformly bounded holomorphic function with values in
$\mathbb{C}^{I_{1}\times\cdots\times I_{N}\times I_{1}\times\cdots\times
I_{N}}$. Fix some $\theta\in[0,1]$ and let
$\mathcal{U},\mathcal{V}\in\mathbb{C}^{I_{1}\times\cdots\times I_{N}\times 1}$
be normalized tensors such that
$\langle\mathcal{U},\mathcal{H}(\theta)\star_{N}\mathcal{V}\rangle=\left\|H(\theta)\right\|$.
If we define $h(z)$ as $h(z)\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\langle\mathcal{U},\mathcal{H}(z)\star_{N}\mathcal{V}\rangle$, we
have following bound: $\left|h(z)\right|\leq\left\|H(z)\right\|$ for all $z\in
S$. From Hirschman interpolation theorem, we then have following interpolation
theorem for tensor-valued function:

(106)
$\displaystyle\log\left\|H(\theta)\right\|\leq\int_{-\infty}^{\infty}\log\left\|H(\iota
t)\right\|^{1-\theta}\beta_{1-\theta}(t)dt+\int_{-\infty}^{\infty}\log\left\|H(1+\iota
t)\right\|^{\theta}\beta_{\theta}(t)dt.$

Let $H(z)=\prod\limits_{i=1}^{n}\mathcal{C}^{z}_{i}$. Then the first term in
the R.H.S. of Eq. (106) is zero since $H(\iota t)$ is a product of unitary
tensors. Then we have

(107)
$\displaystyle\log\left\|\left|\prod\limits_{i=1}^{n}\mathcal{C}_{i}^{\theta}\right|^{\frac{1}{\theta}}\right\|\leq\int_{-\infty}^{\infty}\log\left\|\prod\limits_{i=1}^{n}\mathcal{C}_{i}^{1+\iota
t}\right\|\beta_{\theta}(t)dt.$

From Lemma 2.7, we have following relations:

(108)
$\displaystyle\left|\prod\limits_{i=1}^{n}\left(\wedge^{k}\mathcal{C}_{i}\right)^{\theta}\right|^{\frac{1}{\theta}}=\wedge^{k}\left|\prod\limits_{i=1}^{n}\mathcal{C}^{\theta}_{i}\right|^{\frac{1}{\theta}},$

and

(109)
$\displaystyle\left|\prod\limits_{i=1}^{n}\left(\wedge^{k}\mathcal{C}_{i}\right)^{1+\iota
t}\right|=\wedge^{k}\left|\prod\limits_{i=1}^{n}\mathcal{C}^{1+\iota
t}_{i}\right|.$

If Eq. (107) is applied to $\wedge^{k}\mathcal{C}_{i}$ for $1\leq k\leq r$, we
have following log-majorization relation from Eqs. (108) and (109):

(110)
$\displaystyle\log\vec{\lambda}\left(\left|\prod\limits_{i=1}^{n}\mathcal{C}_{i}^{\theta}\right|^{\frac{1}{\theta}}\right)\prec\int_{-\infty}^{\infty}\log\vec{\lambda}\left|\prod\limits_{i=1}^{n}\mathcal{C}_{i}^{1+\iota
t}\right|^{\frac{1}{\theta}}\beta_{\theta}(t)dt.$

Moreover, we have the equality condition in Eq. (110) for $k=r$ due to
following identies:

(111)
$\displaystyle\det\nolimits_{H}\left|\prod\limits_{i=1}^{n}\mathcal{C}_{i}^{\theta}\right|^{\frac{1}{\theta}}=\det\nolimits_{H}\left|\prod\limits_{i=1}^{n}\mathcal{C}_{i}^{1+\iota
t}\right|=\prod\limits_{i=1}^{n}\det\nolimits_{H}\mathcal{C}_{i}.$

At this stage, we are ready to apply Theorem 3.4 for the log-majorization
provided by Eq. (110) to get following facts:

(112)
$\displaystyle\left\|f\left(\left|\prod\limits_{i=1}^{n}\mathcal{C}_{i}^{\theta}\right|^{\frac{1}{\theta}}\right)\right\|_{(k)}$
$\displaystyle\leq$
$\displaystyle\exp\int_{-\infty}^{\infty}\log\left\|f\left(\left|\prod\limits_{i=1}^{n}\mathcal{C}_{i}^{1+\iota
t}\right|\right)\right\|_{(k)}\beta_{\theta}(t)dt,$

and

(113)
$\displaystyle\left\|g\left(\left|\prod\limits_{i=1}^{n}\mathcal{C}_{i}^{\theta}\right|^{\frac{1}{\theta}}\right)\right\|_{(k)}$
$\displaystyle\leq$
$\displaystyle\int_{-\infty}^{\infty}\left\|g\left(\left|\prod\limits_{i=1}^{n}\mathcal{C}_{i}^{1+\iota
t}\right|\right)\right\|_{(k)}\beta_{\theta}(t)dt.$

From Lie product formula for tensors given by Lemma 3.6, we have

(114)
$\displaystyle\left|\prod\limits_{i=1}^{n}\mathcal{C}_{i}^{\theta}\right|^{\frac{1}{\theta}}\rightarrow\exp\left(\sum\limits_{i=1}^{n}\log\mathcal{C}_{i}\right).$

By setting $\theta\rightarrow 0$ in Eqs. (112), (113) and using Lie product
formula given by Eq. (114), we will get Eqs. (102) and (103). $\hfill\Box$

##  4 Tensor Expander Chernoff Bounds Derivation by Majorization

In this section, we will begin with the derivation for the expectation bound
of Ky Fan $k$-norm for the product of positive Hermitian tensors in Section
4.1. This bound will play a key role in the next Section 4.2 by establishing
tensor expander chernoff bounds.

###  4.1 Expectation Estimation for Product of Tensors

The main purpose of this section is to bound the expectation of Ky Fan
$k$-norm for the product of positive Hermitian tensors. We extend scalar
valued expander Chernoff bound proof in [10] and matrix valued expander
Chernoff bound proof in [8] to context of tensors and remove the restriction
that the summation of all mapped tensors should be zero tensor, i.e.,
$\sum\limits_{v\in\mathfrak{V}}\mathrm{g}(v)=\mathcal{O}$.

Let $\mathbf{A}$ be the normalized adjacency matrix of the underlying graph
$\mathfrak{G}$ and let
$\tilde{\mathbf{A}}=\mathbf{A}\otimes\mathcal{I}_{(\mathbb{I}_{1}^{M})^{2}}$,
where the identity tensor $\mathcal{I}_{(\mathbb{I}_{1}^{M})^{2}}$ has
dimensions as $I^{2}_{1}\times\cdots\times I^{2}_{M}\times
I^{2}_{1}\times\cdots\times I^{2}_{M}$. We use
$\mathcal{F}\in\mathbb{C}^{\left(n\times I^{2}_{1}\times\cdots\times
I^{2}_{M}\right)\times\left(n\times I^{2}_{1}\times\cdots\times
I^{2}_{M}\right)}$ to represent block diagonal tensor valued matrix where the
$v$-th diagonal block is the tensor

(115) $\displaystyle\mathcal{T}_{v}=\exp\left(\frac{t\mathrm{g}(v)(a+\iota
b)}{2}\right)\otimes\exp\left(\frac{t\mathrm{g}(v)(a-\iota b)}{2}\right).$

The tensor $\mathcal{F}$ can also be expressed as

(120) $\displaystyle\mathcal{F}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cccc}\mathcal{T}_{v_{1}}&\mathcal{O}&\cdots&\mathcal{O}\\\
\mathcal{O}&\mathcal{T}_{v_{2}}&\cdots&\mathcal{O}\\\
\vdots&\vdots&\ddots&\vdots\\\
\mathcal{O}&\mathcal{O}&\cdots&\mathcal{T}_{v_{n}}\\\ \end{array}\right].$

Then the tensor
$\left(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\right)^{\kappa}$ is a block
tensor valued matrix whose $(u,v)$-block is a tensor with dimensions as
$I^{2}_{1}\times\cdots\times I^{2}_{M}\times I^{2}_{1}\times\cdots\times
I^{2}_{M}$ expressed as :

(121)
$\displaystyle\sum\limits_{v_{1},\cdots,v_{\kappa-1}\in\mathfrak{V}}\mathbf{A}_{u,v_{1}}\left(\prod\limits_{j=1}^{\kappa-2}\mathbf{A}_{v_{j},v_{j+1}}\right)\mathbf{A}_{v_{\kappa-1},v}\left(\mathcal{T}_{u}\star_{2M}\mathcal{T}_{v_{1}}\star_{2M}\cdots\star_{2M}\mathcal{T}_{v_{\kappa-1}}\right)$

Let
$\mathbf{u}_{0}\in\mathbb{C}^{n\times\mathbb{I}^{2}_{1}\times\cdots\times\mathbb{I}^{2}_{M}}$
be the tensor obtained by
$\frac{\mathbf{1}}{\sqrt{n}}\otimes\mbox{{col}}(\mathcal{I}_{\mathbb{I}_{1}^{M}})$,
where $\mathbf{1}$ is the all ones vector with size $n$ and
$\mbox{{col}}(\mathcal{I}_{\mathbb{I}_{1}^{M}})\in\mathbb{C}^{I^{2}_{1}\times\cdots\times
I^{2}_{M}\times 1}$ is the column tensor of the identity tensor
$\mathcal{I}_{\mathbb{I}_{1}^{M}}\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times I_{1}\times\cdots\times I_{M}}$. By applying the following
relation:

(122)
$\displaystyle\bigl{<}\mbox{{col}}(\mathcal{I}_{\mathbb{I}_{1}^{M}}),\mathcal{C}\otimes\mathcal{B}\star_{M}\mbox{{col}}(\mathcal{I}_{\mathbb{I}_{1}^{M}})\bigr{>}=\mathrm{Tr}\left(\mathcal{C}\star_{M}\mathcal{B}^{T}\right),$

where $\mathcal{C},\mathcal{B}\in\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times I_{1}\times\cdots\times I_{M}}$; we will have following
expectation of $\kappa$ steps transition of Hermitian tensors from the vertex
$v_{1}$ to the vertex $v_{\kappa}$,

$\displaystyle\mathbb{E}\left[\mathrm{Tr}\left(\prod\limits_{i=1}^{\kappa}\exp\left(\frac{t\mathrm{g}(v_{i})(a+\iota
b)}{2}\right)\star_{M}\prod\limits_{i=\kappa}^{1}\exp\left(\frac{t\mathrm{g}(v_{i})(a-\iota
b)}{2}\right)\right)\right]=$ (123)
$\displaystyle=\mathbb{E}\left[\biggl{<}\mbox{{col}}(\mathcal{I}_{\mathbb{I}_{1}^{M}}),\prod_{i=1}^{\kappa}\mathcal{T}_{v_{i}}\star_{M}\mbox{{col}}(\mathcal{I}_{\mathbb{I}_{1}^{M}})\biggr{>}\right]=\biggl{<}\mathbf{u}_{0},\left(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\right)^{\kappa}\star_{M+1}\mathbf{u}_{0}\biggr{>}.$

If we define
$\left(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\right)^{\kappa}\star_{M+1}\mathbf{u}_{0}$
as $\mathbf{u}_{\kappa}$, the goal of this section is to estimate
$\bigl{<}\mathbf{u}_{0},\mathbf{u}_{\kappa}\bigr{>}$.

The trick is to separate the space of $\mathbf{u}$ as the subspace spanned by
the $(\mathbb{I}_{1}^{M})^{2}$ tensors $\mathbf{1}\otimes e_{i}$ denoted by
$\mathbf{u}^{\parallel}$, where $1\leq i\leq(\mathbb{I}_{1}^{M})^{2}$ and
$e_{i}\in\mathbb{C}^{I^{2}_{1}\times\cdots\times I^{2}_{M}\times 1}$ is the
column tensor of size $(\mathbb{I}_{1}^{M})^{2}$ with 1 in position $i$ and 0
elsewhere, and its orthogonal complement space, denoted by
$\mathbf{u}^{\perp}$. Following lemma is required to bound how the tensor norm
is changed in terms of aforementioned subspace and its orthogonal space after
acting by the tensor $\mathcal{F}\star_{2M+1}\tilde{\mathbf{A}}$.

######  Lemma 4.1.

Given paramters $\lambda\in(0,1)$, $a\geq 0$, $r>0$, and $t>0$. Let
$\mathfrak{G}=(\mathfrak{V},\mathfrak{E})$ be a regular $\lambda$-expander
graph on the vetices set $\mathfrak{V}$ and
$\left\|\mathrm{g}(v_{i})\right\|\leq r$ for all $v_{i}\in\mathfrak{V}$. Each
vertex $v\in\mathfrak{V}$ will be assigned a tensor $\acute{\mathcal{T}}_{v}$,
where $\acute{\mathcal{T}}_{v}\stackrel{{\scriptstyle\text{\tiny
def}}}{{=}}\frac{\mathrm{g}(v)(a+\iota
b)}{2}\otimes\mathcal{I}_{\mathbb{I}_{1}^{M}}+\mathcal{I}_{\mathbb{I}_{1}^{M}}\otimes\frac{\mathrm{g}(v)(a-\iota
b)}{2}\in\mathbb{C}^{I^{2}_{1}\times\cdots\times I^{2}_{M}\times
I^{2}_{1}\times\cdots\times I^{2}_{M}}$. Let
$\mathcal{F}\in\mathbb{C}^{\left(n\times I^{2}_{1}\times\cdots\times
I^{2}_{M}\right)\times\left(n\times I^{2}_{1}\times\cdots\times
I^{2}_{M}\right)}$ to represent block diagonal tensor valued matrix where the
$v$-th diagonal block is the tensor
$\exp(t\acute{\mathcal{T}}_{v})=\mathcal{T}_{v}$. For any tensor
$\mathbf{u}\in\mathbb{C}^{n\times\mathbb{I}^{2}_{1}\times\cdots\times\mathbb{I}^{2}_{M}}$,
we have

  1. 1.

$\left\|\left(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\parallel}\right)^{\parallel}\right\|\leq\gamma_{1}\left\|\mathbf{u}^{\parallel}\right\|$,
where $\gamma_{1}=\exp(tr\sqrt{a^{2}+b^{2}})$;

  2. 2.

$\left\|\left(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\perp}\right)^{\parallel}\right\|\leq\gamma_{2}\left\|\mathbf{u}^{\perp}\right\|$,
where $\gamma_{2}=\lambda(\exp(tr\sqrt{a^{2}+b^{2}})-1)$;

  3. 3.

$\left\|\left(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\parallel}\right)^{\perp}\right\|\leq\gamma_{3}\left\|\mathbf{u}^{\parallel}\right\|$,
where $\gamma_{3}=\exp(tr\sqrt{a^{2}+b^{2}})-1$;

  4. 4.

$\left\|\left(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\perp}\right)^{\perp}\right\|\leq\gamma_{4}\left\|\mathbf{u}^{\perp}\right\|$,
where $\gamma_{4}=\lambda\exp(tr\sqrt{a^{2}+b^{2}})$.

Proof:

For Part 1, let $\mathbf{1}\in\mathbb{C}^{n}$ be all ones vector, and let
$\mathbf{u}^{\parallel}=\mathbf{1}\otimes\mathbf{v}$ for some
$\mathbf{v}\in\mathbb{C}^{(\mathbb{I}_{1}^{M})^{2}}$. Then, we have

(124)
$\displaystyle\left(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\star_{M}\mathbf{u}^{\parallel}\right)^{\parallel}=\left(\mathcal{F}\star_{M}\mathbf{u}^{\parallel}\right)^{\parallel}=\mathbf{1}\otimes\left(\frac{1}{n}\sum\limits_{v\in\mathfrak{V}}\exp(t\acute{\mathcal{T}}_{v})\star_{M}\mathbf{v}\right)$

and we can bound
$\left(\frac{1}{n}\sum\limits_{v\in\mathfrak{V}}\exp(t\acute{\mathcal{T}}_{v})\star_{M}\mathbf{v}\right)$
further as

(125)
$\displaystyle\left\|\frac{1}{n}\sum\limits_{v\in\mathfrak{V}}\exp(t\acute{\mathcal{T}}_{v})\right\|$
$\displaystyle=$
$\displaystyle\left\|\frac{1}{n}\sum\limits_{v\in\mathfrak{V}}\sum\limits_{i=0}^{\infty}\frac{t^{i}\acute{\mathcal{T}}^{i}_{v}}{i!}\right\|$
$\displaystyle=$
$\displaystyle\left\|\mathcal{I}+\frac{1}{n}\sum\limits_{v\in\mathfrak{V}}\sum\limits_{i=1}^{\infty}\frac{t^{i}\acute{\mathcal{T}}^{i}_{v}}{i!}\right\|$
$\displaystyle\leq$ $\displaystyle
1+\frac{1}{n}\sum\limits_{v\in\mathfrak{V}}\sum\limits_{i=1}^{\infty}\frac{t^{i}\left\|\acute{\mathcal{T}}_{v}\right\|^{i}}{i!}$
$\displaystyle\leq$ $\displaystyle
1+\sum\limits_{i=1}^{\infty}\frac{(tr\sqrt{a^{2}+b^{2}})^{i}}{i!}=\exp(tr\sqrt{a^{2}+b^{2}}),$

where the last inequality is due to the fact that
$\left\|\frac{t\mathrm{g}(v)(a+\iota
b)}{2}\otimes\mathcal{I}_{\mathbb{I}_{1}^{M}}+\mathcal{I}_{\mathbb{I}_{1}^{M}}\otimes\frac{t\mathrm{g}(v)(a-\iota
b)}{2}\right\|\leq 2tr\times\sqrt{\frac{a^{2}+b^{2}}{4}}$.

Then Part 1. of this lemma is established due to

(126)
$\displaystyle\left\|\left(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\parallel}\right)^{\parallel}\right\|$
$\displaystyle=$
$\displaystyle\sqrt{n}\left\|\frac{1}{n}\sum\limits_{v\in\mathfrak{V}}\exp(t\acute{\mathcal{T}}_{v})\mathbf{v}\right\|$
$\displaystyle\leq$
$\displaystyle\sqrt{n}\left\|\mathbf{v}\right\|\exp(tr\sqrt{a^{2}+b^{2}})=\exp(tr\sqrt{a^{2}+b^{2}})\left\|\mathbf{u}^{\parallel}\right\|.$

For Part 2, since
$(\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\perp})^{\parallel}=0$, we have

(127)
$\displaystyle\left\|\left(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\perp}\right)^{\parallel}\right\|$
$\displaystyle=$
$\displaystyle\left\|((\mathcal{F}-\mathcal{I})\star_{M+1}\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\perp})^{\parallel}\right\|$
$\displaystyle\leq$
$\displaystyle\left\|(\mathcal{F}-\mathcal{I})\star_{M+1}\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\perp}\right\|$
$\displaystyle\leq$
$\displaystyle\max\limits_{v\in\mathfrak{V}}\left\|\exp(t\acute{\mathcal{T}}_{v})-\mathcal{I}\right\|\cdot\left\|\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\perp}\right\|$
$\displaystyle\leq$
$\displaystyle\max\limits_{v\in\mathfrak{V}}\left\|\sum\limits_{i=1}^{\infty}\frac{t^{i}\acute{\mathcal{T}}^{i}_{v}}{i!}\right\|\cdot\left\|\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\perp}\right\|\leq(\exp(tr\sqrt{a^{2}+b^{2}})-1)\lambda\left\|\mathbf{u}^{\perp}\right\|,$

where the last inequality uses that the underlying graph $\mathfrak{G}$ is a
$\lambda$-expander graph, i.e.,
$\left\|\mathbf{A}\mathbf{x}\right\|\leq\lambda\cdot\left\|\mathbf{x}\right\|$.
Therefore, Part 2 is also valid.

For Part 3, because $(\mathbf{u}^{\parallel})^{\perp}=0$, we have
$(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\parallel})^{\perp}=(\mathcal{F}\star_{M+1}\mathbf{u}^{\parallel})^{\perp}=((\mathcal{F}-\mathcal{I})\star_{M+1}\mathbf{u}^{\parallel})^{\perp}$.
Then, we can upper bound as

(128)
$\displaystyle\left\|((\mathcal{F}-\mathcal{I})\star_{M+1}\mathbf{u}^{\parallel})^{\perp}\right\|$
$\displaystyle\leq$
$\displaystyle\left\|(\mathcal{F}-\mathcal{I})\star_{M+1}\mathbf{u}^{\parallel}\right\|$
$\displaystyle\leq$
$\displaystyle\left\|(\mathcal{F}-\mathcal{I}\right\|\cdot\left\|\mathbf{u}^{\parallel}\right\|$
$\displaystyle=$
$\displaystyle\max\limits_{v\in\mathfrak{V}}\left\|\exp(t\acute{\mathcal{T}}_{v})-\mathcal{I}\right\|\cdot\left\|\mathbf{u}^{\parallel}\right\|$
$\displaystyle\leq$
$\displaystyle\max\limits_{v\in\mathfrak{V}}\left\|\sum\limits_{i=1}^{\infty}\frac{t^{i}\acute{\mathcal{T}}^{i}_{v}}{i!}\right\|\cdot\left\|\mathbf{u}^{\parallel}\right\|\leq(\exp(tr\sqrt{a^{2}+b^{2}})-1)\left\|\mathbf{u}^{\parallel}\right\|,$

hence, Part 3 is also proved.

Finally, for Part 4, we have

(129)
$\displaystyle\left\|(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\perp})^{\perp}\right\|$
$\displaystyle\leq$
$\displaystyle\left\|\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\perp}\right\|$
$\displaystyle\leq$
$\displaystyle\left\|\mathcal{F}\right\|\cdot\left\|\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\perp}\right\|\leq\exp(tr\sqrt{a^{2}+b^{2}})\lambda\left\|\mathbf{u}^{\perp}\right\|,$

where we use $\left\|\mathcal{F}\right\|\leq\exp(tr\sqrt{a^{2}+b^{2}})$ (shown
at previous part) and the underlying graph $\mathfrak{G}$ is a
$\lambda$-expander graph. $\hfill\Box$

In the following, we will apply Lemma 4.1 to bound the following term provided
by Eq. (4.1)

(130)
$\displaystyle\biggl{<}\mathbf{u}_{0},\left(\mathbf{F}\star_{M+1}\tilde{\mathbf{A}}\right)^{\kappa}\star_{M+1}\mathbf{u}_{0}\biggr{>}$

This bound is formulated by the following Lemma 4.2

######  Lemma 4.2.

Let $\mathfrak{G}$ be a regular $\lambda$-expander graph on the vertex set
$\mathfrak{V}$, $g:\mathfrak{V}\rightarrow\mathbb{C}^{I_{1}\times\cdots\times
I_{M}\times I_{1}\times\cdots\times I_{M}}$, and let $v_{1},\cdots,v_{\kappa}$
be a stationary random walk on $\mathfrak{G}$. If $tr\sqrt{a^{2}+b^{2}}<1$ and
$\lambda(2\exp(tr\sqrt{a^{2}+b^{2}})-1)\leq 1$, we have:

$\displaystyle\mathbb{E}\left[\mathrm{Tr}\left(\prod\limits_{i=1}^{\kappa}\exp\left(\frac{t\mathrm{g}(v_{i})(a+\iota
b)}{2}\right)\star_{M}\prod\limits_{i=\kappa}^{1}\exp\left(\frac{t\mathrm{g}(v_{i})(a-\iota
b)}{2}\right)\right)\right]\leq$ (131)
$\displaystyle\mathbb{I}_{1}^{M}\exp\left[\kappa\left(2tr\sqrt{a^{2}+b^{2}}+\frac{8}{1-\lambda}+\frac{16tr\sqrt{a^{2}+b^{2}}}{1-\lambda}\right)\right].~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$

Proof: There are two phases for this proof. The first phase is to bound the
evolution of tensor norms $\left\|\mathbf{u}_{i}^{\perp}\right\|$ and
$\left\|\mathbf{u}_{i}^{\parallel}\right\|$, respectively. The second phase is
to bound $\gamma_{i}$ for $1\leq i\leq 4$ in Lemm 4.1. We begin with the
derivation for the bound $\left\|\mathbf{u}_{i}^{\perp}\right\|$, where
$\mathbf{u}_{i}$ is the output tensor after acting by the tensor
$\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}$ for $i$ times. It is

(132) $\displaystyle\left\|\mathbf{u}_{i}^{\perp}\right\|$ $\displaystyle=$
$\displaystyle\left\|(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}_{i-1})^{\perp}\right\|$
$\displaystyle\leq$
$\displaystyle\left\|(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\parallel}_{i-1})^{\perp}\right\|+\left\|(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\perp}_{i-1})^{\perp}\right\|$
$\displaystyle\leq_{1}$
$\displaystyle\gamma_{3}\left\|\mathbf{u}^{\parallel}_{i-1}\right\|+\gamma_{4}\left\|\mathbf{u}^{\perp}_{i-1}\right\|$
$\displaystyle\leq_{2}$
$\displaystyle(\gamma_{3}+\gamma_{3}\gamma_{4}+\gamma_{3}\gamma^{2}_{4}+\cdots)\max\limits_{j<i}\left\|\mathbf{u}_{j}^{\parallel}\right\|\leq\frac{\gamma_{3}}{1-\gamma_{4}}\max\limits_{j<i}\left\|\mathbf{u}_{j}^{\parallel}\right\|,$

where $\leq_{1}$ is obtained from Lemma 4.1, $\leq_{2}$ is obtained by
applying the inequality at $\leq_{1}$ repeatedly. The next task is to bound
$\left\|\mathbf{u}_{i}^{\parallel}\right\|$, we have

(133) $\displaystyle\left\|\mathbf{u}_{i}^{\parallel}\right\|$
$\displaystyle=$
$\displaystyle\left\|(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}_{i-1})^{\parallel}\right\|$
$\displaystyle\leq$
$\displaystyle\left\|(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\parallel}_{i-1})^{\parallel}\right\|+\left\|(\mathcal{F}\star_{M+1}\tilde{\mathbf{A}}\star_{M+1}\mathbf{u}^{\perp}_{i-1})^{\parallel}\right\|$
$\displaystyle\leq_{1}$
$\displaystyle\gamma_{1}\left\|\mathbf{u}^{\parallel}_{i-1}\right\|+\gamma_{2}\left\|\mathbf{u}^{\perp}_{i-1}\right\|$
$\displaystyle\leq_{2}$
$\displaystyle\left(\gamma_{1}+\frac{\gamma_{2}\gamma_{3}}{1-\gamma_{4}}\right)\max\limits_{j<i}\left\|\mathbf{u}_{j}^{\parallel}\right\|,$

where $\leq_{1}$ is obtained from Lemma 4.1, $\leq_{2}$ is obtained from Eq.
(132). From Eqs (4.1), (132) and (133), we have

$\displaystyle\mathbb{E}\left[\mathrm{Tr}\left(\prod\limits_{i=1}^{\kappa}\exp\left(\frac{t\mathrm{g}(v_{i})(a+\iota
b)}{2}\right)\star_{M}\prod\limits_{i=\kappa}^{1}\exp\left(\frac{t\mathrm{g}(v_{i})(a-\iota
b)}{2}\right)\right)\right]$
$\displaystyle=\langle\mathbf{u}_{0},\mathbf{u}_{\kappa}\rangle=\langle\mathbf{u}_{0},\mathbf{u}^{\parallel}_{\kappa}\rangle\leq\left\|\mathbf{z}_{0}\right\|\cdot\left\|\mathbf{z}^{\parallel}_{\kappa}\right\|=\sqrt{\mathbb{I}_{1}^{M}}\cdot\left\|\mathbf{z}^{\parallel}_{\kappa}\right\|~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
(134)
$\displaystyle\leq\sqrt{\mathbb{I}_{1}^{M}}\left(\gamma_{1}+\frac{\gamma_{2}\gamma_{3}}{1-\gamma_{4}}\right)^{\kappa}\cdot\left\|\mathbf{z}^{\parallel}_{0}\right\|\leq\mathbb{I}_{1}^{M}\left(\gamma_{1}+\frac{\gamma_{2}\gamma_{3}}{1-\gamma_{4}}\right)^{\kappa}.~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$

The second phase of this proof requires us to bound following four terms:
$\gamma_{i}$ for $1\leq i\leq 4$. Since $tr\sqrt{a^{2}+b^{2}}<1$, we can bound
$\gamma_{1}$ as following:

(135) $\displaystyle\gamma_{1}$ $\displaystyle=$
$\displaystyle\exp(tr\sqrt{a^{2}+b^{2}})\leq 1+2tr\sqrt{a^{2}+b^{2}};$ (136)
$\displaystyle\gamma_{2}$ $\displaystyle=$
$\displaystyle\lambda(\exp(tr\sqrt{a^{2}+b^{2}})-1)\leq 2\lambda
tr\sqrt{a^{2}+b^{2}};$ (137) $\displaystyle\gamma_{3}$ $\displaystyle=$
$\displaystyle\exp(tr\sqrt{a^{2}+b^{2}})-1\leq 2tr\sqrt{a^{2}+b^{2}};$

and the condition $\lambda(2\exp(tr\sqrt{a^{2}+b^{2}})-1)\leq 1$, we have

(138) $\displaystyle 1-\gamma_{4}$ $\displaystyle=$ $\displaystyle
1-\lambda\exp(tr\sqrt{a^{2}+b^{2}})\geq\frac{1-\lambda}{2}.$

By applying Eqs. (135), (136), (137) and (138) to the upper bound in Eq.
(4.1), we also have

(139)
$\displaystyle\mathbb{I}_{1}^{M}\left(\gamma_{1}+\frac{\gamma_{2}\gamma_{3}}{1-\gamma_{4}}\right)^{\kappa}$
$\displaystyle\leq$
$\displaystyle\mathbb{I}_{1}^{M}\left[1+2(tr\sqrt{a^{2}+b^{2}})+\frac{8\lambda
t^{2}r^{2}(a^{2}+b^{2})}{1-\lambda}\right]^{\kappa}$ $\displaystyle\leq$
$\displaystyle\mathbb{I}_{1}^{M}\left[\left(1+2tr\sqrt{a^{2}+b^{2}}\right)\left(1+\frac{8}{1-\lambda}\right)\right]^{\kappa}$
$\displaystyle\leq$
$\displaystyle\mathbb{I}_{1}^{M}\exp\left[\kappa\left(2tr\sqrt{a^{2}+b^{2}}+\frac{8}{1-\lambda}+\frac{16tr\sqrt{a^{2}+b^{2}}}{1-\lambda}\right)\right]$

This lemma is proved. $\hfill\Box$

###  4.2 Tensor Expander Chernoff Bounds

We begin with a lemma about a Ky Fan $k$-norm inequality for the sum of
tensors.

######  Lemma 4.3.

Let $\mathcal{C}_{i}\in\mathbb{C}^{I_{1}\times\cdots\times I_{N}\times
I_{1}\times\cdots\times I_{N}}$ with Hermitian rank $r$, then we have

(140)
$\displaystyle\left\|\left|\sum\limits_{i=1}^{m}\mathcal{C}_{i}\right|^{s}\right\|_{(k)}\leq
m^{s-1}\sum\limits_{i=1}^{m}\left\|\left|\mathcal{C}_{i}\right|^{s}\right\|_{(k)}$

where $s\geq 1$ and $k\in\\{1,2,\cdots,r\\}$.

Proof: Since we have

(141)
$\displaystyle\left\|\left|\sum\limits_{i=1}^{m}\mathcal{C}_{i}\right|^{s}\right\|_{(k)}=\sum\limits_{j=1}^{k}\lambda_{j}\left(\left|\sum\limits_{i=1}^{m}\mathcal{C}_{i}\right|^{s}\right)=\sum\limits_{j=1}^{k}\lambda^{s}_{j}\left(\left|\sum\limits_{i=1}^{m}\mathcal{C}_{i}\right|\right)=\sum\limits_{j=1}^{k}\sigma^{s}_{j}\left(\sum\limits_{i=1}^{m}\mathcal{C}_{i}\right).$

where we have orders for eigenvalues as
$\lambda_{1}\geq\lambda_{2}\geq\cdots$, and singular values as
$\sigma_{1}\geq\sigma_{2}\geq\cdots$.

From Theorem G.1.d. in [17] and Theorem 5.2 in [19], we have Ky Fan singular
value majorization inequalities:

(142)
$\displaystyle\sum\limits_{j=1}^{k}\sigma_{j}(\sum\limits_{i=1}^{m}\mathcal{C}_{i})\leq\sum\limits_{j=1}^{k}\left(\sum\limits_{i=1}^{m}\sigma_{j}(\mathcal{C}_{i})\right),$

where $k\in\\{1,2,\cdots,s\\}$. Then, we have

(143)
$\displaystyle\sum\limits_{j=1}^{k}\sigma^{s}_{j}(\sum\limits_{i=1}^{m}\mathcal{C}_{i})$
$\displaystyle\leq$
$\displaystyle\sum\limits_{j=1}^{k}\left(\sum\limits_{i=1}^{m}\sigma_{j}(\mathcal{C}_{i})\right)^{s}\leq
m^{s-1}\sum\limits_{j=1}^{k}\left(\sum\limits_{i=1}^{m}\sigma^{s}_{j}(\mathcal{C}_{i})\right)$
$\displaystyle=$ $\displaystyle
m^{s-1}\sum\limits_{j=1}^{k}\left(\sum\limits_{i=1}^{m}\sigma^{s}_{j}(\left|\mathcal{C}_{i}\right|)\right)=m^{s-1}\sum\limits_{j=1}^{k}\left(\sum\limits_{i=1}^{m}\sigma_{j}(\left|\mathcal{C}_{i}\right|^{s})\right)$
$\displaystyle=$ $\displaystyle
m^{s-1}\sum\limits_{i=1}^{m}\left\|\left|\mathcal{C}_{i}\right|^{s}\right\|_{(k)}$

$\hfill\Box$

We are ready to present our main theorem about the tensor expander bound for
Ky Fan $k$-norm.

######  Theorem 4.4.

Let $\mathfrak{G}=(\mathfrak{V},\mathfrak{E})$ be a regular undirected graph
whose transition matrix has second eigenvalue $\lambda$, and let
$g:\mathfrak{V}\rightarrow\in\mathbb{C}^{I_{1}\times\cdots\times I_{M}\times
I_{1}\times\cdots\times I_{M}}$ be a function. We assume following:

  1. 1.

For each $v\in\mathfrak{V}$, $g(v)$ is a Hermitian tensor;

  2. 2.

$\left\|g(v)\right\|\leq r$;

  3. 3.

A nonnegative coefficients polynomial raised by the power $s\geq 1$ as
$f:x\rightarrow(a_{0}+a_{1}x+a_{2}x^{2}+\cdots+a_{n}x^{n})^{s}$ satisfying
$f\left(\exp\left(t\sum\limits_{j=1}^{\kappa}g(v_{j})\right)\right)\succeq\exp\left(tf\left(\sum\limits_{j=1}^{\kappa}g(v_{j})\right)\right)$
almost surely;

  4. 4.

For $\tau\in[\infty,\infty]$, we have constants $C$ and $\sigma$ such that
$\beta_{0}(\tau)\leq\frac{C\exp(\frac{-\tau^{2}}{2\sigma^{2}})}{\sigma\sqrt{2\pi}}$.

Then, we have

$\displaystyle\mathrm{Pr}\left(\left\|f\left(\sum\limits_{j=1}^{\kappa}g(v_{j})\right)\right\|_{(k)}\geq\vartheta\right)\leq\min\limits_{t>0}\left[(n+1)^{(s-1)}e^{-\vartheta
t}\left(a_{0}k+C\left(k+\sqrt{\frac{\mathbb{I}_{1}^{M}-k}{k}}\right)\cdot\right.\right.~{}~{}~{}~{}~{}$
(144)
$\displaystyle\left.\left.\sum\limits_{l=1}^{n}a_{l}\exp(8\kappa\overline{\lambda}+2(\kappa+8\overline{\lambda})lsrt+2(\sigma(\kappa+8\overline{\lambda})lsr)^{2}t^{2})\right)\right],$

where $\overline{\lambda}=1-\lambda$.

Proof: Let $t>0$ be a paramter to be chosen later, then we have

(145)
$\displaystyle\mathrm{Pr}\left(\left\|f\left(\sum\limits_{j=1}^{\kappa}g(v_{j})\right)\right\|_{(k)}\geq\vartheta\right)$
$\displaystyle=$
$\displaystyle\mathrm{Pr}\left(\exp\left(\left\|tf\left(\sum\limits_{j=1}^{\kappa}g(v_{j})\right)\right\|_{(k)}\right)\geq\exp\left(\vartheta
t\right)\right)$ $\displaystyle=_{1}$
$\displaystyle\mathrm{Pr}\left(\left\|\exp\left(tf\left(\sum\limits_{j=1}^{\kappa}g(v_{j})\right)\right)\right\|_{(k)}\geq\exp\left(\vartheta
t\right)\right)$ $\displaystyle\leq_{2}$ $\displaystyle\exp\left(-\vartheta
t\right)\mathbb{E}\left(\left\|\exp\left(tf\left(\sum\limits_{j=1}^{\kappa}g(v_{j})\right)\right)\right\|_{(k)}\right)$
$\displaystyle\leq_{3}$ $\displaystyle\exp\left(-\vartheta
t\right)\mathbb{E}\left(\left\|f\left(\exp\left(t\sum\limits_{j=1}^{\kappa}g(v_{j})\right)\right)\right\|_{(k)}\right),$

where equality $=_{1}$ comes from spectral mapping theorem, inequality
$\leq_{2}$ is obtained from Markov inequality, and the last inequality
$\leq_{3}$ is based on our function $f$ assumption (third assumption).

From Eq. (103) in Theorem 3.7, we can further bound the expectation term in
Eq. (145) as

$\displaystyle\mathbb{E}\left(\left\|f\left(\exp\left(t\sum\limits_{j=1}^{\kappa}g(v_{j})\right)\right)\right\|_{(k)}\right)~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle\leq\mathbb{E}\left(\int\limits_{-\infty}^{\infty}\left\|f\left(\left|\prod\limits_{j=1}^{\kappa}\exp\left(tg(v_{j})(1+\iota\tau)\right)\right|\right)\right\|_{(k)}\beta_{0}(\tau)d\tau\right)~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle=_{1}\mathbb{E}\left(\int\limits_{-\infty}^{\infty}\left\|\left(\sum\limits_{l=0}^{n}a_{l}\left|\prod\limits_{j=1}^{\kappa}\exp\left(tg(v_{j})(1+\iota\tau)\right)\right|^{l}\right)^{s}\right\|_{(k)}\beta_{0}(\tau)d\tau\right)~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle\leq_{2}(n+1)^{(s-1)}\mathbb{E}\left(\int\limits_{-\infty}^{\infty}\sum\limits_{l=0}^{n}a_{l}\left\|\left(\left|\prod\limits_{j=1}^{\kappa}\exp\left(tg(v_{j})(1+\iota\tau)\right)\right|^{l}\right)^{s}\right\|_{(k)}\beta_{0}(\tau)d\tau\right)~{}~{}$
$\displaystyle=(n+1)^{(s-1)}\cdot~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
(146)
$\displaystyle\left(\int\limits_{-\infty}^{\infty}\sum\limits_{l=0}^{n}a_{l}\mathbb{E}\left(\left\|\left(\left|\prod\limits_{j=1}^{\kappa}\exp\left(tg(v_{j})(1+\iota\tau)\right)\right|^{l}\right)^{s}\right\|_{(k)}\right)\beta_{0}(\tau)d\tau\right)$

where equality $=_{1}$ comes from the function $f$ definition, inequality
$\leq_{2}$ is based on Lemma 4.3. Each summand for $l\geq 1$ in Eq. (4.2) can
further be bounded as

$\displaystyle\mathbb{E}\left(\left\|\left(\left|\prod\limits_{j=1}^{\kappa}\exp\left(tg(v_{j})(1+\iota\tau)\right)\right|^{l}\right)^{s}\right\|_{(k)}\right)=\mathbb{E}\left(\left\|\left|\prod\limits_{j=1}^{\kappa}\exp\left(tg(v_{j})(1+\iota\tau)\right)\right|^{ls}\right\|_{(k)}\right)$
$\displaystyle\leq_{1}\frac{k}{\mathbb{I}_{1}^{M}}\mathrm{Tr}\left(\left|\prod\limits_{j=1}^{\kappa}\exp\left(tg(v_{j})(1+\iota\tau)\right)\right|^{ls}\right)+~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle\sqrt{\frac{\mathbb{I}_{1}^{M}-k}{k\mathbb{I}_{1}^{M}}\mathrm{Tr}\left(\left|\prod\limits_{j=1}^{\kappa}\exp\left(tg(v_{j})(1+\iota\tau)\right)\right|^{2ls}\right)}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle\leq_{2}k\exp\left[\kappa\left(2lstr\sqrt{1+\tau^{2}}+\frac{8}{1-\lambda}+\frac{16tlsr\sqrt{1+\tau^{2}}}{1-\lambda}\right)\right]+~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle\left(\frac{\mathbb{I}_{1}^{M}-k}{k}\exp\left[\kappa\left(4lstr\sqrt{1+\tau^{2}}+\frac{8}{1-\lambda}+\frac{32lstr\sqrt{1+\tau^{2}}}{1-\lambda}\right)\right]\right)^{1/2}~{}~{}~{}~{}~{}~{}$
(147)
$\displaystyle\leq_{3}\left(k+\sqrt{\frac{\mathbb{I}_{1}^{M}-k}{k}}\right)\cdot\exp\left[\kappa\left(2lstr(1+\tau)+\frac{8}{1-\lambda}+\frac{16tlsr(1+\tau)}{1-\lambda}\right)\right]~{}~{}~{}~{}$

where $\leq_{1}$ comes from Theorem 5 in [18], and $\leq_{2}$ comes from Lemma
4.2, and the last inequality $\leq_{3}$ is obtaiend by bounding
$\sqrt{1+\tau^{2}}$ as $1+\tau$.

From Eqs. (145), (4.2), and (4.2), we have

$\displaystyle\mathrm{Pr}\left(\left\|f\left(\sum\limits_{j=1}^{\kappa}g(v_{j})\right)\right\|_{(k)}\geq\vartheta\right)\leq\min\limits_{t>0}\left[(n+1)^{(s-1)}e^{-\vartheta
t}\left(a_{0}k+\left(k+\sqrt{\frac{\mathbb{I}_{1}^{M}-k}{k}}\right)\cdot\right.\right.$
$\displaystyle\left.\left.\sum\limits_{l=1}^{n}a_{l}\int\limits_{\infty}^{\infty}\exp\left[\kappa\left(2lstr(1+\tau)+\frac{8}{1-\lambda}+\frac{16tlsr(1+\tau)}{1-\lambda}\right)\right]\beta_{0}(\tau)d\tau\right)\right]~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle\leq_{1}\min\limits_{t>0}\left[(n+1)^{(s-1)}e^{-\vartheta
t}\left(a_{0}k+\left(k+\sqrt{\frac{\mathbb{I}_{1}^{M}-k}{k}}\right)\cdot\right.\right.~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$\displaystyle\left.\left.\sum\limits_{l=1}^{n}a_{l}\int\limits_{\infty}^{\infty}\exp\left[\kappa\left(2lstr(1+\tau)+\frac{8}{1-\lambda}+\frac{16tlsr(1+\tau)}{1-\lambda}\right)\right]\frac{C\exp(\frac{-\tau^{2}}{2\sigma^{2}})}{\sigma\sqrt{2\pi}}d\tau\right)\right]$
$\displaystyle=\min\limits_{t>0}\left[(n+1)^{(s-1)}e^{-\vartheta
t}\left(a_{0}k+C\left(k+\sqrt{\frac{\mathbb{I}_{1}^{M}-k}{k}}\right)\cdot\right.\right.~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
(148)
$\displaystyle\left.\left.\sum\limits_{l=1}^{n}a_{l}\exp(8\kappa\overline{\lambda}+2(\kappa+8\overline{\lambda})lsrt+2(\sigma(\kappa+8\overline{\lambda})lsr)^{2}t^{2})\right)\right],~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$

where inequality $\leq_{1}$ is obtained by the distribution bound for
$\beta_{0}(\tau)$ via another distribution function
$\frac{C\exp(\frac{-\tau^{2}}{2\sigma^{2}})}{\sigma\sqrt{2\pi}}$, and the last
equality comes from Gaussian integral with respect to the variable $\tau$ by
setting $1-\lambda$ as $\overline{\lambda}$. $\hfill\Box$

Following corollary is about a tensor expander bound with identity function
$f$.

######  Corollary 4.5.

If we consider the special case of Theorem 4.4 by assuming that the function
$f:x\rightarrow x$ is an identiy map, then we have

(149)
$\displaystyle\mathrm{Pr}\left(\left\|\sum\limits_{j=1}^{\kappa}g(v_{j})\right\|_{(k)}\geq\vartheta\right)$
$\displaystyle\leq$ $\displaystyle
C\left(k+\sqrt{\frac{\mathbb{I}_{1}^{M}-k}{k}}\right)\cdot$
$\displaystyle\exp\left(-\frac{\vartheta^{2}}{8\sigma^{2}r^{2}}+\frac{\vartheta}{2\sigma^{2}r^{2}}-\frac{1}{2\sigma^{2}}+8\kappa\overline{\lambda}\right).$

Proof: From Theorem 4.4, since the exponent is a quadratic function of $t$,
the minimum of this quadratic function is achieved by selecting $t$ as

(150) $\displaystyle
t=\frac{\vartheta-2(\kappa+8\overline{\lambda})r}{4\sigma^{2}r^{2}(\kappa+8\overline{\lambda})^{2}},$

then, we have the desired bound after some algebra by applying Eq. (150) in
Eq. (4.4) and setting $l=s=1$, all $a_{i}=0$ for $1\leq i\leq n$ except
$a_{1}=1$. $\hfill\Box$

##  5 Conclusions

In this work, we first build tensor norm inequalities based on the concept of
log-majorization, and apply these new tensor norm inequalities to derive the
_tensor expander Chernoff bounds_ which generalize the matrix expander
Chernoff bound by adopting more general norm for tensors, Ky Fan norm, and
general convex function, instead of identity function, of random tensors
summation.

There are several future directions that can be explored based on the current
work. The first is to consider other types of tensor expander Chernoff bounds
under other non-independent assumptions among random tensors. The other
direction is to characterize random behaviors of other tensor related
quantities besides norms or eigenvalues, for example, what is the Hermitian
tensor rank behavior for the summation of random tensors.

## Acknowledgments

The helpful comments of the referees are gratefully acknowledged.

## References

  * [1] R. Ahlswede and A. Winter, Strong converse for identification via quantum channels, IEEE Transactions on Information Theory, 48 (2002), pp. 569–579.
  * [2] R. Bhatia, Matrix analysis, vol. 169, Springer Science & Business Media, 2013.
  * [3] S. Y. Chang, Convenient tail bounds for sums of random tensors, 2020, https://arxiv.org/abs/2012.15428.
  * [4] S. Y. Chang, General tail bounds for random tensors summation: Majorization approach, 2021, https://arxiv.org/abs/2105.06078.
  * [5] H. Chernoff, A note on an inequality involving the normal distribution, The Annals of Probability, (1981), pp. 533–535.
  * [6] K.-M. Chung, H. Lam, Z. Liu, and M. Mitzenmacher, Chernoff-hoeffding bounds for markov chains: Generalized and simplified, arXiv preprint arXiv:1201.0559, (2012).
  * [7] K. Fan and A. J. Hoffman, Some metric inequalities in the space of matrices, Proceedings of the American Mathematical Society, 6 (1955), pp. 111–116.
  * [8] A. Garg, Y. T. Lee, Z. Song, and N. Srivastava, A matrix expander chernoff bound, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018, pp. 1102–1114.
  * [9] D. Gillman, A chernoff bound for random walks on expander graphs, SIAM Journal on Computing, 27 (1998), pp. 1203–1220.
  * [10] A. D. Healy, Randomness-efficient sampling within nc, Computational Complexity, 17 (2008), pp. 3–37.
  * [11] F. Hiai, Matrix analysis: matrix monotone functions, matrix means, and majorization, Interdisciplinary Information Sciences, 16 (2010), pp. 139–248.
  * [12] F. Hiai, R. König, and M. Tomamichel, Generalized log-majorization and multivariate trace inequalities, in Annales Henri Poincaré, vol. 18, Springer, 2017, pp. 2499–2521.
  * [13] D. Huang, Generalizing lieb’s concavity theorem via operator interpolation, Advances in Mathematics, 369 (2020), p. 107208.
  * [14] Y. M. Jang and B. G. Kim, Chernoff bound approach for connection control in broadband satellite systems, IEEE Communications letters, 3 (1999), pp. 154–156.
  * [15] M. J. Kearns, U. V. Vazirani, and U. Vazirani, An introduction to computational learning theory, MIT press, 1994.
  * [16] M. Liang and B. Zheng, Further results on Moore-Penrose inverses of tensors with application to tensor nearness problems, Comput. Math. Appl., 77 (2019), pp. 1282–1293, https://doi.org/10.1016/j.camwa.2018.11.001, https://doi.org/10.1016/j.camwa.2018.11.001.
  * [17] A. W. Marshall, I. Olkin, and B. C. Arnold, Inequalities: theory of majorization and its applications, Springer Series in Statistics, Springer, New York, second ed., 2011, https://doi.org/10.1007/978-0-387-68276-1, https://doi.org/10.1007/978-0-387-68276-1.
  * [18] J. K. Merikoski and A. Virtanen, Bounds for eigenvalues using the trace and determinant, Linear algebra and its applications, 264 (1997), pp. 101–108.
  * [19] G. Ni, Hermitian tensor and quantum mixed state, arXiv preprint arXiv:1902.02640, (2019).
  * [20] S. Rao and O. Regev, A sharp tail bound for the expander random sampler, arXiv preprint arXiv:1703.10205, (2017).
  * [21] M. Rudelson, Random vectors in the isotropic position, Journal of Functional Analysis, 164 (1999), pp. 60–72.
  * [22] D. Sutter, M. Berta, and M. Tomamichel, Multivariate trace inequalities, Communications in Mathematical Physics, 352 (2017), pp. 37–58.
  * [23] J. A. Tropp, User-friendly tail bounds for sums of random matrices, Foundations of computational mathematics, 12 (2012), pp. 389–434.
  * [24] J. A. Tropp, An introduction to matrix concentration inequalities, arXiv preprint arXiv:1501.01571, (2015).
  * [25] A. Wigderson and D. Xiao, Derandomizing the ahlswede-winter matrix-valued chernoff bound using pessimistic estimators, and applications, Theory of Computing, 4 (2008), pp. 53–76.