Sketching Frobenius norm of a tensor with a rank-1 random tensor

Question

Let $A\in\mathbb{R}^{n^k}$ be a $k$-dimensional tensor with $n$ elements along each dimension. Moreover 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, and 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? As it is shown at the bottom of the post, $\mathbb{E} X^2=\lVert A\rVert_F^2$, i.e., the sum of the square of all elements in the tensor. How can the tails of the distribution around the mean be bounded: $P\left(|X^2-\mathbb{E} X^2|\ge x \right)$? Alternatively, as is typical in many concentration bounds, can the probability be bounded as an $\epsilon$-deviation from the mean: $P\left(|X^2-\mathbb{E} X^2|\ge \epsilon \left(\mathbb{E} X^2\right) \right)$?

Follow-up as @IosifPinelis has pointed out in their answer, moments of $X$, $\mathbb{E} X^{2p}$, can be effectively bounded, leading to a tail bound roughly of type $P(X\ge x)\le \exp(-x^{2/k})$. However, the main question was to bound the tail bounds of $X^2$ around its mean, which is $P(|X^2-\mathbb{E} X^2| \ge x)$. Taking a similar approach as @IosifPinelis, one could try to bound the tails of $Y:=X^2 - \lVert A\rVert_F^2$ by bounding its moments $\mathbb{E} Y^p$. Is that a sound approach?

Context: given that tails are light, this can be seen as sketching the Frobenius norm of a tensor. More so to the point, if $A,B$ are tensors, if we compute $v=\langle A,u_1\otimes \dots\otimes u_k\rangle$ and $w=\langle B,u_1\otimes \dots\otimes u_k\rangle$, then $\mathbb{E}(v-w)^2 = \lVert A-B\rVert_F^2$ and if the concentration is high, it can be seen as a distance-preserving embedding of tensors into the $L^2$-norm. The reason for choosing a rank-1 random tensor as opposed to a fully random one, which makes the bound trivial to compute, is that for certain applications the product with a rank-1 tensor can be computed much more efficiently and hence the sketching is faster to compute.

Derivation of $\mathbb{E} X^2$: \begin{align*} \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} u_{1,i_1}\dots u_{k,i_k} u_{1,j_1}\dots u_{k,j_k}\\ &= \sum_{i_1,j_1, \dots,i_k,j_k\le n} 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}) &&\rhd \text{L.o.E, and $u_i$s independence}\\ &= \sum_{i_1,\dots,i_k\le n} a_{i_1,\dots,i_k}^2 && \rhd i_m\neq j_m: \mathbb{E} u_{i_m}u_{j_m} = 0\\ &= \sum_{i_1,\dots,i_k\le n} a_{i_1,\dots,i_k}^2=\lVert A \rVert_F^2 && \rhd \mathbb{E} u_{i_m}^2 = \mathrm{Var}(u_{i_m}) = 1 \end{align*}

Answer 1

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_{j\le2p;\ i_{1,j},\dots,i_{k,j}\le n}\, \Big(\prod_{j=1}^{2p}\,a_{i_{1,j},\dots,i_{k,j}}\Big)\, E\prod_{j=1}^{2p}(u_{1,i_{1,j}}\dots u_{k,i_{k,j}}) \\ &\le\sum_{j\le2p;\ i_{1,j},\dots,i_{k,j}\le n}\, E\prod_{j=1}^{2p}\,(u_{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 $E\prod_{j=1}^{2p}(u_{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.