# Concentration tensor product with a rank-1 random tensor with sub-Gaussian elements

Suppose $$A\in\mathbb{R}^{n^k}$$ is a $$k$$-dimensional tensor with $$n$$ elements along each dimension. Morover suppose $$u_1,u_2,\dots,u_k\sim\text{Unif}(\pm1)^n$$ are $$n$$ dimensional vectors with each of their components drawn iid from Rademacher distribution. More generally, you can think of their components as zero-mean, unit-variance iid sub-Gaussian random variables. Moroever, let $$U:=u_1\otimes u_2 \otimes \dots \otimes u_k$$ be a rank-1 random tensor constructed from these vectors. Finally, let $$X=\langle A, U \rangle$$, in which by $$\langle, \rangle$$ we simply mean the inner product of tensor if we flatten them as vectors.

Question: What is the concentration of $$X^2$$ around its mean? Does $$X$$ have exponentially light tails? It is easy to show that $$\mathbb{E}[X^2]$$ is simply the sum of squares of all elements of $$A$$, using linearity of expectation and the fact that $$u_i$$s have zero-mean unit variance elements (the proof given at the end of the post). Therefore, if $$X^2$$ has a distribution with exponentially light tails, the product would in effect sketch the sum of squares of elements of tensor $$A$$.

Derivation of $$\mathbb{E} X^2$$: $$\mathbb{E} X^2 = \mathbb{E}\sum_{i_1,j_1, \dots,i_k,j_k} a_{i_1, \dots,i_k} a_{j_1,\dots,j_k} \Pi_{m=1}^k (u_{m,i_m} u_{m,j_m})$$ Because of linearity of expectation and independence of $$u_i$$ vectors from each other we have:

$$\mathbb{E} X^2 = \sum_{i_1,j_1, \dots,i_k,j_k} a_{i_1, \dots,i_k} a_{j_1,\dots,j_k} \Pi_{m=1}^k \mathbb{E}(u_{m,i_m} u_{m,j_m})$$ Now, for all the terms that have $$i_m\neq j_m$$ based on indep $$\mathbb{E}(u_{m,i_m} u_{m,j_m}) = \mathbb{E}u_{m,i_m} \mathbb{E}u_{m,j_m} = 0\cdot 0 = 0$$ Therefore, only terms that satisfy $$i_m=j_m$$ for all $$m\in[k]$$ remain, and for those terms we have: $$\Pi_{m=1}^k\mathbb{E}(u_{m,i_m} u_{m,j_m}) = \Pi_{m=1}^k\mathbb{E}(u_{m,i_m})^2 = \Pi_{m=1}^k\text{Var}(u_{m,i_m})=\Pi_{m=1}^k 1 = 1$$ And therefore: $$\mathbb{E} X^2 = \sum_{i_1,j_1, \dots,i_k,j_k} a_{i_1, \dots,i_k}^2$$ which is the result we wanted.

## 1 Answer

The tail probability $$P(X\ge x)$$ is in general like $$e^{-x^{2/k}}$$ for large $$x>0$$.

Indeed, we have $$\begin{equation*} X=\sum_{i_1,\dots,i_k\le n} a_{i_1,\dots,i_k}u_{1,i_1}\dots u_{k,i_k}, \end{equation*}$$ where the $$u_{i,j}$$'s are assumed to be independent Rademacher random variables. Without loss of generality, $$|a_{i_1,\dots,i_k}|\le1$$ for all $$i_1,\dots,i_k$$ in $$[n]:=\{1,\dots,n\}$$. So, for any natural $$p$$ and $$Z\sim N(0,1)$$, \begin{align*} EX^{2p}&=E\prod_{j=1}^{2p}\,\sum_{i_{1,j},\dots,i_{k,j}\le n} a_{i_{1,j},\dots,i_{k,j}}u_{1,i_{1,j}}\dots u_{k,i_{k,j}} \\ &=\sum_{i_{1,j},\dots,i_{k,j}\le n}\, \prod_{j=1}^{2p}\, a_{i_{1,j},\dots,i_{k,j}}\, Eu_{1,i_{1,j}}\dots u_{k,i_{k,j}} \\ &\le\sum_{i_{1,j},\dots,i_{k,j}\le n}\, \prod_{j=1}^{2p}\, Eu_{1,i_{1,j}}\dots u_{k,i_{k,j}} \\ &=E\Big(\sum_{i_1,\dots,i_k\le n} u_{1,i_1}\dots u_{k,i_k}\Big)^{2p} \\ &=E\Big(\sum_{i_1\le n} u_{1,i_1}\cdots \sum_{i_k\le n} u_{k,i_k}\Big)^{2p} \\ &=E\Big(\sum_{i_1\le n} u_{1,i_1}\Big)^{2p}\cdots E\Big(\sum_{i_k\le n} u_{k,i_k}\Big)^{2p} \\ &=\Big(E\Big(\sum_{i\le n} u_{1,i}\Big)^{2p}\Big)^k \\ &\le\Big(E(Z\sqrt n)^{2p}\Big)^k \\ &\le (np)^{kp}. \end{align*} The first inequality in the above multiline display follows because $$|a_{i_1,\dots,i_k}|\le1$$ and $$Eu_{1,i_{1,j}}\dots u_{k,i_{k,j}}$$ is either $$0$$ or $$1$$ and hence $$\ge0$$; the penultimate inequality there holds by the Whittle--Haagerup inequality; and the last inequality follows because $$EZ^{2p}=(2p-1)!!\le p^p$$, as easy to check by induction.

So, by Markov's inequality, for $$x>0$$ $$\begin{equation*} P(X\ge x)\le R(p):=EX^{2p}/x^{2p}\le e^{g(p)}, \end{equation*}$$ where $$\begin{equation*} g(p):=g_x(p):=-p\ln(x^2)+kp\ln(np). \end{equation*}$$ The minimizer of $$g(p)$$ in all real $$p>0$$ is $$p_x:=x^{2/k}/(en)$$, and $$R(p_x)=\exp\{-kx^{2/k}/(en)\}$$. However, $$p_x$$ does not have to be an integer. Rounding it to the closest integer and using the facts that $$g'(p_x)=0$$ and $$g''(p)=k/p\to0$$ for $$p\in[p_x-1/2,p_x+1/2]$$ and $$x\to\infty$$, we conclude that $$\begin{equation*} P(X\ge x)\le \exp\{-kx^{2/k}/(en)\}(1+o(1)) \end{equation*}$$ as $$x\to\infty$$, as claimed. Also, looking back at the above proof, it is easy to see that the obtained upper bound on $$P(X\ge x)$$ cannot be substantially improved in general.

• Is there a way bound $\mathbb{E}(|X|^p)$ for general $p$ (not limited to integers)? In particular, I'm curious if the result on Khintchine inequality with both $L^1$ and $L^2$-norms terms, can be generalized to the tensor case? (talking about this: en.wikipedia.org/wiki/Khintchine_inequality#Generalizations) – kvphxga Jul 31 at 1:42
• I can show that, again in the Rademacher case, $$E|X|^q\le(nq)^{kq}\exp\Big\{\frac k{4\max(1,q-2)}\Big\}$$ for all real $q\ge2$. However, in more ways than one, it is better to post additional questions separately. – Iosif Pinelis Jul 31 at 13:47