§ INTRODUCTION

§.§ From Random Matrices to Radom Tensors

A random matrix is a matrix-valued random variable—that is, a matrix in which some or all entries are random variables. Random matrices have played an important role in computational mathematics [14], physics [3], neuroscience [39], wireless communication [36], control [37], etc. Many important properties of scientific and engineering systems can be modelled mathematically as matrix problems. In order to consider a high-dimensional system, it is often more convenient to consider tensors, or multidimensional data, instead of matrices (two-dimensional data).

Tensors have various applications in science and engineering [22]. In numerical applications, tensors can be applied to solve multilinear system of equations [40], high-dimensional data fitting/regression [11], tensor complementary problem [42], tensor eigenvalue problem [9], etc. In data processing applications, tensor theory applications include unsupervised separation of unknown mixtures of data signals [41, 26], data filtering [27], MIMO (multi-input multi-output) code-division [10, 8], radar, passive sensing, and communications [28, 33]. In other applications, tensors are also utilized to characterize data with coupling effects, e.g., network signal processing [32, 31, 13] and image processing [21, 18]. Tensor decomposition methods have been reported recently to establish the latent-variable models, such as topic models in [2], and the connections between the orthogonal tensor decomposition and the method of moments for undertaking the Latent Dirichlet Allocation (LDA) in [34]. However, all these applications assume that systems modelled by tensors are fixed and such assumption is not true and practical in solving tensors associated issues. In recent years, there are more works begin to target theory about random tensors, see [15], [20], [19],
[23], [38], and references therein. In this work, we will focus on establishing a series of tail bounds for sums of random tensors.

§.§ Technical Results

Given a finite sequence of random Hermitian tensors $\{ \mathcal{X}_i \} \in \mathbb{C}^{I_1 \times \cdots \times I_M \times I_1 \times \cdots \times I_M}$, the main purpose of this work is to bound the following probability:

\begin{eqnarray}\label{eq:the problem of max eigen}
\mathbb{P} \left( \lambda_{\max}\left( \sum\limits_{i} \mathcal{X}_i \right) \geq \theta    \right),
\end{eqnarray}

where $\lambda_{\max}$ represents the largest eigenvalue of a Hermitian tensor obtained from eigenvalue decomposition. The problem posted in Eq. (<ref>) are associated to the following problems: (1) the smallest and the largest singular value of a sum of random tensors with square or rectangular shapes; (2) extension random variable probability bounds, e.g., Chernoff and Bernstein bounds, to tensors settings; (3) tensor martingales and other adapted random sequences of tensors.

There are two main technical tools required by this work to build those tensor probability bounds. The first is Laplace transform method, which provides a systematic way to give tail bounds for the sum of scalar random variables. In [1], the authors apply Laplace transform method to bound Eq. (<ref>) with the matrix setting, i.e., the tail probability for the maximum eigenvalue of the sum of Hermitian matrices is controlled by a matrix version of the moment-generating function. They proved following:

\begin{eqnarray}\label{eq:Ahlswede Winter bound for max eigen}
\mathbb{P} \left( \lambda_{\max}\left( \sum\limits_{i} \mathbf{X}_i \right) \geq \theta    \right) \leq \inf\limits_{t > 0} \Big\{ e^{-t \theta} \mathbb{E} \mathrm{Tr} \exp \left( \sum\limits_{i} t \mathbf{X}_i \right)\Big\}.
\end{eqnarray}

However, the bound to $\inf\limits_{t > 0} \Big\{ e^{-t \theta} \mathbb{E} \mathrm{Tr} \exp \left( \sum\limits_{i} t \mathbf{X}_i \right)\Big\}$ is far from optimal according to [35] (see Sections 3.7 and 4.8 in [35]). In this work, we extend the Laplace transform method to tensors. The other important technique utilized in this work is to extend Lieb's concavity theorem [25] to tensors. Tensor Lieb’s theorem is introduced in Section <ref>, and we illustrate how to combine this result with the tensor Laplace transform method as our main technique to prove a series of random tensors bounds. We utilize this mechanism as our main approach to derive a large family of probability inequalities that are essentially tight in a wide variety of scenarios. Most random matrix inequalities studied in [35] have same origin as those random tensor inequalities discussed at this work, however, we enhance main tools, i.e., Laplace transform method and Lieb's concavity theorem, from matrices to tensors, and obtain new random tensor inequalities with tensor orders and dimensions as factors.

This work will derive various inequalities based on Eq. (<ref>). We will provide basic notations first before listing main inequalities investigated at this paper. The symbols $\lambda_{\min}$ and $\lambda_{\max}$ are used to represent the minimum and maximum eigenvalues of a Hermitian tensor. The notation $\succeq$ is used to indicate the semidefinite ordering of tensors. $\left\Vert \mathcal{A} \right\Vert$ is defined as the largest singular value of the tensor $\mathcal{A}$.
The first category of concentration is associated with a sum of real numbers multiplied by independent random variables. If the independent random variables are drawn as normal (Gaussian) distribution or Rademacher distribution, the sum of real numbers multiplied by such random variables has sub-Gaussian tail behavior. In Section <ref>, we will provide the proof and its application about the following theorem.

Given a finite sequence $\mathcal{A}_i$ of fixed Hermitian tensors with dimensions as $\mathbb{C}^{I_1 \times \cdots \times I_M \times I_1 \times \cdots \times I_M}$, and let $\{ \alpha_i \}$ be a finite sequence of independent normal variables. We define

\begin{eqnarray}\label{eq:4_5_intro}
\sigma^2 &\define& \left\Vert \sum\limits_{i=1}^{n} \mathcal{A}^2_i \right\Vert,
\end{eqnarray}

then, for all $\theta \geq 0$, we have

\begin{eqnarray}\label{eq:4_3_intro}
\mathrm{Pr}\left( \lambda_{\max} \left( \sum\limits_{i=1}^{n}\alpha_i \mathcal{A}_i \right) \geq \theta \right) \leq \mathbb{I}_1^M e^{-\frac{\theta^2 }{2 \sigma^2}},
\end{eqnarray}

\begin{eqnarray}\label{eq:4_4_intro}
\mathrm{Pr}\left( \left\Vert \sum\limits_{i=1}^{n}\alpha_i \mathcal{A}_i \right\Vert \geq \theta \right) \leq 2 \mathbb{I}_1^M e^{-\frac{\theta^2 }{2 \sigma^2}}.
\end{eqnarray}

This theorem is also valid for a finite sequence of independent Rademacher random variables $\{ \alpha_i \}$.

Chernoff bound provides an estimate on the probability of the concentration results related to the number of successes in a sequence of independent random trials. In the tensor situation, the similar theorem concerns a sum of positive-semidefinite random
tensors subject to a uniform eigenvalue bound. The tensor Chernoff bound indicates that the largest (or smallest) eigenvalues of the tensor series have similar binomial random variable behavior.

Consider a sequence $\{ \mathcal{X}_i  \in \mathbb{C}^{I_1 \times \cdots \times I_M  \times I_1 \times \cdots \times I_M } \}$ of independent, random, Hermitian tensors that satisfy

\begin{eqnarray}
\mathcal{X}_i \succeq \mathcal{O} \mbox{~~and~~} \lambda_{\max}(\mathcal{X}_i) \leq T
\mbox{~~ almost surely.}
\end{eqnarray}

Define following two quantities:

\begin{eqnarray}
\mu_{\max} \define \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathbb{E} \mathcal{X}_i \right) \mbox{~~and~~}
\mu_{\min} \define \lambda_{\min}\left( \sum\limits_{i=1}^{n} \mathbb{E} \mathcal{X}_i \right),
\end{eqnarray}

then, let $\mathbb{I}_1^M = \prod\limits_{m=1}^M I_m$, we have following two inequalities:

\begin{eqnarray}\label{eq:Chernoff II Upper Bound_intro}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right) \geq (1+\theta) \mu_{\max} \right) \leq \mathbb{I}_1^M \left(\frac{e^{\theta}}{ (1 + \theta)^{1 + \theta}  }\right)^{\mu_{\max}/T} ,\mbox{~~ for $\theta \geq 0$;}
\end{eqnarray}

\begin{eqnarray}\label{eq:Chernoff II Lower Bound_intro}
\mathrm{Pr} \left( \lambda_{\min}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right) \leq (1 - \theta) \mu_{\min} \right) \leq \mathbb{I}_1^M \left(\frac{e^{-\theta}}{ (1 - \theta)^{1 - \theta}  }\right)^{\mu_{\min}/T} ,\mbox{~~ for $\theta \in [0,1]$.}
\end{eqnarray}

In Section <ref>, we will prove Chernoff inequality and discuss its applications.

Bernstein inequality is another inequality to bound the sum of independent, bounded random tensors by restricting the range of the maximum eigenvalue of each random tensors. Bernstein inequality can provide tighter bound compared to Hoeffding inequality.
In Section <ref>, following tensor Bernstein bound theorem and its applications are provided.

Given a finite sequence of independent Hermitian tensors $\{ \mathcal{X}_i  \in \mathbb{C}^{I_1 \times \cdots \times I_M  \times I_1 \times \cdots \times I_M } \}$ that satisfy

\begin{eqnarray}\label{eq1:thm:Bounded Tensor Bernstein_intro}
\mathbb{E} \mathcal{X}_i = 0 \mbox{~~and~~} \lambda_{\max}(\mathcal{X}_i) \leq T
\mbox{~~almost surely.}
\end{eqnarray}

Define the total variance $\sigma^2$ as: $\sigma^2 \define \left\Vert \sum\limits_i^n \mathbb{E} \left( \mathcal{X}^2_i \right) \right\Vert$.

Then, we have following inequalities:

\begin{eqnarray}\label{eq2:thm:Bounded Tensor Bernstein_intro}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right)\geq \theta \right) \leq \mathbb{I}_1^M \exp \left( \frac{-\theta^2/2}{\sigma^2 + T\theta/3}\right);
\end{eqnarray}

\begin{eqnarray}\label{eq3:thm:Bounded Tensor Bernstein_intro}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right)\geq \theta \right) \leq \mathbb{I}_1^M \exp \left( \frac{-3 \theta^2}{ 8 \sigma^2}\right)~~\mbox{for $\theta \leq \sigma^2/T$};
\end{eqnarray}

\begin{eqnarray}\label{eq4:thm:Bounded Tensor Bernstein_intro}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right)\geq \theta \right) \leq \mathbb{I}_1^M \exp \left( \frac{-3 \theta}{ 8 T } \right)~~\mbox{for $\theta \geq \sigma^2/T$}.
\end{eqnarray}

We also applied techniques developed at this work to tensor martingales in Section <ref>. In probability theory, the Azuma inequality gives a concentration result for the values of martingales that have bounded differences. Tensor Azuma inequality is given below.

Given a finite adapted sequence of Hermitian tensors $\{ \mathcal{X}_i  \in \mathbb{C}^{I_1 \times \cdots \times I_M  \times I_1 \times \cdots \times I_M } \}$ and a fixed sequence of Hermitian tensors $\{ \mathcal{A}_i \}$ that satisfy

\begin{eqnarray}\label{eq1:thm:Tensor Azuma_intro}
\mathbb{E}_{i-1} \mathcal{X}_i = 0 \mbox{~~and~~} \mathcal{X}^2_i \preceq  \mathcal{A}^2_i \mbox{almost surely},
\end{eqnarray}

where $i = 1,2,3,\cdots$.

Define the total varaince $\sigma^2$ as: $\sigma^2 \define \left\Vert \sum\limits_i^n \mathcal{A}_i^2 \right\Vert$.

Then, we have following inequalities:

\begin{eqnarray}\label{eq2:thm:Tensor Azuma_intro}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right)\geq \theta \right) \leq \mathbb{I}_1^M e^{-\frac{\theta^2}{8 \sigma^2}}.
\end{eqnarray}

In probability theory, Hoeffding's inequality builds an upper bound on the probability that the sum of bounded independent random variables drifts away from its expected value by more than a certain amount [17]. In this work, we generalize this result to the tensor setting by considering random tensors that satisfy semidefinite upper bounds in Section <ref>. In the tensor situation, the maximum eigenvalue for the sum of tensors also have subgaussian behavior.

Given a finite sequence of independent Hermitian tensors $\{ \mathcal{X}_i  \in \mathbb{C}^{I_1 \times \cdots \times I_M  \times I_1 \times \cdots \times I_M } \}$ and a fixed sequence of Hermitian tensors $\{ \mathcal{A}_i \}$ that satisfy

\begin{eqnarray}\label{eq1:thm:Tensor Hoeffding}
\mathbb{E}\mathcal{X}_i = 0 \mbox{~~and~~} \mathcal{X}^2_i \preceq  \mathcal{A}^2_i \mbox{almost surely},
\end{eqnarray}

where $i = 1,2,3,\cdots$.

Define the total variance $\sigma^2$ as: $\sigma^2 \define \left\Vert \sum\limits_i^n \mathcal{A}_i^2 \right\Vert$.

Then, we have following inequalities:

\begin{eqnarray}\label{eq2:thm:Tensor Hoeffding}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right)\geq \theta \right) \leq \mathbb{I}_1^M e^{-\frac{\theta^2}{8 \sigma^2}}.
\end{eqnarray}

McDiarmid inequality is crucial in determining the stability of machine learning algorithms by applying a simple concept: small change in training set will make small change in hypothesis. In Section <ref>, we extend McDiarmid inequality from the scalar-valued function to the tensor-valued function as shown below.

Given a set of $n$ independent random variables, i.e. $\{X_i: i = 1,2,\cdots n\}$, and let
$F$ be a Hermitian tensor-valued function that maps these $n$ random variables to a Hermitian tensor of dimension within $\mathbb{C}^{I_1 \times \cdots \times I_M  \times I_1 \times \cdots \times I_M }$. Consider a sequence of Hermitian tensors $\{ \mathcal{A}_i \}$ that satisfy

