0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – kvphxga Jul 31 at 1:42
  • $\begingroup$ 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. $\endgroup$ – Iosif Pinelis Jul 31 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.