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

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

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.
• 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 '19 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 '19 at 13:47
• how do you convert this result back a concentration for $X^2$ after centering (subtracting its mean)? The upper side is trivial as $X^2-E(X^2)>=t$ implies $X^2>t$, but what about its lower tail? Also, I got a bound of $P(X\ge x)\le exp(-x^2/(8n^L)$ using the Taylor expansion of $exp$ and then Markov, I did it because it doesn't need the rounding, but which one is stronger? This bound or the one you've given here? – kvphxga Aug 29 '19 at 16:00
• (i) The expectation of the product of powers with integer exponents of independent Rademacher random variables can only be $1$ (if all the exponents are even) or $0$ (otherwise). So, such an expectation cannot be negative. (ii) $\prod_{j=1}^{2p}$ was missing/misplaced in two places; these typos are now corrected. (iii) At this point, I don't have good ideas about bounding the lower tail. – Iosif Pinelis Aug 30 '19 at 15:29