\begin{eqnarray}\label{eq1:thm:Tensor McDiarmid_intro}
\left( F(x_1,\cdots,x_i,\cdots,x_n)  -  F(x_1,\cdots,x'_i,\cdots,x_n) \right)^2 \preceq \mathcal{A}^2_i,
\end{eqnarray}

where $x_i, x'_i \in X_i$ and $1 \leq i \leq n$. Define the total variance $\sigma^2$ as: $\sigma^2 \define \left\Vert \sum\limits_i^n \mathcal{A}_i^2 \right\Vert $.

Then, we have following inequality:

\begin{eqnarray}\label{eq2:thm:Tensor McDiarmid_intro}
\mathrm{Pr} \left( \lambda_{\max}\left( F(x_1,\cdots,x_n) - \mathbb{E}F(x_1,\cdots,x_n )\right)\geq \theta \right) \leq \mathbb{I}_1^M e^{-\frac{\theta^2}{8 \sigma^2}}.
\end{eqnarray}

§.§ Paper Organization

The remaining part of this paper is organized as follows. Basic probability theory required by our proofs and tensor notations are provided in Section <ref>. Main technical tools for tensor tail bounds are discussed in  Section <ref>. Section <ref> utilizes Gaussian and Rademacher series as case studies to explain tensor probability inequalities. Tensor Chernoff bound and its applications are discussed in Section <ref>. In Section <ref>, Tensor Bernstein bound and its applications are provided. Several martingale results based on random tensor are presented in Section <ref>. Concluding remarks are given by Section <ref>.

§ PRELIMINARIES OF TENSOR AND PROBABILITY

In this section, we will provide a brief introduction of tensors and probability required for our future theory development. More detailed exposition about tensors can be found at [30, 29]. In [4], it introduces those basic concepts about probability and moment-generating function.

§.§ Fundamental of Tensor

§.§.§ Tensor Notations

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] \define \{1, 2, \cdots ,N\}$. An order-$N$ tensor (or $N$-th order tensor) denoted by $\mathcal{X} \define (a_{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 $I_1 \times I_2 \times \cdots \times 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 $a_{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 $a_{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} \define (a_{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} \define (b_{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 [24], 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

\begin{eqnarray}\label{eq: tensor addition definition}
(\mathcal{X} + \mathcal{Y} )_{i_1, \cdots, i_M, j_1 \times \cdots \times j_N} &\define&
a_{i_1, \cdots, i_M, j_1 \times \cdots \times j_N} \nonumber \\
& &+ b_{i_1, \cdots, i_M, j_1 \times \cdots \times j_N}.
\end{eqnarray}

On the other hand, for tensors $\mathcal{X} \define (a_{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} \define (b_{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 [24], 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

\begin{eqnarray}\label{eq: Einstein product definition}
\lefteqn{(\mathcal{X} \star_{N} \mathcal{Y} )_{i_1, \cdots, i_M,k_1 \times \cdots \times k_L} \define} \nonumber \\ &&\sum\limits_{j_1, \cdots, j_N} a_{i_1, \cdots, i_M, j_1, \cdots,j_N}b_{j_1, \cdots, j_N, k_1, \cdots,k_L}.
\end{eqnarray}

Note that we will often abbreviate a tensor product $\mathcal{X} \star_{N} \mathcal{Y}$ to “$\mathcal{X} \hspace{0.05cm}\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.

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

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

\begin{eqnarray}\label{eq: identity tensor definition}
(\mathcal{I})_{i_1 \times \cdots \times i_N\times
j_1 \times \cdots \times j_N} \define \prod_{k = 1}^{N} \delta_{i_k, j_k},
\end{eqnarray}

where $\delta_{i_k, j_k} \define 1$ if $i_k  = j_k$; otherwise $\delta_{i_k, j_k} \define 0$.

In order to define Hermitian tensor, the conjugate transpose operation (or Hermitian adjoint) of a tensor is specified as follows.

Given a tensor $\mathcal{X} \define (a_{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

\begin{eqnarray}\label{eq:tensor conjugate transpose definition}
(\mathcal{X}^H)_{ j_1, \cdots,j_N,i_1, \cdots, i_M}  \define
\overline{a_{i_1, \cdots, i_M,j_1, \cdots,j_N}},
\end{eqnarray}

where the overline notion indicates the complex conjugate of the complex number $a_{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.

Given a tensor $\mathcal{U} \define (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

\begin{eqnarray}\label{eq:unitary tensor definition}
\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},
\end{eqnarray}

then $\mathcal{U}$ is a unitary tensor.

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

Given a square tensor $\mathcal{X} \define (a_{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

\begin{eqnarray}\label{eq:tensor invertible definition}
\mathcal{X} \star_M \mathcal{X} = \mathcal{X} \star_M \mathcal{X} = \mathcal{I},
\end{eqnarray}

then $\mathcal{X}$ is the inverse of $\mathcal{X}$. We usually write $\mathcal{X} \define \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

\begin{eqnarray}\label{eq: tensor trace def}
\mathrm{Tr}(\mathcal{X}) \define \sum\limits_{1 \leq i_j \leq I_j,\hspace{0.05cm}j \in [M]} \mathcal{X}_{i_1, \cdots, i_M,i_1, \cdots, i_M}.
\end{eqnarray}

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

\begin{eqnarray}\label{eq: tensor inner product def}
\langle \mathcal{X}, \mathcal{Y} \rangle \define \mathrm{Tr}\left(\mathcal{X}^H \star_M \mathcal{Y}\right).
\end{eqnarray}

According to Eq. (<ref>), the Frobenius norm of a tensor $\mathcal{X}$ is defined by

\begin{eqnarray}\label{eq:Frobenius norm}
\left\Vert \mathcal{X} \right\Vert \define \sqrt{\langle \mathcal{X}, \mathcal{X} \rangle}.
\end{eqnarray}

We use $\lambda_{\min}$ and $\lambda_{\max}$ to represent the minimum and the maximum eigenvalues of a Hermitian tensor. The notation $\succeq$ is used to indicate the semidefinite ordering of tensors. If we have $\mathcal{X} \succeq \mathcal{Y}$, this means that the difference tensor $\mathcal{X} - \mathcal{Y}$ is a positive semidefinite tensor.

§.§.§ Tensor Functions

Given a function $g: \mathbb{R} \rightarrow \mathbb{R}$, the mapping result of a diagonal tensor by the function $g$ is to obtain another same size diagonal tensor with diagonal entry mapped by the function $g$. Then, the function $g$ can be extended to allow a Hermitian tensor $\mathcal{X} \in \mathbb{C}^{I_1 \times \cdots \times I_M\times I_1 \times \cdots \times I_M}$ as an input argument as

\begin{eqnarray}\label{eq:tensor func def}
g(\mathcal{X}) \define \mathcal{U} \star_M g(\Lambda) \star_M \mathcal{U}^H,~~\mbox{where $\mathcal{X} =  \mathcal{U}\star_M \Lambda \star_M \mathcal{U}^H $.}
\end{eqnarray}

The spectral mapping theorem asserts that each eigenvalue of $g(\mathcal{X})$ is equal to $g(\lambda)$ for some eigenvalue $\lambda$ of $\mathcal{X}$. From the semidefinite ordering of tensors, we also have

\begin{eqnarray}\label{eq:tensor psd ordering}
f(x) \geq g(x),~~\mbox{for $x \in [a, b]$}~~~ \Rightarrow ~~~ f(\mathcal{X})  \succeq
g(\mathcal{X}),~~\mbox{for eigenvalues of $\mathcal{X} \in [a, b]$;}
\end{eqnarray}

where $[a, b]$ is a real interval.

Given a square tensor $\mathcal{X} \in \mathbb{C}^{I_1 \times \cdots \times I_M\times I_1 \times \cdots \times I_M}$, the tensor exponential of the tensor $\mathcal{X}$ is defined as

\begin{eqnarray}\label{eq: tensor exp def}
e^{\mathcal{X}} \define \sum\limits_{k=0}^{\infty} \frac{\mathcal{X}^{k}}{k !},
\end{eqnarray}

where $\mathcal{X}^0$ is defined as the identity tensor $\mathcal{I} \in \mathbb{C}^{I_1 \times \cdots \times I_M\times I_1 \times \cdots \times I_M}$ and

$\mathcal{X}^{k} = \underbrace{\mathcal{X} \star_M \mathcal{X} \star_M \dots \star_M\mathcal{X} }_{\mbox{$k$ terms of $\mathcal{X}$}} $.

Given a tensor $\mathcal{Y}$, the tensor $\mathcal{X}$ is said to be a tensor logarithm of $\mathcal{Y}$ if $e^{\mathcal{X}}  = \mathcal{Y}$

Several facts are about tensor exponential. First, the exponential of a Hermitian tensor is always positive-definite due to the spectral mapping theorem. Second, the trace exponential function, $\mathcal{X} \rightarrow \mathrm{Tr} \exp(\mathcal{X})$, is convex. Third, the trace exponential function follows monotone property with respect to semidefinite ordering as

\begin{eqnarray}\label{eq:trace exp monotone}
\mathcal{X} \succeq \mathcal{Y} ~~~ \Rightarrow ~~~ \mathrm{Tr} \exp(\mathcal{X}) \geq  \mathrm{Tr} \exp(\mathcal{Y}).
\end{eqnarray}

However, different from exponential rules for scalers, the tensor exponential does not convert sums into products. The Golden-Thompson inequality for tensors [5] shows the following relationship

\begin{eqnarray}
\mathrm{Tr}e^{\mathcal{X} + \mathcal{Y}} \leq \mathrm{Tr} \left( e^{\mathcal{X} \star_M \mathcal{Y} }\right),
\end{eqnarray}

where $\mathcal{X}, \mathcal{Y} \in \mathbb{C}^{I_1 \times \cdots \times I_M\times I_1 \times \cdots \times I_M}$ are Hermitian tensors.

For the tensor logarithm, we have the following monotone relation

\begin{eqnarray}\label{eq:log monotone}
\mathcal{X} \succeq \mathcal{Y} ~~~ \Rightarrow ~~~ \log(\mathcal{X}) \succeq  \log(\mathcal{Y}).
\end{eqnarray}

Moreover, the tensor logarithm is also concave, i.e., we have

\begin{eqnarray}\label{eq:log concave}
t \log (\mathcal{X}_1) + (1-t) \log (\mathcal{X}_2)  \preceq \log( t \mathcal{X}_1 +
(1-t) \mathcal{X}_2 ),
\end{eqnarray}

where $\mathcal{X}_1, \mathcal{X}_2$ are positive-definite tensors and $t \in [0,1]$. The concavity of tensor logarithm can be derived from Hansen-Pedersen Characterizations, see [7].

If a given tensor $\mathcal{Y} \in \mathbb{C}^{I_1 \times \cdots \times I_M\times J_1 \times \cdots \times J_M}$ is not square, we can perform Hermitian dialation, represented as $\mathbb{D}$, to the tensor $\mathcal{Y}$ as

\begin{eqnarray}\label{eq:Hermitian dialation def}
\mathbb{D}(\mathcal{Y}) \define  \begin{bmatrix}
\mathcal{O} & \mathcal{Y} \\
\mathcal{Y}^H & \mathcal{O}  \\
\end{bmatrix}
\end{eqnarray}

where $\mathbb{D}(\mathcal{Y}) \in  \mathbb{C}^{(I_1 + J_1) \times \cdots \times (I_M + J_M) \times (I_1 + J_1) \times \cdots \times (I_M + J_M)}$ is a Hermitian tensor. Since we have

\begin{eqnarray}
\mathbb{D}(\mathcal{Y})^2 =  \begin{bmatrix}
\mathcal{Y}\mathcal{Y}^H & \mathcal{O}   \\
\mathcal{O} & \mathcal{Y}^H \mathcal{Y}  \\
\end{bmatrix},
\end{eqnarray}

then, we have following spectral norm relation

\begin{eqnarray}\label{eq:spectral identity}
\lambda_{\max}( \mathbb{D}(\mathcal{Y})  ) = \left\Vert \mathbb{D}(\mathcal{Y})\right\Vert = \left\Vert \mathcal{Y} \right\Vert,
\end{eqnarray}

where $\left \Vert \cdot \right \Vert$ is the spectral norm for a tensor and this will return the maximum singular value of its argument tensor. Hermitian dilation operation enables us to extend results from Hermitian tensors to other non-square tensors.

§.§ Tensor Moments and Cumulants

Since the expectation of a random tensor can be treated as convex combination, expectation will preserve the semidefinite order as

\begin{eqnarray}
\mathcal{X} \succ \mathcal{Y} \mbox{~~almost surely} ~~~ \Rightarrow ~~~
\mathbb{E}(\mathcal{X}) \succ \mathbb{E}(\mathcal{Y}).
\end{eqnarray}

From operator Jensen's inequality [16], we also have

\begin{eqnarray}
\mathbb{E}(\mathcal{X}^2) \succeq \left(\mathbb{E}(\mathcal{X})\right)^2.
\end{eqnarray}

Suppose a random Hermitian tensor $\mathcal{X}$ having tensor moments of all orders, i.e., $\mathbb{E}(\mathcal{X}^n)$ existing for all $n$, we can define the tensor moment-generating function, denoted as $\mathbb{M}_{\mathcal{X}}(t)$, and the tensor cumulant-generating function, denoted as $\mathbb{K}_{\mathcal{X}}(t)$, for the tensor $\mathcal{X}$ as

\begin{eqnarray}\label{eq:def mgf and cgf}
\mathbb{M}_{\mathcal{X}}(t) \define \mathbb{E} e^{t \mathcal{X}}, \mbox{~~and~~~}
\mathbb{K}_{\mathcal{X}}(t) \define \log \mathbb{E} e^{t \mathcal{X}},
\end{eqnarray}

where $t \in \mathbb{R}$. Both the tensor moment-generating function and the tensor cumulant-generating function can be expressed as power series expansions:

\begin{eqnarray}\label{eq:mgf and cgf expans}
\mathbb{M}_{\mathcal{X}}(t) = \mathcal{I} + \sum\limits_{n=1}^{\infty} \frac{t^n}{n !}\mathbb{E}(\mathcal{X}^n), \mbox{~~and~~~}
\mathbb{K}_{\mathcal{X}}(t) = \sum\limits_{n=1}^{\infty} \frac{t^n}{n !} \psi_n,
\end{eqnarray}

where $\psi_n$ is called tensor cumulant. The tensor cumulant $\psi_n$ can be expressed as a polynomial in terms of tensor moments up to the order $n$, for example, the first cumulant is the mean and the second cumulant is the variance:

\begin{eqnarray}\label{eq:cumulant mean and var}
\psi_1 = \mathbb{E}(\mathcal{X}), \mbox{~~and~~~}
\psi_2 = \mathbb{E}(\mathcal{X}^2) - (\mathbb{E}(\mathcal{X}))^2.
\end{eqnarray}

Finally, in this work, we also assume that all random variables are sufficiently regular for us to compute their expectations, interchange limits, etc.

§ TRACE CONCAVITY METHOD

The main purpose of this section is to develop two important tools which will be applied
intensively in the proof of probability inequalities for the maximum eigenvalue of a sum
of independent random tensors. The first one is the Laplace transform method for tensors discussed in Section <ref>, and the second one is the tensor trace concavity which will be presented in Section <ref>.

§.§ Laplace Transform Method for Tensors

We extend the Laplace transform bound from matrices to tensors based on [1]. Following lemma is given to establish the Laplace transform bound for tensors.

Let $\mathcal{X}$ be a random Hermitian tensor. For $\theta \in \mathbb{R}$, we have

\begin{eqnarray}
\mathbb{P} (\lambda_{\max}(\mathcal{X}) \geq \theta) \leq \inf_{t > 0} \Big\{ e^{-\theta t} \mathbb{E}\mathrm{Tr} e^{t \mathcal{X}} \Big\}
\end{eqnarray}

Given a fix value $t$, we have

\begin{eqnarray}\label{eq1: lma: Laplace Transform Method}
\mathbb{P} (\lambda_{\max}(\mathcal{X}) \geq \theta) = \mathbb{P} (\lambda_{\max}(t\mathcal{X}) \geq t \theta ) = \mathbb{P} (e^{ \lambda_{\max}(t\mathcal{X})  } \geq e^{ t \theta}  ) \leq e^{-t \theta} \mathbb{E} e^{ \lambda_{\max}(t\mathcal{X}) }.
\end{eqnarray}

The first equality uses the homogeneity of the maximum eigenvalue map, the second equality comes from the monotonicity of the scalar exponential function, and the last relation is Markov's inequality. Because we have

\begin{eqnarray}\label{eq2: lma: Laplace Transform Method}
e^{\lambda_{\max} (t \mathcal{Y})} = \lambda_{\max}(e^{t \mathcal{Y}}) \leq  \mathrm{Tr} e^{t \mathcal{Y}},
\end{eqnarray}

where the first equality used the spectral mapping theorem, and the inequality holds because the exponential of an Hermitian tensor is positive definite and the maximum eigenvalue of a positive definite tensor is dominated by the trace [24]. From Eqs (<ref>) and (<ref>), this lemma is established.

The Lemma <ref> helps us to control the tail probabilities for the maximum eigenvalue of a random Hermitian tensor by utilizing a bound for the traces of the tensor moment-generating function introduced in Section <ref>.

§.§ Tensor Trace Concavity

In this section, we will extend Lieb’s concavity theorem to tensors and we begin with the definition about the relative entropy between two tensors.

Given two positive definite tensors $\mathcal{A} \in \mathbb{C}^{I_1 \times \cdots \times I_M \times I_1 \times \cdots \times I_M}$ and tensor $\mathcal{B} \in \mathbb{C}^{I_1 \times \cdots \times I_M \times I_1 \times \cdots \times I_M}$. The relative entropy between tensors $\mathcal{A}$ and  $\mathcal{B}$ is defined as

\begin{eqnarray}
D( \mathcal{A} \parallel \mathcal{B}) \define \mathrm{Tr} \mathcal{A} \star_M (\log \mathcal{A} - \log \mathcal{B}).
\end{eqnarray}

Given a continuous function defined over a real interval as $f: [a, b] \rightarrow \mathbb{R}$, and $\mathcal{T} \in \mathbb{C}^{I_1 \times \cdots \times I_M \times I_1 \times \cdots \times I_M}$ as a Hermitian tensor with spectrum in $[a, b]$ and spectrum decomposition as $\mathcal{T} = \sum\limits_{\lambda_n} \lambda_n \mathcal{U}_{\lambda_n}$, where $\mathcal{U}_{\lambda_n} \in \mathbb{C}^{I_1 \times \cdots \times I_M \times I_1 \times \cdots \times I_M}$ are mutually orthogonal tensors, then the mapping for the tensor $\mathcal{T}$ by $f$ can be defined as $f(\mathcal{T}) = \sum\limits_{\lambda_n} f(\lambda_n) \mathcal{U}_{\lambda_n}$. The function $f$ is called as a tensor convex function if $f(\lambda_n)$ is convex on the Hermitian tenor with spectrum in $[a,b]$. We apply perspective function [12] notion for tensor convex and introduce the following lemma about the convexity of a tensor convex function.

Given $f$ as a tensor convex function, two commuting tensors $\mathcal{X}, \mathcal{Y} \in$
$\mathbb{C}^{I_1 \times \cdots \times I_M \times I_1 \times \cdots \times I_M}$, i.e., $\mathcal{X}\star_M \mathcal{Y} = \mathcal{Y}\star_M \mathcal{X}$, and the existence of the $\mathcal{Y}^{-1}$, then the following map $h$

\begin{eqnarray}\label{eq:lma:perspective func}
h (\mathcal{X}, \mathcal{Y}) = f(\mathcal{X} \star_M \mathcal{Y}^{-1}) \star_M \mathcal{Y}
\end{eqnarray}

is jointly convex in the sense that, given $t \in [0, 1]$, if $\mathcal{X} = t \mathcal{X}_1 + (1-t) \mathcal{X}_2$ and $\mathcal{Y} = t \mathcal{Y}_1 + (1-t) \mathcal{Y}_2$ with $\mathcal{X}_1 \star_M \mathcal{Y}_1 = \mathcal{Y}_1 \star_M \mathcal{X}_1$ and $\mathcal{X}_2 \star_M \mathcal{Y}_2 = \mathcal{Y}_2 \star_M \mathcal{X}_2$, we should have

\begin{eqnarray}
h (\mathcal{X}, \mathcal{Y})  \leq t h (\mathcal{X}_1, \mathcal{Y}_1) + (1-t) h (\mathcal{X}_2, \mathcal{Y}_2).
\end{eqnarray}

Constructing tensors $\mathcal{A} = (t \mathcal{Y}_1)^{1/2} \star_M \mathcal{Y}^{-1/2}$
and $\mathcal{B} = ( (1-t)\mathcal{Y}_2)^{1/2} \star_M \mathcal{Y}^{-1/2}$, then we have

\begin{eqnarray}\label{eq:lma:perspective func 1}
\mathcal{A}^H \star_M \mathcal{A} + \mathcal{B}^H \star_M \mathcal{B} = \mathcal{I}
\end{eqnarray}

Since we have

\begin{eqnarray}
h(\mathcal{X}, \mathcal{Y}) &=& f(\mathcal{X} \star_M \mathcal{Y}^{-1} ) \star_M \mathcal{Y} \nonumber \\
&=&   \mathcal{Y}^{1/2} \star_M f(  \mathcal{Y}^{-1/2} \star_M \mathcal{X} \star_M \mathcal{Y}^{-1/2} ) \star_M \mathcal{Y}^{1/2} \nonumber \\
&=&  \mathcal{Y}^{1/2} \star_M f( \mathcal{A}^H \star_M \mathcal{X}_1 \star_M \mathcal{Y}^{-1}_1 \star_M \mathcal{A} +  \mathcal{B}^H \star_M  \mathcal{X}_2 \star_M \mathcal{Y}^{-1}_2  \star_M \mathcal{B} ) \star_M \mathcal{Y}^{1/2} \nonumber \\
&\leq_1& \mathcal{Y}^{1/2} \star_M \left( \mathcal{A}^H \star_M f(\mathcal{X}_1 \star_M \mathcal{Y}^{-1}_1 ) \star_M \mathcal{A} \right. \nonumber \\
&  & \left. +  \mathcal{B}^H \star_M f(\mathcal{X}_2 \star_M \mathcal{Y}^{-1}_2 )  \star_M \mathcal{B} \right) \star_M \mathcal{Y}^{1/2} \nonumber \\
&=&  (t \mathcal{Y}_1)^{1/2}  f(\mathcal{X}_1 \star_M \mathcal{Y}^{-1}_1 )  (t \mathcal{Y}_1)^{1/2} + ((1-t) \mathcal{Y}_2)^{1/2}  f(\mathcal{X}_2 \star_M \mathcal{Y}^{-1}_2 )  ((1-t) \mathcal{Y}_2)^{1/2}   \nonumber \\
&=& t h(\mathcal{X}_1, \mathcal{Y}_1)  + (1 - t) h(\mathcal{X}_2, \mathcal{Y}_2)
\end{eqnarray}

where $\leq_1$ is based on Hansen-Pedersen-Jensen inequality and the condition provided by Eq. (<ref>), see Theorem 2.1 in [12].

Following lemma is given to establish the joint convexity property of relative entropy for tensors.

The relative entropy function of two positive-definite tensors  is a jointly convex function. That is

\begin{eqnarray}\label{eq:lma:joint conv of rela entropy}
\mathbb{D}(t \mathcal{A}_1 + (1 - t) \mathcal{A}_2 \parallel t \mathcal{B}_1 + (1 - t) \mathcal{B}_2) \leq t \mathbb{D}( \mathcal{A}_1 \parallel \mathcal{B}_1 ) +  (1- t) \mathbb{D} (\mathcal{A}_2 \parallel \mathcal{B}_2),
\end{eqnarray}

where $ t \in [0, 1]$ and all the following four tensors $\mathcal{A}_1$, $\mathcal{B}_1$, $\mathcal{A}_2$ and $\mathcal{B}_2$, are positive definite.

From the definition <ref>, we wish to show the joint convexity of the function $\mathbb{D} (\mathcal{A} \parallel \mathcal{B})$ with respect to the tensors $\mathcal{A}, \mathcal{B} \in \mathbb{C}^{I_1 \times \cdots \times I_M \times I_1 \times \cdots \times I_M}$. Let us define tensor operators $\mathcal{F}(\mathcal{X}) \define \mathcal{A} \star_M \mathcal{X}$ and $\mathcal{G}(\mathcal{X}) \define \mathcal{X} \star_M \mathcal{B}$  for the variable tensor $\mathcal{X}  \in \mathbb{C}^{I_1 \times \cdots \times I_M \times I_1 \times \cdots \times I_M}$. Then, we have $\mathcal{F}(\mathcal{X})$ and $\mathcal{G}(\mathcal{X})$ commuting on the inner product operation $\langle \mathcal{F}(\mathcal{X}), \mathcal{G}(\mathcal{X}) \rangle$ defined by Eq. (<ref>), i.e., $\mathrm{Tr}(\mathcal{F}^H(\mathcal{X})\star_M \mathcal{G}(\mathcal{X}) ) =\mathrm{Tr}(\mathcal{G}^H(\mathcal{X}) \star_M \mathcal{F}(\mathcal{X}) )$. Since the function $f(x) = x \log x$ is tensor convex, we apply Lemma <ref> to operators $\mathcal{F}(~~), \mathcal{G}(~~)$ and the function $h$ definition provided by Eq. (<ref>) to obtain the following relation:

\begin{eqnarray}
\langle \mathcal{I}, h (\mathcal{F}(\mathcal{I}), \mathcal{G}(\mathcal{I}) \rangle &=&
\langle \mathcal{I},~~\mathcal{G}(\mathcal{I}) \star_M ( \mathcal{F}(\mathcal{I}) \star_M \mathcal{G}^{-1}(\mathcal{I} )) \log ( \mathcal{F}(\mathcal{I} ) \star_M \mathcal{G}^{-1}(\mathcal{I})  )   \rangle \nonumber \\
&=& \langle \mathcal{I}, \mathcal{F}(\mathcal{I}) (\log \mathcal{F}(\mathcal{I}) - \log \mathcal{G}(\mathcal{I}) )   \rangle \nonumber \\
&=& \mathrm{Tr}(\mathcal{A} \log \mathcal{A} - \mathcal{A} \log \mathcal{B} )= \mathbb{D}(\mathcal{A} \parallel \mathcal{B}),
\end{eqnarray}

is jointly convex with respect to tensors $\mathcal{A}$ and $\mathcal{B}$.

Let $\mathcal{H}$ be a Hermitian tensor. Following map

\begin{eqnarray}\label{eq:thm:Lieb concavity thm}
\mathcal{A} \rightarrow \mathrm{Tr}e^{\mathcal{H}+ \log \mathcal{A}}
\end{eqnarray}

is concave on the positive-definite cone.

From Klein's inequality for the map $t \rightarrow t \log t$ (which is strictly concave for $t > 0$) and Hermitian tensors $\mathcal{X}, \mathcal{Y}, $we have

\begin{eqnarray}
\mathrm{Tr} \mathcal{Y} \geq \mathrm{Tr} \mathcal{X} - \mathrm{Tr} \mathcal{X} \log \mathcal{X} + \mathrm{Tr} \mathcal{X} \log \mathcal{Y}.
\end{eqnarray}

If we replace $\mathcal{Y}$ by $e^{\mathcal{H} + \log \mathcal{A}}$, we then have

\begin{eqnarray}\label{eq:var formula}
\mathrm{Tr} e^{\mathcal{H} + \log \mathcal{A}} = \max\limits_{\mathcal{X} \succ \mathcal{O}} \Big\{ \mathrm{Tr}\mathcal{X} \star \mathcal{H} - \mathbb{D}(\mathcal{X} \parallel \mathcal{A})  + \mathrm{Tr}\mathcal{X} \Big\}
\end{eqnarray}

where $\mathbb{D}(\mathcal{X} \parallel  \mathcal{A})$ is the quantum relative entropy between two tensor operators. For real number $t \in [0, 1]$ and two positive-definite tensors $\mathcal{A}_1, \mathcal{A}_2$, we have

\begin{eqnarray}
\mathrm{Tr} e^{\mathcal{H} + \log (t \mathcal{A}_1 + (1-t) \mathcal{A}_2 )} &=&
\max_{\mathcal{X} \succ \mathcal{O}} \Big\{ \mathrm{Tr} \mathcal{X}\mathcal{H}
- \mathbb{D}(\mathcal{X} \parallel t \mathcal{A}_1 + (1-t) \mathcal{A}_2) + \mathrm{Tr}\mathcal{X} \Big\}  \nonumber \\
&\geq & t \max_{\mathcal{X} \succ \mathcal{O}} \Big\{ \mathrm{Tr} \mathcal{X}\mathcal{H}
- \mathbb{D}(\mathcal{X} \parallel  t \mathcal{A}_1)
+ \mathrm{Tr}\mathcal{X} \Big\} \nonumber \\
& &+ (1-t) \max_{\mathcal{X} \succ \mathcal{O}} \Big\{ \mathrm{Tr} \mathcal{X}\mathcal{H}
- \mathbb{D}(\mathcal{X}  \parallel  (1-t) \mathcal{A}_2) + \mathrm{Tr}\mathcal{X} \Big\} \nonumber \\
& = & t \mathrm{Tr}e^{\mathcal{H} + \log \mathcal{A}_1} +  (1-t) \mathrm{Tr}e^{\mathcal{H} + \log \mathcal{A}_2},
\end{eqnarray}

where the first and last equalities are obtained based on the variational formula provided by Eq. (<ref>), and the inequality is due to the joint convexity property of the
relative entropy from Leamm <ref>.

Based on Lieb's concavity theorem for tensors, we have the following corollary.

Let $\mathcal{A}$ be a fixed Hermitian tensor, and let $\mathcal{X}$ be a random Hermitian tensor, then we have

\begin{eqnarray}
\mathbb{E} \mathrm{Tr} e^{\mathcal{A} + \mathcal{X}} \leq \mathrm{Tr} e^{\mathcal{A} + \log \left( \mathbb{E} e^{\mathcal{X}} \right) }.
\end{eqnarray}

Define the random tensor $\mathcal{Y} = e^{\mathcal{X}}$, we have

\begin{eqnarray}
\mathbb{E} \mathrm{Tr} e^{\mathcal{A} + \mathcal{X}} =
\mathbb{E} \mathrm{Tr} e^{\mathcal{A} + \log \mathcal{Y} }
\leq \mathrm{Tr} e^{\mathcal{A} + \log\left( \mathbb{E} \mathcal{Y} \right) }
= \mathrm{Tr} e^{\mathcal{A} + \log \left( \mathbb{E} e^{\mathcal{X}} \right) },
\end{eqnarray}

where the inequality is based on Lieb's concavity theorem for tensors <ref> and Jensen's inequality .

§.§ Tail Bounds for Independent Sums

This section will present the tail bound for the sum of independent random tensors and several corollaries according to this tail bound for independent sums. We begin with the subadditivity lemma of tensor cumulant-generating functions.

Given a finite sequence of independent Hermitian random tensors $\{ \mathcal{X}_i \}$, we have

\begin{eqnarray}\label{eq1:lma:subadditivity of tensor cgfs}
\mathbb{E} \mathrm{Tr} \exp\left( \sum\limits_{i=1}^n t \mathcal{X}_i \right) \leq
\mathrm{Tr} \exp\left( \sum\limits_i^n \log \mathbb{E} e^{t \mathcal{X}_i} \right),~~\mbox{for $t \in \mathbb{R}$.}
\end{eqnarray}

We first define the following term for the tensor cumulant-generating function for $\mathcal{X}_i$ as:

\begin{eqnarray}
\mathbb{K}_{i}(t) &\define& \log (\mathbb{E} e^{t \mathcal{X}_i}).
\end{eqnarray}

Then, we define the Hermitian tensor $\mathcal{H}_k$ as

\begin{eqnarray}\label{eq2:lma:subadditivity of tensor cgfs}
\mathcal{H}_k(t) = \sum\limits_{i = 1}^{k-1} t \mathcal{X}_k + \sum\limits_{i = k+1}^n \mathbb{K}_{i}(t).
\end{eqnarray}

By applying Eq. (<ref>) to Theorem <ref> repeatedly for $k = 1,2,\cdots,n$, we have

\begin{eqnarray}
\mathbb{E} \mathrm{Tr} \exp\left( \sum\limits_{i=1}^n t \mathcal{X}_i \right)
&=_1& \mathbb{E}_0 \cdots \mathbb{E}_{n-1} \mathrm{Tr} \exp\left(\sum\limits_{i=1}^{n-1} t\mathcal{X}_i + t\mathcal{X}_n \right) \nonumber \\
&\leq&  \mathbb{E}_0 \cdots \mathbb{E}_{n-2} \mathrm{Tr} \exp\left( \sum\limits_{i=1}^{n-1}t \mathcal{X}_i + \log\left( \mathbb{E}_{n - 1}e^{t\mathcal{X}_n} \right) \right) \nonumber \\
& = &  \mathbb{E}_0 \cdots \mathbb{E}_{n-2} \mathrm{Tr} \exp\left( \sum\limits_{i=1}^{n-2} t \mathcal{X}_i + t \mathcal{X}_{n-1} +\mathbb{K}_{n}(t).  \right) \nonumber \\
& \leq &  \mathbb{E}_0 \cdots \mathbb{E}_{n-3} \mathrm{Tr} \exp\left( \sum\limits_{i=1}^{n-2} t \mathcal{X}_i +  \mathbb{K}_{n-1}(t) + \mathbb{K}_{n}(t)  \right) \nonumber \\
\cdots
& \leq & \mathrm{Tr} \exp\left( \sum\limits_{i = 1}^{n}  \mathbb{K}_{i}(t)  \right)
\end{eqnarray}

where the equality $=_1$ is based on the law of total expectation by defining $\mathbb{E}_i$ as the conditional expectation given $\mathcal{X}_1, \cdots, \mathcal{X}_i$.

We are ready to present the theorem for the tail bound of independent sums.

Given a finite sequence of independent Hermitian random tensors $\{ \mathcal{X}_i \}$, we have

\begin{eqnarray}\label{eq1:thm:master tail bound}
\mathrm{Pr} \left( \lambda_{\max} (\sum\limits_{i=1}^n \mathcal{X}_i) \geq \theta \right)
& \leq & \inf\limits_{t > 0} \Big\{ e^{- t \theta} \mathrm{Tr}\exp \left( \sum\limits_{i=1}^{n} \log \mathbb{E} e^{t \mathcal{X}_i}  \right) \Big\}.
\end{eqnarray}

By substituting the Lemma <ref> into the Laplace transform bound provided by the Lemma <ref>, this theorem is established.

Several useful corollaries will be provided based on Theorem <ref>.

Given a finite sequence of independent Hermitian random tensors $\{ \mathcal{X}_i \}$ with dimensions in $\mathbb{C}^{I_1 \times \cdots \times I_M \times I_1 \times \cdots \times I_M}$. If there is a function $f: (0, \infty) \rightarrow [0, \infty]$ and a sequence of non-random Hermitian tensors $\{ \mathcal{A}_i \}$ with following condition:

\begin{eqnarray}\label{eq:cond in cor 3_7}
f(t) \mathcal{A}_i \succeq  \log \mathbb{E} e^{t \mathcal{X}_i},~~\mbox{for $t > 0$.}
\end{eqnarray}

Then, for all $\theta \in \mathbb{R}$, we have

\begin{eqnarray}
\mathrm{Pr} \left( \lambda_{\max}\left(\sum\limits_{i=1}^n \mathcal{X}_i \right) \geq \theta \right)
& \leq & \mathbb{I}_{1}^M \inf\limits_{t > 0}\Big\{\exp\left[ - t \theta + f(\theta)\lambda_{\max}\left(\sum\limits_{i=1}^n \mathcal{A}_i \right) \right] \Big\}
\end{eqnarray}

From the condition provided by Eq. (<ref>) and Theorem <ref>, we have

\begin{eqnarray}
\mathrm{Pr} \left( \lambda_{\max}\left(\sum\limits_{i=1}^n \mathcal{X}_i \right) \geq \theta \right) & \leq & e^{- t \theta} \mathrm{Tr} \exp (f(\theta) \sum\limits_{i=1}^n \mathcal{A}_i) \nonumber \\
& \leq &  (I_1 \cdots I_M) e^{- t \theta} \lambda_{\max} \left( \exp (f(\theta) \sum\limits_{i=1}^n \mathcal{A}_i) \right) \nonumber \\
& = &  \mathbb{I}_1^M  e^{- t \theta} \exp\left( f(\theta) \lambda_{\max} \left(\sum\limits_{i=1}^n \mathcal{A}_i \right) \right),
\end{eqnarray}

where the second inequality holds since we bound the trace of a positive-definite tensor by the dimension size $I_1 \cdots I_M$ (the multiplication of $M$ positive integers) times the maximum eigenvalue; the last equality is based on the spectral mapping theorem since the function $f$ is nonnegative. This theorem is proved by taking the infimum over positive $t$.

Given a finite sequence of independent Hermitian random tensors $\{ \mathcal{X}_i \}$ with dimensions in $\mathbb{C}^{I_1 \times \cdots \times I_M \times I_1 \times \cdots \times I_M}$. For all $\theta \in \mathbb{R}$, we have

\begin{eqnarray}
\mathrm{Pr} \left( \lambda_{\max}\left(\sum\limits_{i=1}^n \mathcal{X}_i \right) \geq \theta \right)
& \leq & \mathbb{I}_1^M \inf\limits_{t > 0}  \Big\{  \exp\left[ - t \theta +n \log \lambda_{\max} \left( \frac{ \sum\limits_{i=1}^{n} \mathbb{E} e^{t \mathcal{X}_i}}{n}\right)  \right]  \Big\} \nonumber \\
\end{eqnarray}

From tensor logarithm given by Eq. (<ref>), we have

\begin{eqnarray}
\sum\limits_{i=1}^{n} \log \mathbb{E} e^{t \mathcal{X}_i} = n \cdot \frac{1}{n}  \sum\limits_{i=1}^{n} \log \mathbb{E} e^{t \mathcal{X}_i} \preceq n \log \left( \frac{1}{n} \sum\limits_{i=1}^{n} \mathbb{E} e^{t \mathcal{X}_i} \right),
\end{eqnarray}

and from the trace exponential monotone property provided by Eq. (<ref>), we have

\begin{eqnarray}
\mathrm{Pr} \left( \lambda_{\max}\left(\sum\limits_{i=1}^n \mathcal{X}_i \right) \geq \theta \right)
\leq  e^{- t \theta} \mathrm{Tr} \exp \left(n \log \left( \frac{1}{n} \sum\limits_{i=1}^n \mathbb{E} e^{ t \mathcal{X}_i }  \right) \right)~~~~~~~~~~~~~~~~~~ \nonumber \\
\leq  ( I_1 \cdots I_M) \inf\limits_{t > 0}  \Big\{ \exp\left[ - t \theta +n \log \lambda_{\max} \left( \frac{ \sum\limits_{i=1}^{n} \mathbb{E} e^{t \mathcal{X}_i}}{n}\right)  \right] \Big\},
\end{eqnarray}

where the last inequality holds since we bound the trace of a positive-definite tensor by the dimension size $I_1 \cdots I_M$ (the multiplication of $M$ positive integers) times the maximum eigenvalue and apply spectral mapping theorem.

§ TENSOR WITH RANDOM SERIES

A tensor Gaussian series is one of the simplest cases of a sum of independent random tensors. For scalers, a Gaussian series with real coefficients satisfies a normal-type tail bound where the variance is controlled by the sum of squares coefficients. The main purpose of the first Section <ref> is to extend this scenario to tensors. In Section <ref>, we will apply results from Section <ref> to consider Gaussian tensor with nonuniform variances. Finally, we will provide the lower and upper bounds of tensor expectation in Section <ref>.

§.§ Tensor with Gaussian and Rademacher Random Series

We begin with a lemma about moment-generating functions of Rademacher and Gaussian normal random variables.

Suppose that the tensor $\mathcal{A}$ is Hermitian.  Given a Gaussian normal random variable $\alpha$ and a Rademacher random variable $\beta$, then, we have

\begin{eqnarray}
\mathbb{E}e^{\alpha t \mathcal{A}} =  e^{t^2 \mathcal{A}^2 / 2}  \mbox{~~and~~} e^{t^2 \mathcal{A}^2 / 2} \succeq \mathbb{E}e^{\beta t \mathcal{A}},
\end{eqnarray}

where $t \in \mathbb{R}$.

For the Gaussian normal random variable, because we have

\begin{eqnarray}
\mathbb{E} (\alpha^{2n}) = \frac{ (2i)!}{i ! 2^i}  \mbox{~~and~~} \mathbb{E} (\alpha^{2i + 1}) = 0,
\end{eqnarray}

where $i = 0,1,2,\cdots$; then

\begin{eqnarray}
\mathbb{E}e^{\alpha t \mathcal{A}} &=& \mathcal{I} + \sum\limits_{i=1}^{\infty} \frac{  \mathbb{E}(\alpha^{2i}) (t \mathcal{A})^{2i}}{ (2i)! } \nonumber \\
&=& \mathcal{I} + \sum\limits_{i=1}^{\infty} \frac{ (t^2 \mathcal{A}^2/2)^i}{ i! } = e^{t^2 \mathcal{A}^2 /2}.
\end{eqnarray}

For the Rademacher random variable, we have

\begin{eqnarray}
\mathbb{E} e^{\beta  t \mathcal{A}} = \cosh (t \mathcal{A}) \preceq e^{t^2 \mathcal{A}^2/2}.
\end{eqnarray}

Therefore, this Lemma is proved.

We are ready to present the main Theorem of this section about Hermitian tensors with Gaussian and Rademacher series.

Given a finite sequence $\mathcal{A}_i$ of fixed Hermitian tensors with dimensions as $\mathbb{C}^{I_1 \times \cdots \times I_M \times I_1 \times \cdots \times I_M}$, and let $\{ \alpha_i \}$ be a finite sequence of independent normal variables. We define

\begin{eqnarray}\label{eq:4_5}
\sigma^2 &\define& \left\Vert \sum\limits_i^{n} \mathcal{A}^2_i \right\Vert,
\end{eqnarray}

then, for all $\theta \geq 0$, we have

\begin{eqnarray}\label{eq:4_3}
\mathrm{Pr}\left( \lambda_{\max} \left( \sum\limits_{i=1}^{n}\alpha_i \mathcal{A}_i \right) \geq \theta \right) \leq \mathbb{I}_1^M e^{-\frac{\theta^2 }{2 \sigma^2}},
\end{eqnarray}

\begin{eqnarray}\label{eq:4_4}
\mathrm{Pr}\left( \left\Vert \sum\limits_{i=1}^{n}\alpha_i \mathcal{A}_i \right\Vert \geq \theta \right) \leq 2 \mathbb{I}_1^M e^{-\frac{\theta^2 }{2 \sigma^2}}.
\end{eqnarray}

This theorem is also valid for a finite sequence of independent Rademacher random variables $\{ \alpha_i \}$.

Given a finite sequence of independent Gaussian or Rademacher random variables $\{ \alpha_i \}$, from Lemma <ref>, we have

\begin{eqnarray}
e^{\frac{t^2 \mathcal{A}_i^2}{2}} \succeq \mathbb{E}e^{\alpha_i t \mathcal{A}_i}.
\end{eqnarray}

From the definition in Eq. (<ref>) and Corollary <ref>, we have

\begin{eqnarray}\label{eq:4_9}
\mathrm{Pr}\left( \lambda_{\max} \left( \sum\limits_{i=1}^{n}\alpha_i \mathcal{A}_i \right) \geq \theta \right) \leq  \mathbb{I}_1^M \inf\limits_{t > 0}\Big\{ e^{- t \theta + \frac{t^2 \sigma^2}{2} } \Big\} = \mathbb{I}_1^M e^{- \frac{\theta^2}{2 \sigma^2}}.
\end{eqnarray}

This establishes  Eq. (<ref>). For  Eq. (<ref>), we have to apply following facts: $\left\Vert \mathcal{X} \right\Vert$ for any given Hermitian tensor $\mathcal{X}$. Because Gaussian and Rademacher random variables are symmetric, we have

\begin{eqnarray}
\mathrm{Pr}\left( \lambda_{\max} \left( \sum\limits_{i=1}^{n} (-\alpha_i) \mathcal{A}_i \right) \geq \theta \right) =
\mathrm{Pr}\left(  - \lambda_{\min} \left( \sum\limits_{i=1}^{n}\alpha_i \mathcal{A}_i \right) \geq \theta \right) \leq \mathbb{I}_1^M e^{- \frac{\theta^2}{2 \sigma^2}}.
\end{eqnarray}

Then, we obtain  Eq. (<ref>) as follows:

\begin{eqnarray}
\mathrm{Pr}\left( \left\Vert \sum\limits_{i=1}^{n}\alpha_i \mathcal{A}_i \right\Vert \geq \theta \right)
&=& 2 \mathrm{Pr}\left( \lambda_{\max} \left( \sum\limits_{i=1}^{n}\alpha_i \mathcal{A}_i \right) \geq \theta \right)
\nonumber \\
& \leq &  2 \mathbb{I}_1^M e^{-\frac{\theta^2 }{2 \sigma^2}}.
\end{eqnarray}

From the Hermitian dilation definition provided by Eq. (<ref>), we can extend Theorem <ref> from square Hermitian tensor to rectangular tensor by the following corollary.

Given a finite sequence $\mathcal{A}_i$ of fixed Hermitian tensors with dimensions as $\mathbb{C}^{I_1 \times \cdots \times I_M \times J_1 \times \cdots \times J_M}$, and let $\{ \alpha_i \}$ be a finite sequence of indepedent normal variables. We define

\begin{eqnarray}\
\sigma^2 &\define& \max \Bigg\{ \left\Vert \sum\limits_{i=1}^n \mathcal{A}_i \star_M \mathcal{A}^H_i \right\Vert,  \left\Vert \sum\limits_{i=1}^n \mathcal{A}^H_i \star_M \mathcal{A}_i \right\Vert\Bigg\}.
\end{eqnarray}

then, for all $\theta \geq 0$, we have

\begin{eqnarray}
\mathrm{Pr}\left( \left\Vert \sum\limits_{i=1}^n \alpha_i \mathcal{A}_i \right\Vert \geq \theta \right) \leq \prod\limits_{m=1}^M(I_m + J_m) e^{-\frac{\theta^2 }{2 \sigma^2}}.
\end{eqnarray}

This corollary is also valid for a finite sequence of independent Rademacher random variables $\{ \alpha_i \}$.

Let $\{ \alpha_i \}$ be a finite sequence of independent Gaussian or Rademacher random variables. Consider a finite sequence of random Hermitian tensors $\{ \alpha_i \mathbb{D}(\mathcal{A}_i) \}$ with dimensions $\mathbb{C}^{(I_1 + J_1) \times \cdots \times (I_M + J_M) \times (I_1 + J_1) \times \cdots \times (I_M + J_M)}$, from the spectral relation of a dilation tensor provided by Eq. (<ref>), we have

\begin{eqnarray}\label{eq1:cor:Rectangular Tensor Gaussian with Normal Series}
\left\Vert \sum\limits_i^n \alpha_i \mathcal{A}_i \right\Vert &=& \lambda_{\max} \left( \mathbb{D} \left(  \sum\limits_{i=1}^n\alpha_i \mathcal{A}_i \right)\right) = \lambda_{\max} \left(\sum\limits_{i=1}^n \alpha_i  \mathbb{D} \left(\mathcal{A}_i \right)\right).
\end{eqnarray}

Due to the following singular value relation

\begin{eqnarray}\label{eq2:cor:Rectangular Tensor Gaussian with Normal Series}
\sigma^2 &=& \left \Vert  \sum\limits_i \mathbb{D}( \mathcal{A}_i)^2\right\Vert
\left\Vert
\begin{bmatrix}
\sum\limits_{i=1}^n \mathcal{A}_i \star_M \mathcal{A}_i^H & \mathcal{O}   \\
\mathcal{O} &\sum\limits_{i=1}^n \mathcal{A}^H_i \star_M \mathcal{A}_i \\
\end{bmatrix}\right\Vert \nonumber \\
&=& \max \Bigg\{ \left\Vert\sum\limits_{i=1}^n  \mathcal{A}_i \star_M \mathcal{A}^H_i \right\Vert,  \left\Vert \sum\limits_i^{n} \mathcal{A}^H_i \star_M \mathcal{A}_i \right\Vert\Bigg\}.
\end{eqnarray}

From Eqs. (<ref>),   (<ref>) and Theorem <ref>, this corollary is proved.

§.§ A Gaussian Tensor with Nonuniform Variances

In this section, we will apply results obtained from the previous section to consider Gaussian tensor with nonuniform variances

Given a tensor $\mathcal{A} \in \mathbb{C}^{I_1 \times \cdots \times I_M \times J_1 \times \cdots \times J_M}$ and a random tensor $\mathcal{X} \in $
$ \mathbb{C}^{I_1 \times \cdots \times I_M \times J_1 \times \cdots \times J_M}$ whose entries are independent standard Gaussian normal random variables. Let $\circ$ be used to represent a Hadamard product (entrywise) between two tensors with same dimensions. Then, we have

\begin{eqnarray}
\mathrm{Pr} \left( \left\Vert \mathcal{X} \circ \mathcal{A} \right\Vert \geq \theta \right)
\leq \prod\limits_{m=1}^M (I_m + J_m) e^{-\frac{\theta^2 }{2 \sigma^2}},
\end{eqnarray}

\begin{eqnarray}
\sigma^2 = \max \Bigg\{\max_{i_1,\cdots,i_M} \left\Vert a_{i_1,\cdots,i_M,:}\right\Vert^2,
\max_{j_1,\cdots,j_M} \left\Vert a_{:,j_1,\cdots,j_M}\right\Vert^2 \Bigg\},
\end{eqnarray}

where $a_{i_1,\cdots,i_M,:}$ and $a_{:,j_1,\cdots,j_M}$ represent the row-part of the tensor $\mathcal{A}$ and column-part of the tensor $\mathcal{A}$, respectively.

Since we can decompose the tensor $\mathcal{X} \circ \mathcal{A}$ as:

\begin{eqnarray}
\mathcal{X} \circ \mathcal{A}  &=& \sum\limits_{i_1,\cdots,i_M,j_1,\cdots,j_M} x_{i_1,\cdots,i_M,j_1,\cdots,j_M} a_{i_1,\cdots,i_M,j_1,\cdots,j_M} \mathcal{E}_{i_1,\cdots,i_M,j_1,\cdots,j_M},
\end{eqnarray}

where $\mathcal{E}_{i_1,\cdots,i_M,j_1,\cdots,j_M} \in \mathbb{C}^{I_1 \times \cdots \times I_M \times J_1 \times \cdots \times J_M}$ is the tensor with all zero entries except unity at the position $i_1,\cdots,i_M,j_1,\cdots,j_M$; then, we have

\begin{eqnarray}
\sum\limits_{i_1,\cdots,i_M,j_1,\cdots,j_M} \left(a_{i_1,\cdots,i_M,j_1,\cdots,j_M} \mathcal{E}_{i_1,\cdots,i_M,j_1,\cdots,j_M} \right) \left( \overline{a_{i_1,\cdots,i_M,j_1,\cdots,j_M} \mathcal{E}_{i_1,\cdots,i_M,j_1,\cdots,j_M} } \right)  \nonumber \\
= \sum\limits_{i_1,\cdots,i_M} \left( \sum\limits_{j_1,\cdots,j_M} \left\| a_{i_1,\cdots,i_M,j_1,\cdots,j_M}\right\|^2 \right)    \mathcal{E}_{i_1,\cdots,i_M,i_1,\cdots,i_M} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \nonumber \\
= \mbox{diag} \left(\left\Vert a_{1,\cdots,1:}\right\Vert^2, \left\Vert a_{1,\cdots,2:}\right\Vert^2, \cdots, \left\Vert a_{I_1,\cdots,I_M:}\right\Vert^2\right),~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\end{eqnarray}

and, similarly,

\begin{eqnarray}
\sum\limits_{i_1,\cdots,i_M,j_1,\cdots,j_M} \left( \overline{a_{i_1,\cdots,i_M,j_1,\cdots,j_M} \mathcal{E}_{i_1,\cdots,i_M,j_1,\cdots,j_M}} \right) \left(a_{i_1,\cdots,i_M,j_1,\cdots,j_M} \mathcal{E}_{i_1,\cdots,i_M,j_1,\cdots,j_M} \right)   \nonumber \\
= \sum\limits_{j_1,\cdots,j_M} \left( \sum\limits_{i_1,\cdots,i_M} \left\| a_{i_1,\cdots,i_M,j_1,\cdots,j_M}\right\|^2 \right)    \mathcal{E}_{j_1,\cdots,j_M,j_1,\cdots,j_M} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ \nonumber \\
= \mbox{diag} \left(\left\Vert a_{:1,\cdots,1}\right\Vert^2, \left\Vert a_{:,1,\cdots,2}\right\Vert^2, \cdots, \left\Vert a_{:,J_1,\cdots,J_M}\right\Vert^2\right).~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
\end{eqnarray}

Therefore, we have

\begin{eqnarray}
\sigma^2 &=& \max\Bigg\{\mbox{diag} \left(\left\Vert a_{1,\cdots,1:}\right\Vert^2, \left\Vert a_{1,\cdots,2:}\right\Vert^2, \cdots, \left\Vert a_{I_1,\cdots,I_M:}\right\Vert^2\right), \nonumber \\
&  & \mbox{diag} \left(\left\Vert a_{:1,\cdots,1}\right\Vert^2, \left\Vert a_{:,1,\cdots,2}\right\Vert^2, \cdots, \left\Vert a_{:,J_1,\cdots,J_M}\right\Vert^2\right) \Bigg\} \nonumber \\
&=& \max \Bigg\{\max_{i_1,\cdots,i_M} \left\Vert a_{i_1,\cdots,i_M,:}\right\Vert^2,
\max_{j_1,\cdots,j_M} \left\Vert a_{:,j_1,\cdots,j_M}\right\Vert^2 \Bigg\}.
\end{eqnarray}

Finally, from Corollary <ref>, this Corollary is proved.

§.§ Lower and Upper Bounds of Tensor Expectation

Given a finite sequence $\mathcal{A}_i$ of fixed Hermitian tensors with dimensions as $\mathbb{C}^{I_1 \times \cdots \times I_M \times I_1 \times \cdots \times I_M}$, and let $\{ \alpha_i \}$ be a finite sequence of indepedent normal variables. We define following random tensor

\begin{eqnarray}
\mathcal{X} = \sum\limits_{i=1}^n \alpha_i \mathcal{A}_i.
\end{eqnarray}

From Theorem <ref>, we have

\begin{eqnarray}\label{eq:upper bound for exp tensor}
\mathbb{E}\left( \left\Vert \mathcal{X} \right\Vert^2 \right)& = & \int_0^{\infty} \mathrm{Pr}\left(
\left\Vert \mathcal{X} \right\Vert > \sqrt{t} \right) dt \leq 2 \sigma^2 \log(2 \mathbb{I}_1^M)  \nonumber \\
&  &
+ 2 (I_1\cdots I_M) \int_{2 \sigma^2 \log(2\mathbb{I}_1^M)}^{\infty} = 2 \sigma^2 \log (2 e \mathbb{I}_1^M).
\end{eqnarray}

On the other hand, from Jesen's inequality, we have

\begin{eqnarray}\label{eq:lower bound for exp tensor}
\mathbb{E}\left( \left\Vert \mathcal{X} \right\Vert^2 \right) = \mathbb{E} \left\Vert \mathcal{X}^2 \right\Vert  \geq \left\Vert \mathbb{E}(\mathcal{X}^2) \right\Vert =  \left\Vert \sum\limits_{i=1}^n \mathcal{A}^2_i\right\Vert = \sigma^2.
\end{eqnarray}

From both Eqs. (<ref>) and (<ref>),
we have following relation:

\begin{eqnarray}
c \sigma \leq \mathbb{E} \left\Vert \mathcal{X} \right\Vert \leq \sigma \sqrt{2 \log (2 e \mathbb{I}_1^M)}.
\end{eqnarray}

This shows that the tensor variance parameter $\sigma^2$ controls the expected norm $ \mathbb{E} \left\Vert \mathcal{X} \right\Vert$ with square root of logarithmic function for the tensor dimensions.

§ TENSOR CHERNOFF BOUNDS

The traditional Chernoff bounds concern the sum of independent, nonnegative, and uniformly bounded random variables. In this work, we will try to extend such Chernoff bounds under the scenario of random tensors.

§.§ Tensor Chernoff Bounds Derivations

We begin to present a Lemma about the semidefinite relation for the tensor moment-generating function of a random positive semidefinite contraction.

Given a random positive semifefinite tensor with $\lambda_{\max}(\mathcal{X})\leq 1$, then, for any $t \in \mathbb{R}$, we have

\begin{eqnarray}
\mathcal{I}+ (e^t - 1) \mathbb{E} \mathcal{X} \succeq \mathbb{E} e^{t \mathcal{X}}.
\end{eqnarray}

Consider a convex function $g(x) = e^{t x}$, we have

\begin{eqnarray}
1 + (e^t - 1)x \geq g(x),
\end{eqnarray}

where $x \in [0,1]$. Since the eigenvalues of the random tensor $\mathcal{X}$ lie in the interval $[0, 1]$, from Eq. (<ref>), we obtain

\begin{eqnarray}
\mathcal{I} + (e^t - 1)\mathcal{X} \succeq e^{t \mathcal{X}}.
\end{eqnarray}

Then, this Lemma is proved by taking the expectation with respect to the random tensor $\mathcal{X}$.

Given two real values $a, b \in [0, 1]$, we define binary information divergence of $a$ and $b$, expressed by $\mathfrak{D}(a || b)$, as

\begin{eqnarray}\label{eq:def of binary info div}
\mathfrak{D}(a || b) \define a \log \frac{a}{b} + (1-a) \frac{1-a}{1-b}.
\end{eqnarray}

We are ready to present tensor Chernoff inequality.

Consider a sequence $\{ \mathcal{X}_i  \in \mathbb{C}^{I_1 \times \cdots \times I_M  \times I_1 \times \cdots \times I_M } \}$ of independent, random, Hermitian tensors that satisfy

\begin{eqnarray}
\mathcal{X}_i \succeq \mathcal{O} \mbox{~~and~~} \lambda_{\max}(\mathcal{X}_i) \leq 1
\mbox{~~ almost surely.}
\end{eqnarray}

Define following two quantaties:

\begin{eqnarray}
\overline{\mu}_{\max} \define \lambda_{\max}\left( \frac{1}{n} \sum\limits_{i=1}^{n} \mathbb{E} \mathcal{X}_i \right) \mbox{~~and~~}
\overline{\mu}_{\min} \define \lambda_{\min}\left( \frac{1}{n} \sum\limits_{i=1}^{n} \mathbb{E} \mathcal{X}_i \right),
\end{eqnarray}

then, we have following two inequalities:

\begin{eqnarray}\label{eq:Chernoff I Upper Bound}
\mathrm{Pr} \left( \lambda_{\max}\left( \frac{1}{n}\sum\limits_{i=1}^{n} \mathcal{X}_i \right) \geq \theta \right) \leq \mathbb{I}_1^M e^{- n \mathfrak{D}(\theta || \overline{\mu}_{\max} )},\mbox{~~ for $\overline{\mu}_{\max} \leq \theta \leq 1$;}
\end{eqnarray}

\begin{eqnarray}\label{eq:Chernoff I Lower Bound}
\mathrm{Pr} \left( \lambda_{\min}\left( \frac{1}{n}\sum\limits_{i=1}^{n} \mathcal{X}_i \right) \leq \theta \right) \leq \mathbb{I}_1^M e^{- n \mathfrak{D}(\theta || \overline{\mu}_{\min} )},\mbox{~~ for $0 \leq \theta \leq \overline{\mu}_{\min}$.}
\end{eqnarray}

From Lemma <ref>, we have

\begin{eqnarray}
\mathcal{I} + f(t) \mathbb{E} \mathcal{X}_i \succeq \mathbb{E} e^{t \mathcal{X}_i},
\end{eqnarray}

where $f(t) \define e^t -1$ for $t > 0$.

By applying Corollary <ref>, we obtain

\begin{eqnarray}\label{eq1:Chernoff I Upper Bound proof}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right) \geq \alpha \right) &\leq& \mathbb{I}_1^M \exp\left( - t \alpha + n \log\lambda_{\max}\left( \frac{1}{n} \sum\limits_{i=1}^{n} \left( \mathcal{I} + f(t) \mathbb{E} \mathcal{X}_i \right) \right) \right) \nonumber \\
&= &  \mathbb{I}_1^M \exp\left( - t \alpha+ n \log\lambda_{\max}\left(  \mathcal{I} + f(t)  \frac{1}{n} \sum\limits_{i=1}^{n} \mathbb{E} \mathcal{X}_i \right) \right) \nonumber \\
&=& \mathbb{I}_1^M \exp\left( - t \alpha + n \log \left(1 + f(t) \overline{\mu}_{\max} \right) \right) .
\end{eqnarray}

The last equality follows from the definition of $\overline{\mu}_{\max}$ and the eigenvalue map properties. When the value $t$ at the right-hand side of  Eq. (<ref>) is

\begin{eqnarray}\label{eq2:Chernoff I Upper Bound proof}
t = \log \frac{\alpha}{1 - \alpha} - \log \frac{\overline{\mu}_{\max}}{1 - \overline{\mu}_{\max}},
\end{eqnarray}

we can achieve the tightest upper bound at Eq. (<ref>). By substituting the value $t$ in Eq. (<ref>) into Eq. (<ref>) and change the variable $\alpha \rightarrow n \theta$, Eq. (<ref>) is proved. The next goal is to prove Eq. (<ref>).

If we apply Lemma <ref> to the sequence $\{- \mathcal{X}_i \}$, we have

\begin{eqnarray}
\mathcal{I} - g(t) \mathbb{E} \mathcal{X}_i \succeq \mathbb{E} e^{t (-\mathcal{X}_i)},
\end{eqnarray}

where $g(t) \define 1 - e^t$ for $t > 0$.

By applying Corollary <ref> again, we obtain

\begin{eqnarray}\label{eq1:Chernoff I Lower Bound proof}
\mathrm{Pr} \left( \lambda_{\min}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right) \leq \alpha \right) &=& \mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \left( - \mathcal{X}_i \right)\right) \geq \alpha \right)
\nonumber \\
&\leq& \mathbb{I}_1^M \exp\left( t \alpha + n \log\lambda_{\max}\left( \frac{1}{n} \sum\limits_{i=1}^{n} \left( \mathcal{I} - g(t) \mathbb{E} \mathcal{X}_i \right) \right) \right) \nonumber \\
&=_1 &  \mathbb{I}_1^M \exp\left( t \alpha + n \log \left( 1 -f(t)  \lambda_{\min}\left(    \frac{1}{n} \sum\limits_{i=1}^{n} \mathbb{E} \mathcal{X}_i \right) \right) \right) \nonumber \\
&=& \mathbb{I}_1^M \exp\left( t \alpha + n \log \left(1 - g(t) \overline{\mu}_{\min} \right) \right),
\end{eqnarray}

where we apply the relation $\lambda_{\min}( -\frac{1}{n} \sum\limits_{i=1}^{n} \mathbb{E} \mathcal{X}_i  ) = -\lambda_{\max} (\frac{1}{n} \sum\limits_{i=1}^{n} \mathbb{E} \mathcal{X}_i )$ at the equality $=_1$. When the value $t$ at the right-hand side of  Eq. (<ref>) is

\begin{eqnarray}\label{eq2:Chernoff I Lower Bound proof}
t = log \frac{\overline{\mu}_{\max}}{1 - \overline{\mu}_{\max}} -  \log \frac{\alpha}{1 - \alpha},
\end{eqnarray}

we can achieve the tightest upper bound at Eq. (<ref>). By substituting the value $t$ in Eq. (<ref>) into Eq. (<ref>) and change the variable $\alpha \rightarrow n \theta$, Eq. (<ref>) is proved also.

The tensor Chernoff bounds discussed at Theorem <ref> is not related to $\mu_{\max}$ and $\mu_{\min}$ directly. Following theorem is another version of tensor Chernoff bounds to associate the probability range in terms of $\mu_{\max}$ and $\mu_{\min}$ directly and this format of tensor Chernoff bounds are easier to be applied.

Consider a sequence $\{ \mathcal{X}_i  \in \mathbb{C}^{I_1 \times \cdots \times I_M  \times I_1 \times \cdots \times I_M } \}$ of independent, random, Hermitian tensors that satisfy

\begin{eqnarray}
\mathcal{X}_i \succeq \mathcal{O} \mbox{~~and~~} \lambda_{\max}(\mathcal{X}_i) \leq T
\mbox{~~ almost surely.}
\end{eqnarray}

Define following two quantaties:

\begin{eqnarray}
\mu_{\max} \define \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathbb{E} \mathcal{X}_i \right) \mbox{~~and~~}
\mu_{\min} \define \lambda_{\min}\left( \sum\limits_{i=1}^{n} \mathbb{E} \mathcal{X}_i \right),
\end{eqnarray}

then, we have following two inequalities:

\begin{eqnarray}\label{eq:Chernoff II Upper Bound}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right) \geq (1+\theta) \mu_{\max} \right) \leq \mathbb{I}_1^M \left(\frac{e^{\theta}}{ (1 + \theta)^{1 + \theta}  }\right)^{\mu_{\max}/T} ,\mbox{~~ for $\theta \geq 0$;}
\end{eqnarray}

\begin{eqnarray}\label{eq:Chernoff II Lower Bound}
\mathrm{Pr} \left( \lambda_{\min}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right) \leq (1 - \theta) \mu_{\min} \right) \leq \mathbb{I}_1^M \left(\frac{e^{-\theta}}{ (1 - \theta)^{1 - \theta}  }\right)^{\mu_{\min}/T} ,\mbox{~~ for $\theta \in [0,1]$.}
\end{eqnarray}

Without loss of generality, we can assume $T=1$ in our proof. From  Eq. (<ref>) and the inequality $\log(1 + x) \leq x$ for $x > -1$, we have

\begin{eqnarray}\label{eq1:Chernoff II Upper Bound}
\mathrm{Pr}\left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right) \geq t \right) \leq \mathbb{I}_1^{M}\exp(- \delta t + f(\delta) \mu_{\max})
\end{eqnarray}

By selecting $\delta = \log (1 + \theta)$ and $t \rightarrow (1 + \theta) \mu_{\max}$, we can establish  Eq. (<ref>).

From  Eq. (<ref>) and the inequality $\log(1 + x) \leq x$ for $x > -1$, we have

\begin{eqnarray}\label{eq1:Chernoff II Lower Bound}
\mathrm{Pr}\left( \lambda_{\min}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right) \leq t \right) \leq \mathbb{I}_1^{M}\exp(- \delta t - f(\delta) \mu_{\min})
\end{eqnarray}

By selecting $\delta =- \log (1 - \theta)$ and $t \rightarrow (1 - \theta) \mu_{\min}$, we can establish  Eq. (<ref>). Therefore, this theorem is proved.

§.§ Application of Tensor Chernoff Bounds

Consider a general random tensor $\mathcal{X} \in \mathbb{C}^{I_1 \times \cdots \times I_M \times J_1 \times \cdots \times J_N}$, we can express the $\mathcal{X}$ as

\begin{eqnarray}
\mathcal{X} = [x_{1}, x_{2}, \cdots, x_{J_1\cdots J_N}],
\end{eqnarray}

where $x_i$ is a family of independent random tensors in $ \mathbb{C}^{I_1 \times \cdots \times I_M}$ (vector part in $\mathcal{X}$. The squared norm of $\mathcal{X}$ can be expressed as

\begin{eqnarray}\label{eq1:Remark 5_4}
\left\Vert \mathcal{X} \right\Vert^2 = \lambda_{\max}(\mathcal{X} \star_N \mathcal{X}^H) = \lambda_{\max}(\sum\limits_{i=1}^{J_1\cdots J_N} x_i \star_0 \overline{x_i}).
\end{eqnarray}

Similarly, for the minimum singular value of the tensor $\mathcal{X}$, we have

\begin{eqnarray}\label{eq2:Remark 5_4}
\mbox{Minimum singular value of $\mathcal{X}$} = \lambda_{\min}(\mathcal{X} \star_N \mathcal{X}^H) = \lambda_{\min}(\sum\limits_{i=1}^{J_1\cdots J_N} x_i \star_0 x_i^H).
\end{eqnarray}

From tensor Chernoff bounds provided by Theorem <ref>, we can bound both Eqs. (<ref>) and (<ref>).

Another application of tensor Chernoff bounds is to estimate the expectation of the maximum eigenvalue of independent sum of random tensors.

Consider a sequence $\{ \mathcal{X}_i  \in \mathbb{C}^{I_1 \times \cdots \times I_M  \times I_1 \times \cdots \times I_M } \}$ of independent, random, Hermitian tensors that satisfy

\begin{eqnarray}
\mathcal{X}_i \succeq \mathcal{O} \mbox{~~and~~} \lambda_{\max}(\mathcal{X}_i) \leq T
\mbox{~~ almost surely.}
\end{eqnarray}

Then, we have

\begin{eqnarray}\label{eq1:cor:Bounds for the Maximum Eigenvalue}
\mu_{\max} \leq \mathbb{E} \lambda_{\max}\left( \sum\limits_{i=1}^n \mathcal{X}_i \right) \leq C \mathbb{I}_1^M e^{- \mu_{\max}/T},
\end{eqnarray}

where the constant value of $C$ is about 10.28.

The lower bound at Eq. (<ref>) is true from the convexity of the function $\mathcal{A} \rightarrow \lambda_{\max}(\mathcal{A})$ and the Jensen's inequality.

For the upper bound, we have

\begin{eqnarray}\label{eq2:cor:Bounds for the Maximum Eigenvalue}
\mathbb{E} \lambda_{\max}\left( \sum\limits_{i=1}^n \mathcal{X}_i \right)
&=& \int_{0}^{\infty} \mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^n \mathcal{X}_i \right)  \geq t \right) d t  \nonumber \\
&\leq_1& \int_{0}^{\infty} \mathbb{I}_1^{M}\exp(- \delta t + (e^{\delta} - 1) \mu_{\max}/T)dt \nonumber \\
&=&  \frac{e^{e^{\delta}}}{\delta} \mathbb{I}_1^M e^{- \mu_{\max}/T} \nonumber \\
&\leq&  \frac{e^{e^{\delta_{opt}}}}{\delta_{opt}} \mathbb{I}_1^M e^{- \mu_{\max}/T}
= C \mathbb{I}_1^M e^{- \mu_{\max}/T},
\end{eqnarray}

where the inequality $\leq_1$ comes from  Eq. (<ref>) with the scaling factor $T$. If we select $\theta$ as the solution of the following relation $e^{\delta_{opt}} = \frac{1}{\delta_{opt}}$ to minimize the right-hand side of Eq. (<ref>),  we have the desired upper bound when $\delta_{opt} \approx = 0.56699$. This corollary is proved.

§ TENSOR BERNSTEIN BOUNDS

For random variables, Bernstein inequalities give the upper tail of a sum of
independent, zero-mean random variables that are either bounded or subexponential. In this section, we wish to extend Bernstein bounds for a sum of zero-mean random tensors.

§.§ Tensor Bernstein Bounds Derivation

We will condier bounded Tensor Bernstein bounds first by considering the bounded Bernstein moment-generating function with the following Lemma.

Given a random Hermitian tensor $\mathcal{X} \in \mathbb{C}^{I_1 \times \cdots \times I_M  \times I_1 \times \cdots \times I_M }$ that satisfies:

\begin{eqnarray}\label{eq1:lam:Bounded Bernstein mgf}
\mathbb{E} \mathcal{X} = 0 \mbox{~~and~~} \lambda_{\max}(\mathcal{X} ) \leq 1
\mbox{~~almost surely.}
\end{eqnarray}

Then, we have

\begin{eqnarray}
e^{  (e^t - t - 1) \mathbb{E}(\mathcal{X}^2)}   \succeq  \mathbb{E}e^{t \mathcal{X}}
\end{eqnarray}

where $t > 0$.

If we define a real function $g(x) \define \frac{e^{t x} - t x - 1}{x^2}$, it is easy to see that this function $g(x)$ is an increasing function for $0 < x \leq 1$. From Eq (<ref>), we have

\begin{eqnarray}\label{eq2:lam:Bounded Bernstein mgf}
g(\mathcal{X}) \preceq g(1) \mathcal{I}.
\end{eqnarray}

Moreover, we also have

\begin{eqnarray}\label{eq3:lam:Bounded Bernstein mgf}
e^{t \mathcal{X}} &=& \mathcal{I} + t \mathcal{X} + g(\mathcal{X}) \star_M \mathcal{X}^2 \nonumber \\
&\preceq&  \mathcal{I} + t \mathcal{X} + g(1) \mathcal{X}^2,
\end{eqnarray}

where the $\preceq$ comes from Eq. (<ref>). By taking the expectation for both sides of Eq. (<ref>), we then obtain

\begin{eqnarray}
\mathbb{E}e^{t \mathcal{X}} &\preceq& \mathcal{I} + g(1) \mathbb{E}\left( \mathcal{X}^2\right) \preceq e^{g(1)\mathbb{E}\left( \mathcal{X}^2\right) } \nonumber \\
&=&   e^{ (e^t - t - 1) \mathbb{E}(\mathcal{X}^2)}.
\end{eqnarray}

This lemma is established.

We are ready to present the Tensor Bernstein bounds for random tensors with bounded $\lambda_{\max}$.

Given a finite sequence of independent Hermitian tensors $\{ \mathcal{X}_i  \in \mathbb{C}^{I_1 \times \cdots \times I_M  \times I_1 \times \cdots \times I_M } \}$ that satisfy

\begin{eqnarray}\label{eq1:thm:Bounded Tensor Bernstein}
\mathbb{E} \mathcal{X}_i = 0 \mbox{~~and~~} \lambda_{\max}(\mathcal{X}_i) \leq T
\mbox{~~almost surely.}
\end{eqnarray}

Define the total varaince $\sigma^2$ as: $\sigma^2 \define \left\Vert \sum\limits_i^n \mathbb{E} \left( \mathcal{X}^2_i \right) \right\Vert$.

Then, we have following inequalities:

\begin{eqnarray}\label{eq2:thm:Bounded Tensor Bernstein}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right)\geq \theta \right) \leq \mathbb{I}_1^M \exp \left( \frac{-\theta^2/2}{\sigma^2 + T\theta/3}\right);
\end{eqnarray}

\begin{eqnarray}\label{eq3:thm:Bounded Tensor Bernstein}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right)\geq \theta \right) \leq \mathbb{I}_1^M \exp \left( \frac{-3 \theta^2}{ 8 \sigma^2}\right)~~\mbox{for $\theta \leq \sigma^2/T$};
\end{eqnarray}

