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\*}



Sketching Frobenius norm of a tensor with a rank-1 random tensor
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](https://en.wikipedia.org/wiki/Eaton%27s_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. 