\begin{eqnarray}\label{eq4:thm:Bounded Tensor Bernstein}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right)\geq \theta \right) \leq \mathbb{I}_1^M \exp \left( \frac{-3 \theta}{ 8 T } \right)~~\mbox{for $\theta \geq \sigma^2/T$}.
\end{eqnarray}

Without loss of generality, we can assume that $T=1$ since the summands are 1-homogeneous and the variance is 2-homogeneous. From Lemma <ref>, we have

\begin{eqnarray}\label{eq5:thm:Bounded Tensor Bernstein}
\mathbb{E}e^{t \mathcal{X}_i} \preceq e^{(e^t - t- 1) \mathbb{E}(\mathcal{X}_i^2)} \mbox{~~ for $t > 0$.}
\end{eqnarray}

By applying Corollary <ref>, we then have

\begin{eqnarray}\label{eq6:thm:Bounded Tensor Bernstein}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right)\geq \theta \right) &\leq &\mathbb{I}_1^{M} \exp\left(- t \theta + (e^t - t - 1) \lambda_{\max}\left( \sum\limits_{i=1}^n \mathbb{E} \left( \mathcal{X}^2_i \right)\right)\right) \nonumber \\
&=& \mathbb{I}_1^{M} \exp \left( - t \theta + \sigma^2(e^t - t - 1)   \right).
\end{eqnarray}

The right-hand side of Eq. (<ref>) can be minimized by setting $t = \log (1 + \theta/\sigma^2)$. Substitute such $t$ and simplify the right-hand side of Eq. (<ref>), we obtain  Eq. (<ref>).

For $\theta \leq \sigma^2/T$, we have

\begin{eqnarray}
\frac{1}{\sigma^2 + T\theta/3} \geq \frac{1}{\sigma^2 + T (\sigma^2/T) /3} = \frac{3}{4\sigma^2},
\end{eqnarray}

then, we obtain  Eq. (<ref>). Correspondingly, for $\theta \geq \sigma^2/T$, we have

\begin{eqnarray}
\frac{\theta}{\sigma^2 + T\theta/3} \geq \frac{\sigma^2/T}{\sigma^2 + T (\sigma^2/T)/3} = \frac{3}{4 T},
\end{eqnarray}

and, we obtain  Eq. (<ref>) also.

The following theorem <ref> is the extension of the theorem <ref> by allowing the moments of the random tensors to grow at a controlled rate. We have to prepare subexponential Bernstein moment-generating function Lemma first for later proof of Theorem <ref>

Suppose that $\mathcal{X}$ is a random Hermitian tensor that satisfies

\begin{eqnarray}\label{eq1:lem:Subexponential Bernstein mgf}
\mathbb{E} \mathcal{X} = 0 \mbox{~~and~~} \mathbb{E}(\mathcal{X}^p)  \preceq \frac{p! \mathcal{A}^2}{2}
\mbox{for $p=2,3,4,\cdots$.}
\end{eqnarray}

Then, we have

\begin{eqnarray}
\exp\left(\frac{t^2 \mathcal{A}^2}{2(1 - t)}\right)   \succeq  \mathbb{E}e^{t \mathcal{X}},
\end{eqnarray}

where $0 < t < 1$.

From Tayler series of the tensor exponential expansion, we have

\begin{eqnarray}
\mathbb{E}e^{t \mathcal{X}} &=& \mathcal{I} + t \mathbb{E}\mathcal{X} + \sum\limits_{p=2}^{\infty} \frac{t^p \mathbb{E}(\mathcal{X}^p)}{p!} \preceq \mathcal{I}+ \sum\limits_{p=2}^{\infty} \frac{t^p \mathcal{A}^2}{2} \nonumber \\
&=& \mathcal{I} + \frac{t^2 \mathcal{A}^2}{2 (1-t)} \preceq \exp\left(\frac{t^2 \mathcal{A}^2}{2(1 - t)} \right),
\end{eqnarray}

therefore, this Lemma is proved.

Given a finite sequence of independent Hermitian tensors $\{ \mathcal{X}_i  \in \mathbb{C}^{I_1 \times \cdots \times I_M  \times I_1 \times \cdots \times I_M } \}$ that satisfy

\begin{eqnarray}\label{eq1:thm:Subexponential Tensor Bernstein}
\mathbb{E} \mathcal{X}_i = 0 \mbox{~~and~~} \mathbb{E} (\mathcal{X}^p_i) \preceq \frac{p! T^{p-2} }{2} \mathcal{A}_i^2,
\end{eqnarray}

where $p = 2,3,4,\cdots$.

Define the total varaince $\sigma^2$ as: $\sigma^2 \define \left\Vert \sum\limits_i^n \mathcal{A}_i^2 \right\Vert$.

Then, we have following inequalities:

\begin{eqnarray}\label{eq2:thm:Subexponential Tensor Bernstein}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right)\geq \theta \right) \leq \mathbb{I}_1^M \exp \left( \frac{-\theta^2/2}{\sigma^2 + T\theta}\right);
\end{eqnarray}

\begin{eqnarray}\label{eq3:thm:Subexponential Tensor Bernstein}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right)\geq \theta \right) \leq \mathbb{I}_1^M \exp \left( \frac{-\theta^2}{ 4 \sigma^2}\right)~~\mbox{for $\theta \leq \sigma^2/T$};
\end{eqnarray}

\begin{eqnarray}\label{eq4:thm:Subexponential Tensor Bernstein}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right)\geq \theta \right) \leq \mathbb{I}_1^M \exp \left( \frac{- \theta}{ 4 T } \right)~~\mbox{for $\theta \geq \sigma^2/T$}.
\end{eqnarray}

Without loss of generality, we can assume that $T=1$. From Lemma <ref>, we have

\begin{eqnarray}
\mathbb{E}e^{t \mathcal{X}_i} \preceq e^{\frac{t^2 \mathcal{A}^2_i}{2(1-t)}},
\end{eqnarray}

where $0 < t < 1$.

By applying Corollary <ref>, we then have

\begin{eqnarray}\label{eq6:thm:Subexponential Tensor Bernstein}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right)\geq \theta \right) &\leq &\mathbb{I}_1^{M} \exp\left(- t \theta + \frac{t^2}{2(1-t)} \lambda_{\max}\left( \sum\limits_{i=1}^n \mathcal{A}_i^2  \right)\right) \nonumber \\
&=& \mathbb{I}_1^{M} \exp \left( - t \theta + \frac{\sigma^2 t^2}{2(1-t)}  \right).
\end{eqnarray}

The right-hand side of Eq. (<ref>) can be minimized by setting $t = \frac{\theta}{\theta + \sigma^2}$. Substitute such $t$ and simplify the right-hand side of Eq. (<ref>), we obtain  Eq. (<ref>).

For $\theta \leq \sigma^2/T$, we have

\begin{eqnarray}
\frac{1}{\sigma^2 + T\theta} \geq \frac{1}{\sigma^2 + T (\sigma^2/T )} = \frac{1}{2\sigma^2},
\end{eqnarray}

then, we obtain  Eq. (<ref>). Similarly, for $\theta \geq \sigma^2/T$, we have

\begin{eqnarray}
\frac{\theta}{\sigma^2 + T\theta} \geq \frac{\sigma^2/T}{\sigma^2 + T( \sigma^2/T) } = \frac{1}{2T},
\end{eqnarray}

therefore, we also obtain  Eq. (<ref>).

§.§ Application of Tensor Bernstein Bounds

The tensor Bernstein bounds can also be extended to rectangular tensors by dilation. Consider a sequence of tensors $\{\mathcal{Y}_i\} \in \mathbb{C}^{I_1 \times \cdots \times I_M \times J_1 \times \cdots \times J_M}$ satisfy following:

\begin{eqnarray}
\mathbb{E} \mathcal{Y}_i = \mathcal{O} \mbox{~~and~~} \left\Vert \mathcal{Y}_i \right\Vert \leq T \mbox{~~almost surely.}
\end{eqnarray}

If the variance $\sigma^2$ is expressed as:

\begin{eqnarray}
\sigma^2 \define  \max \Bigg\{ \left\Vert \sum\limits_{i=1}^n \mathcal{Y}_i \star_M \mathcal{Y}^H_i \right\Vert,  \left\Vert \sum\limits_{i=1}^n \mathcal{Y}^H_i \star_M \mathcal{Y}_i \right\Vert\Bigg\},
\end{eqnarray}

we have

\begin{eqnarray}
\mathrm{Pr} \left( \left\Vert \sum\limits_{i=1}^{n} \mathcal{Y}_i \right\Vert \geq \theta \right) \leq \prod_{m=1}^M (I_m + J_m) \exp \left( \frac{-\theta^2/2}{\sigma^2 + T\theta/3}\right);
\end{eqnarray}

from Theorem <ref>.

Another application of tensor Bernstein bounds is to get upper and lower Bounds for the maximum eigenvalue with subexponential tensors. This application can relax the corollary <ref> conditions by allowing the moments of the random tensors to grow at a controlled rate.

Consider a sequence $\{ \mathcal{X}_i  \in \mathbb{C}^{I_1 \times \cdots \times I_M  \times I_1 \times \cdots \times I_M } \}$ of independent, random, Hermitian tensors that satisfy

\begin{eqnarray}
\mathcal{X}_i \succeq \mathcal{O} \mbox{~~and~~} \mathbb{E} (\mathcal{X}^p_i) \preceq \frac{p! T^{p-2} }{2} \mathcal{A}_i^2,
\end{eqnarray}

and $\sigma^2 \define \left\Vert \sum\limits_{i=1}^n \mathcal{A}^2_i \right\Vert$. Then, we have

\begin{eqnarray}\label{eq1:cor:Bounds for the Maximum Eigenvalue Subexponential Tensors}
\mu_{\max} \leq \mathbb{E} \lambda_{\max}\left( \sum\limits_{i=1}^n \mathcal{X}_i \right) \leq
2\mathbb{I}_1^M\left(\sigma \mathfrak{G}\left(\frac{\sigma}{2T} \right) + 2T e^{-\frac{\sigma^2}{4T^2}}\right),
\end{eqnarray}

where $\mathfrak{G}(\frac{\sigma}{2T}) \define \int_0^{\frac{\sigma}{2T}} e^{-s^2} ds$.

The lower bound at Eq. (<ref>) is true from the convexity of the function $\mathcal{A} \rightarrow \lambda_{\max}(\mathcal{A})$ and the Jensen's inequality.

For the upper bound, we have

\begin{eqnarray}\label{eq2:cor:Bounds for the Maximum Eigenvalue Subexponential Tensors}
\mathbb{E} \lambda_{\max}\left( \sum\limits_{i=1}^n \mathcal{X}_i \right)
&=& \int_{0}^{\infty} \mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^n \mathcal{X}_i \right)  \geq t \right) d t  \nonumber \\
&\leq_1& \mathbb{I}_1^{M}  \int_{0}^{\frac{\sigma^2}{T}}\exp \left(- \frac{t^2}{4 \sigma^2} \right)   dt +  \mathbb{I}_1^{M}  \int_{\frac{\sigma^2}{T}}^{\infty}\exp \left(- \frac{t}{4 T} \right)   dt \nonumber \\
&=&  2\mathbb{I}_1^M\left(\sigma \mathfrak{G}\left(\frac{\sigma}{2T} \right) + 2T e^{-\frac{\sigma^2}{4T^2}}\right),
\end{eqnarray}

where the inequality $\leq_1$ comes from the Eqs. (<ref>) and (<ref>). This corollary is proved by introducing Gaussian integral function $\mathfrak{G}(x) \define \int_0^{x} e^{-s^2} ds$.

§ MARTINGALE DEVIATION BOUNDS

In this section, we introduce concepts about tensor martingales in Section <ref>, and extend Hoeffding, Azuma, and McDiarmid inequalities to tensors context in Section <ref>.

§.§ Tensor Martingales

Necessary definitions about tensor martingales will be provided here for later tensor martingale deviation bounds derivations. Let $(\Omega, \mathfrak{F}, \mathbb{P})$ be a master probability space. Consider a filtration $\{ \mathfrak{F}_i \}$ contained in the master sigma algebra as:

\begin{eqnarray}
\mathfrak{F}_0 \subset \mathfrak{F}_1 \subset \mathfrak{F}_2 \subset \cdots
\subset \mathfrak{F}_{\infty} \subset \mathfrak{F}.
\end{eqnarray}

Given such a filtration, we define the conditional expectation $\mathbb{E}_i[ \cdot ] \define \mathbb{E}_i[ \cdot | \mathfrak{F}_i]$. A sequence $\{ \mathcal{Y}_i \}$ of random tensors is called adapted to the filtration when each tensor $\mathcal{Y}_i$ is measurable with respect to $\mathfrak{F}_i$. We can think that an adapted sequence is one where the present depends only on the past.

An adapted sequence $\{ \mathcal{X}_i \}$ of Hermitian tensors is named as a tensor martingale when

\begin{eqnarray}
\mathbb{E}_{i-1} \mathcal{X}_i = \mathcal{X}_{i-1} \mbox{~~~and~~~} \mathbb{E} \left\Vert \mathcal{X}_i \right\Vert < \infty,
\end{eqnarray}

where $i = 1, 2, 3, \cdots$. We obtain a scalar martingale if we track any fixed entry of a tensor martingale $\{ \mathcal{X}_i \}$. Given a tensor martingale $\{ \mathcal{X}_i \}$, we can construct the following new sequence of tensors

\begin{eqnarray}
\mathcal{Y}_i \define \mathcal{X}_i  - \mathcal{X}_{i-1}  \mbox{~~for $i=1, 2, 3,\cdots$}
\end{eqnarray}

We then have $\mathbb{E}_{i-1}\mathcal{Y}_i = \mathcal{O}$.

§.§ Tensor Martingale Deviation Bounds

Two Lemmas should be presented first before presenting tensor martingale deviation bounds and their proofs.

Let $\mathcal{A}$ be a fixed Hermitian tensor, and let $\mathcal{X}$ be a random Hermitian tensor with $\mathbb{E}\mathcal{E} = \mathcal{O}$. Then

\begin{eqnarray}
\mathbb{E} \mathrm{Tr}e^{\mathcal{A} + \mathcal{X}} \leq \mathbb{E} \mathrm{Tr}e^{\mathcal{A} + 2\beta \mathcal{X}},
\end{eqnarray}

where $\beta$ is Rademacher random variable.

Build an independent copy random tensor $\mathcal{Y}$ from $\mathcal{X}$, and let $\mathbb{E}_{\mathcal{Y}}$ denote the expectation with respect to the new random tensor $\mathcal{Y}$. Then, we have

\begin{eqnarray}
\mathbb{E} \mathrm{Tr}e^{\mathcal{A} + \mathcal{X}} =
\mathbb{E} \mathrm{Tr}e^{\mathcal{A} + \mathcal{X} - \mathbb{E}_{\mathcal{Y}} \mathcal{Y}}  \leq \mathbb{E} \mathrm{Tr}e^{\mathcal{A} + \mathcal{X} - \mathcal{Y}}
= \mathbb{E} \mathrm{Tr}e^{\mathcal{A} + \beta( \mathcal{X} - \mathcal{Y})},
\end{eqnarray}

where the first equality uses $\mathbb{E}_{\mathcal{Y}} \mathcal{Y} = \mathcal{O}$; the inequality uses the convexity of the trace exponential with Jensen's inequality; finally, the last equality comes from that the random tensor $\mathcal{X} - \mathcal{Y}$ is a symmetric random tensor and Rademacher is also a symmetric random variable.

This Lemma is established by the following:

\begin{eqnarray}
\mathbb{E} \mathrm{Tr}e^{\mathcal{A} + \mathcal{X}} &\leq& \mathbb{E} \mathrm{Tr} \left( e^{\mathcal{A}/2 + \beta \mathcal{X}}  e^{\mathcal{A}/2 - \beta \mathcal{Y}}\right) \nonumber \\
& \leq & \left( \mathbb{E} \mathrm{Tr} e^{\mathcal{A} + 2 \beta \mathcal{X}}\right)^{1/2}  \left( \mathbb{E} \mathrm{Tr} e^{\mathcal{A} - 2 \beta \mathcal{Y}}\right)^{1/2}
= \mathbb{E} \mathrm{Tr}e^{\mathcal{A} + 2 \beta \mathcal{X}},
\end{eqnarray}

where the first inequality comes from tensor Golden-Thompson inequality [6], the second inequality comes from the Cauchy-Schwarz inequality, and the last identity follows from that the two factors are identically distributed.

The other Lemma is to provide the tensor cumulant-generating function of a symetrized random tensor.

Given that $\mathcal{X}$ is a random Hermitian tensor and $\mathcal{A}$ is a fixed Hermitian tensor that satisfies $\mathcal{X}^2 \preceq \mathcal{A}^2$. Then, we have

\begin{eqnarray}
\log \mathbb{E} \left [ e^{2 \beta t  \mathcal{X}} | \mathcal{X} \right] \preceq 2 t^2 \mathcal{A}^2,
\end{eqnarray}

where $\beta$ is a Rademacher random variable.

From Lemma <ref>, we have

\begin{eqnarray}
\mathbb{E} \left [ e^{2 \beta t \mathcal{X}} | \mathcal{X} \right] \preceq  e^{2 t ^2 \mathcal{X}^2}.
\end{eqnarray}

And, from the monotone property of logarithm, we also have

\begin{eqnarray}
\log \mathbb{E} \left [ e^{2 t \theta \mathcal{X}} | \mathcal{X} \right] \preceq  2t^2 \mathcal{X}^2 \preceq 2 t^2 \mathcal{A}^2~~\mbox{for $t \in \mathbb{R}$}.
\end{eqnarray}

Therefore, this Lemma is proved.

At this point, we are ready to present tensor martingale deviation bounds. In probability theory, the Azuma inequality for a scaler martingale gives normal concentration about its mean value, and the deviation is controlled by the total maximum squared of the difference sequence. Below is a tensor extension.

Given a finite adapted sequence of Hermitian tensors $\{ \mathcal{X}_i  \in \mathbb{C}^{I_1 \times \cdots \times I_M  \times I_1 \times \cdots \times I_M } \}$ and a fixed sequence of Hermitian tensors $\{ \mathcal{A}_i \}$ that satisfy

\begin{eqnarray}\label{eq1:thm:Tensor Azuma}
\mathbb{E}_{i-1} \mathcal{X}_i = 0 \mbox{~~and~~} \mathcal{X}^2_i \preceq  \mathcal{A}^2_i \mbox{almost surely},
\end{eqnarray}

where $i = 1,2,3,\cdots$.

Define the total varaince $\sigma^2$ as: $\sigma^2 \define \left\Vert \sum\limits_i^n \mathcal{A}_i^2 \right\Vert$.

Then, we have following inequalities:

\begin{eqnarray}\label{eq2:thm:Tensor Azuma}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right)\geq \theta \right) \leq \mathbb{I}_1^M e^{-\frac{\theta^2}{8 \sigma^2}}.
\end{eqnarray}

Define the filtration $\mathfrak{F}_i \define \mathfrak{F}(\mathcal{X}_1, \cdots, \mathcal{X}_i)$ for the process $\{\mathcal{X}_i \}$. Then, we have

\begin{eqnarray}\label{eq3:thm:Tensor Azuma}
\mathbb{E} \mathrm{Tr} \exp\left( \sum\limits_{i=1}^n t \mathcal{X}_i \right) &=& \mathbb{E}   \left( \mathbb{E}\left( \mathrm{Tr}\exp\left( \sum\limits_{i=1}^{n-1} t \mathcal{X}_i+ t \mathcal{X}_n \right) | \mathfrak{F}_{n}\right) | \mathfrak{F}_{n-1}\right) \nonumber \\
& \leq & \mathbb{E}   \left( \mathbb{E}\left( \mathrm{Tr}\exp\left( \sum\limits_{i=1}^{n-1} t \mathcal{X}_i+ 2 \beta t \mathcal{X}_n \right) | \mathfrak{F}_{n}\right) | \mathfrak{F}_{n}\right) \nonumber \\
& \leq &  \mathbb{E}   \left( \mathrm{Tr}\exp\left( \sum\limits_{i=1}^{n-1} t \mathcal{X}_i+ \log \mathbb{E} \left( e^{2 \beta t \mathcal{X}_n} | \mathfrak{F}_{n}\right)  \right) | \mathfrak{F}_{n}\right) \nonumber \\
& \leq & \mathbb{E} \mathrm{Tr} \exp \left( \sum\limits_{i=1}^{n-1} t \mathcal{X}_i +2 t^2 \mathcal{A}_n^2 \right),
\end{eqnarray}

where the first equality comes from the total expectation property of conditional expectation; the first inequality comes from Lemma <ref>; the second inequality comes from Corollary <ref> and the relaxation the connection to the larger algebra set $\mathfrak{F}_n$; finally, the last inequality requires Lemma <ref>.

If we continue the iteration procedure based on Eq. (<ref>), we have

\begin{eqnarray}\label{eq4:thm:Tensor Azuma}
\mathbb{E} \mathrm{Tr} \exp \left( \sum\limits_{i=1}^n t \mathcal{X}_i  \right)
\leq \mathrm{Tr} \exp \left( 2t^2 \sum\limits_{i=1}^n \mathcal{A}^2_i \right),
\end{eqnarray}

then apply Eq. (<ref>) into Lemma <ref>, we obtain

\begin{eqnarray}
\mathrm{Pr} \left( \lambda_{\max}\left( \sum\limits_{i=1}^{n} \mathcal{X}_i \right)\geq \theta \right) &\leq&  \inf\limits_{t > 0} \Big\{ e^{- t \theta} \mathbb{E} \mathrm{Tr}\exp \left( \sum\limits_{i=1}^n t \mathcal{X}_i \right) \Big\} \nonumber \\
& \leq &  \inf\limits_{t > 0} \Big\{ e^{- t \theta} \mathbb{E} \mathrm{Tr}\exp \left( 2 t^2 \sum\limits_{i=1}^n  \mathcal{A}^2_i \right) \Big\} \nonumber \\
& \leq & \inf\limits_{t > 0} \Big\{ e^{- t \theta} \mathbb{I}_{1}^M
\lambda_{\max} \left(  \exp \left( 2t^2 \sum\limits_{i=1}^{n} \mathcal{A}^2_i \right)\right) \Big\} \nonumber \\
& = &\inf\limits_{t > 0} \Big\{ e^{- t \theta} \mathbb{I}_{1}^M
\exp \left( 2t^2 \sigma^2 \right) \Big\} \nonumber \\
& \leq &  \mathbb{I}_{1}^M  e^{-\frac{\theta^2}{8 \sigma^2}},
\end{eqnarray}

where the third inequality utilizes $\lambda_{\max}$ to bound trace, the equality applies the definition of $\sigma^2$ and spectral mapping theorem, finally, we select $t = \frac{\theta}{4 \sigma^2}$ to minimize the upper bound to obtain this theorem.

If we add extra assumption that the summands are independent, Theorem <ref> gives a tensor extension of Hoeffding’s inequality. If we apply Theorem <ref> to a Hermitian tensor martingale, we will have following corollary.

Given a Hermitian tensor martingale $\{\mathcal{Y}_i: i=1,2,\cdots,n \} \in $
$\mathbb{C}^{I_1 \times \cdots \times I_M \times I_1 \times \cdots \times I_M}$, and let $\mathcal{X}_i$ be the difference sequence of $\{\mathcal{Y}_i \}$, i.e., $\mathcal{X}_i \define \mathcal{Y}_i - \mathcal{Y}_{i-1}$ for $i = 1,2,3, \cdots$. If the difference sequence satisfies

\begin{eqnarray}\label{eq1:cor:7.2}
\mathbb{E}_{i-1} \mathcal{X}_i = 0 \mbox{~~and~~} \mathcal{X}^2_i \preceq  \mathcal{A}_i \mbox{almost surely},
\end{eqnarray}

where $i = 1,2,3,\cdots$ and the total varaince $\sigma^2$ is defined as as: $\sigma^2 \define \left\Vert \sum\limits_i^n \mathcal{A}_i^2 \right\Vert$. Then, we have

\begin{eqnarray}
\mathrm{Pr} \left( \lambda_{\max}\left( \mathcal{Y}_n -  \mathbb{E} \mathcal{Y}_n \right)\geq \theta \right) \leq \mathbb{I}_1^M e^{-\frac{\theta^2}{8 \sigma^2}}.
\end{eqnarray}

In the scalar setting, McDiarmid inequality can be treated as a corollary of Azuma’s inequality. McDiarmid inequality states that a function of independent random variables exhibits normal concentration about its mean, and the variance
depends on the function value sensitivity with respect to the input. A version
of the bounded differences inequality is still valid in tensor context.

Given a set of $n$ independent random variables, i.e. $\{X_i: i = 1,2,\cdots n\}$, and let
$F$ be a Hermitian tensor-valued function that maps these $n$ random variables to a Hermitian tensor of dimension within $\mathbb{C}^{I_1 \times \cdots \times I_M  \times I_1 \times \cdots \times I_M }$. Consider a sequence of Hermitian tensors $\{ \mathcal{A}_i \}$ that satisfy

\begin{eqnarray}\label{eq1:thm:Tensor McDiarmid}
\left( F(x_1,\cdots,x_i,\cdots,x_n)  -  F(x_1,\cdots,x'_i,\cdots,x_n) \right)^2 \preceq \mathcal{A}^2_i,
\end{eqnarray}

where $x_i, x'_i \in X_i$ and $1 \leq i \leq n$. Define the total variance $\sigma^2$ as: $\sigma^2 \define \left\Vert \sum\limits_i^n \mathcal{A}_i^2 \right\Vert $.

Then, we have following inequality:

\begin{eqnarray}\label{eq2:thm:Tensor McDiarmid}
\mathrm{Pr} \left( \lambda_{\max}\left( F(x_1,\cdots,x_n) - \mathbb{E}F(x_1,\cdots,x_n )\right)\geq \theta \right) \leq \mathbb{I}_1^M e^{-\frac{\theta^2}{8 \sigma^2}}.
\end{eqnarray}

We define following random tensors $\mathcal{Y}_i$ for $0 \leq i \leq n$ as:

\begin{eqnarray}\label{eq3:thm:Tensor McDiarmid}
\mathcal{Y}_i \define \mathbb{E} \left( F(x_1,\cdots,x_n) | X_1, \cdots, X_i \right) = \mathbb{E}_{X_{i+1}}  \mathbb{E}_{X_{i+2}} \cdots  \mathbb{E}_{X_{n}} F(x_1,\cdots,x_n),
\end{eqnarray}

where $ \mathbb{E}_{X_{i+1}}$ is the expectation with respect to the random variable $X_{i+1}$. The constructed sequence $\mathcal{Y}_i$ forms a martingale. The associated difference sequence with respect to $\mathcal{Y}$, denoted as $\{ \mathcal{Z}_i \}$, can be stated as:

\begin{eqnarray}\label{eq4:thm:Tensor McDiarmid}
\mathcal{Z}_i  \define \mathcal{Y}_i  - \mathcal{Y}_{i-1} =
\mathbb{E}_{X_{i+1}}  \mathbb{E}_{X_{i+2}} \cdots  \mathbb{E}_{X_{n}}\left(
F(x_1,\cdots,x_n) -   \mathbb{E}_{X_{i}}  F(x_1,\cdots,x_n ) \right).
\end{eqnarray}

Because $(x_1,\cdots,x_i)$ forms a filtration with respect to $i$, we have

\begin{eqnarray}
\mathbb{E}_{X_{i-1}}\mathcal{Y}_i &=& \mathbb{E}_{X_{i-1}} \left( \mathbb{E}_{X_{i+1}}  \mathbb{E}_{X_{i+2}} \cdots  \mathbb{E}_{X_{n}} F(x_1,\cdots,x_n) | X_{i-1} \right) \nonumber \\
&=& \mathbb{E}_{X_{i-1}} \left( \mathbb{E}_{X_{i}}  \mathbb{E}_{X_{i+1}} \cdots  \mathbb{E}_{X_{n}} F(x_1,\cdots,x_n) | X_{i-1} \right) = \mathbb{E}_{X_{i-1}}\mathcal{Y}_{i-1},
\end{eqnarray}

\begin{eqnarray}\label{eq5:thm:Tensor McDiarmid}
\mathbb{E}_{X_{i-1}} \mathcal{Z}_i
&=& \mathbb{E}_{X_{i-1}}\mathcal{Y}_i - \mathbb{E}_{X_{i-1}}\mathcal{Y}_{i-1} = \mathcal{O}
\end{eqnarray}

Let $X'_i$ be an independent copy of $X_i$, and construct the following two random vectors:

\begin{eqnarray}
\mathbf{x}' &=&  (X_1,\cdots,X_{i-1},X'_i,X_{i+1},\cdots,X_n), \nonumber \\
\mathbf{x}  &=&  (X_1,\cdots,X_{i-1},X_i,X_{i+1},\cdots,X_n).
\end{eqnarray}

Since $\mathbb{E}_{X_i} F(\mathbf{x}) =
\mathbb{E}_{X'_i} F(\mathbf{x}')$, we have

\begin{eqnarray}\label{eq6:thm:Tensor McDiarmid}
\mathcal{Z}_i = \mathbb{E}_{X_{i+1}}  \mathbb{E}_{X_{i+2}} \cdots  \mathbb{E}_{X_{n}}  \mathbb{E}_{X'_{i}}  \left(
F(\mathbf{x}) -    F(\mathbf{x}') \right).
\end{eqnarray}

Then, $\left(  F(\mathbf{x}) -    F(\mathbf{x}')  \right)^2 \preceq \mathcal{A}^2_i$ from requirement provided by Eq. (<ref>). We have following upper bound

\begin{eqnarray}\label{eq7:thm:Tensor McDiarmid}
\mathbb{E}_{X_{i+1}}  \mathbb{E}_{X_{i+2}} \cdots  \mathbb{E}_{X_{n}}  \mathbb{E}_{X'_{i}}  \left(
F(\mathbf{x}) -    F(\mathbf{x}') \right)^2 \preceq \mathcal{A}^2_i.
\end{eqnarray}

Therefore, from conditions provided by Eq. (<ref>) and Eq. (<ref>), this theorem is proved by applying Corollary <ref> to the martingale $\{\mathcal{Y}_i\}$.

§ CONCLUSION

In this paper, we generalize Lapalce transform method and Lieb's concavity theorem from matrices to tensors, and apply these techniques to extend following classical bounds from the scalar to the tensor situation: Chernoff, Azuma, Hoeffding, Bennett, Bernstein, and McDiarmid. The purpose of these probability inequalities tries to identify large-deviation behavior of the extreme eigenvalue of the sums of random tensors. Tail bounds for the norm of a sum of random rectangular tensors follow as an immediate corollary. Finally, we also apply the proof techniques developed at this work to study tensor-valued martingales.

[1]
Rudolf Ahlswede and Andreas Winter, Addendum to: “Strong converse for
identification via quantum channels” [IEEE Trans. Inform. Theory
48 (2002), no. 3, 569–579; MR1889969 (2003d:94069)], IEEE Trans.
Inform. Theory 49 (2003), no. 1, 346. 1966716

[2]
Anima Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade, and Matus Telgarsky,
Tensor decompositions for learning latent variable models (A survey
for ALT), Proceedings of International Conference on Algorithmic Learning
Theory, Springer, Oct. 2015, pp. 19–38.

[3]
O. Bohigas, M.-J. Giannoni, and C. Schmit, Characterization of chaotic
quantum spectra and universality of level fluctuation laws, Phys. Rev. Lett.
52 (1984), no. 1, 1–4. 730191

[4]
M. G. Bulmer, Principles of statistics, second ed., Dover Publications,
Inc., New York, 1979. 559726

[5]
Shih Yu Chang, Tensor Multivariate Trace Inequalities and their
Applications, arXiv e-prints (2020), arXiv:2010.02152.

[6]
Shih Yu Chang, Tensor multivariate trace inequalities and their
applications, 2020.

[7]
Pattrawut Chansangiam, A survey on operator monotonicity, operator
convexity, and operator means, Int. J. Anal. (2015), Art. ID 649839, 8.

[8]
Yannan Chen, Deren Han, and Liqun Qi, New ALS methods with
extrapolating search directions and optimal step size for complex-valued
tensor decompositions, IEEE Transactions on Signal Processing 59
(2011), no. 12, 5888–5898.

[9]
Lu-Bin Cui, Chuan Chen, Wen Li, and Michael K. Ng, An eigenvalue problem
for even order tensors with its applications, Linear Multilinear Algebra
64 (2016), no. 4, 602–621. 3479021

[10]
André LF de Almeida, Gérard Favier, and João Cesar M Mota,
Constrained tensor modeling approach to blind multiple-antenna CDMA
schemes, IEEE Transactions on Signal Processing 56 (2008), no. 6,

[11]
Weiyang Ding, Liqun Qi, and Yimin Wei, Fast Hankel tensor-vector
product and its application to exponential data fitting, Numer. Linear
Algebra Appl. 22 (2015), no. 5, 814–832. 3395816

[12]
Edward G. Effros, A matrix convexity approach to some celebrated quantum
inequalities, Proc. Natl. Acad. Sci. USA 106 (2009), no. 4,
1006–1008. 2475796

[13]
Xiao Fu, Kejun Huang, Wing-Kin Ma, Nicholas D Sidiropoulos, and Rasmus Bro,
Joint tensor factorization and outlying slab suppression with
applications, IEEE Transactions on Signal Processing 63 (2015),
no. 23, 6315–6328.

[14]
Herman H. Goldstine and John von Neumann, Numerical inverting of matrices
of high order. II, Proc. Amer. Math. Soc. 2 (1951), 188–202.

[15]
Razvan Gurau, Random tensors, Oxford University Press, Oxford, 2017.

[16]
Frank Hansen and Gert Kjaergȧrd Pedersen, Jensen's inequality for
operators and Löwner's theorem, Math. Ann. 258 (1981/82),
no. 3, 229–241. 649196

[17]
Wassily Hoeffding, Probability inequalities for sums of bounded random
variables, J. Amer. Statist. Assoc. 58 (1963), 13–30. 144363

[18]
Tai-Xiang Jiang, Michael K Ng, Xi-Le Zhao, and Ting-Zhu Huang, Framelet
representation of tensor nuclear norm for third-order tensor completion,
IEEE Transactions on Image Processing 29 (2020), 7233–7244.

[19]
Tiefeng Jiang and Junshan Xie, Limiting behavior of largest entry of
random tensor constructed by high-dimensional data, J. Theoret. Probab.
33 (2020), no. 4, 2380–2400. 4166204

[20]
Igor R. Klebanov and Grigory Tarnopolsky, Uncolored random tensors, melon
diagrams, and the Sachdev-Ye-Kitaev models, Phys. Rev. D 95
(2017), no. 4, 046004, 13. 3783911

[21]
Ching-Yun Ko, Kim Batselier, Luca Daniel, Wenjian Yu, and Ngai Wong, Fast
and accurate tensor completion with total variation regularized tensor
trains, IEEE Transactions on Image Processing (2020).

[22]
Tamara G Kolda and Brett W Bader, Tensor decompositions and
applications, SIAM Review 51 (2009), no. 3, 455–500.

[23]
Vincent Lahoche and Dine Ousmane Samary, Reliability of the local
truncations for the random tensor models renormalization group flow, Phys.
Rev. D 102 (2020), no. 5, 056002, 30. 4163785

[24]
Maolin Liang and Bing Zheng, Further results on Moore-Penrose
inverses of tensors with application to tensor nearness problems, Comput.
Math. Appl. 77 (2019), no. 5, 1282–1293. 3913666

[25]
Elliott H. Lieb, Convex trace functions and the Wigner-Yanase-Dyson
conjecture, Advances in Math. 11 (1973), 267–288. 332080

[26]
Seyedmahdad Mirsamadi and John HL Hansen, A generalized nonnegative
tensor factorization approach for distant speech recognition with distributed
microphones, IEEE/ACM Transactions on Audio, Speech, and Language Processing
24 (2016), no. 10, 1721–1731.

[27]
Damien Muti and Salah Bourennane, Survey on tensor signal algebraic
filtering, Signal Processing 87 (2007), no. 2, 237–249.

[28]
Dimitri Nion and Nicholas D Sidiropoulos, Tensor algebra and
multidimensional harmonic retrieval in signal processing for MIMO radar,
IEEE Transactions on Signal Processing 58 (2010), no. 11,

[29]
Liqun Qi, Haibin Chen, and Yannan Chen, Tensor eigenvalues and their
applications, Advances in Mechanics and Mathematics, vol. 39, Springer,
Singapore, 2018. 3791481

[30]
Liqun Qi and Ziyan Luo, Tensor analysis, Society for Industrial and
Applied Mathematics, Philadelphia, PA, 2017, Spectral theory and special
tensors. 3660696

[31]
Yanning Shen, Brian Baingana, and Georgios B Giannakis, Tensor
Decompositions for Identifying Directed graph Topologies and
Tracking Dnamic Networks, IEEE Transactions on Signal Processing
65 (2017), no. 14, 3675–3687.

[32]
Yanning Shen, Xiao Fu, Georgios B Giannakis, and Nicholas D Sidiropoulos,
Topology identification of directed graphs via joint diagonalization of
correlation matrices, IEEE Transactions on Signal and Information Processing
over Networks 6 (2020), 271–283.

[33]
Nicholas D Sidiropoulos, Rasmus Bro, and Georgios B Giannakis, Parallel
factor analysis in sensor array rrocessing, IEEE Transactions on Signal
Processing 48 (2000), no. 8, 2377–2388.

[34]
Nicholas D Sidiropoulos, Lieven De Lathauwer, Xiao Fu, Kejun Huang, Evangelos E
Papalexakis, and Christos Faloutsos, Tensor decomposition for signal
processing and machine learning, IEEE Transactions on Signal Processing
65 (2017), no. 13, 3551–3582.

[35]
Joel A. Tropp, User-friendly tail bounds for sums of random matrices,
Found. Comput. Math. 12 (2012), no. 4, 389–434. 2946459

[36]
Antonia M Tulino, Sergio Verdú, and Sergio Verdu, Random matrix
theory and wireless communications, Now Publishers Inc, 2004.

[37]
Stephen J Turnovsky, The stability properties of optimal economic
policies, The American Economic Review 64 (1974), no. 1, 136–148.

[38]
Roman Vershynin, Concentration inequalities for random tensors,
Bernoulli 26 (2020), no. 4, 3139–3162. 4140540

[39]
Gilles Wainrib and Jonathan Touboul, Topological and dynamical complexity
of random neural networks, Physical review letters 110 (2013),
no. 11, 118101.

[40]
Xuezhong Wang, Maolin Che, and Yimin Wei, Neural networks based approach
solving multi-linear systems with m-tensors, Neurocomputing 351
(2019), 33–42.

[41]
Qiang Wu, Liqing Zhang, and Guangchuan Shi, Robust multifactor speech
feature extraction based on gabor analysis, IEEE Transactions on Audio,
Speech, and Language Processing 19 (2010), no. 4, 927–936.

[42]
Hong-Ru Xu, Dong-Hui Li, and Shui-Lian Xie, An equivalent tensor equation
to the tensor complementarity problem with positive semi-definite
$Z$-tensor, Optim. Lett. 13 (2019), no. 4, 685–694. 3947912

We are grateful to reviewers' precious comments.