Concentration inequalities for random tensors (Q2203634)

Let \(x_1,x_2,\ldots\) be independent random vectors in \(\mathbb{R}^n\) whose coordinates are independent random variables with zero mean and unit variance, and let \(X=x_1\otimes\cdots\otimes x_d\), a random tensor in \(\mathbb{R}^{n^d}\). The author proves two concentration inequalities for \(X\). Firstly, in the case where the \(x_k\) are bounded almost surely, it is shown that for a convex and Lipschitz function \(f\), and all \(0\leq t\leq2(\mathbb{E}|f(X)|^2)^{1/2}\), we have \[ \mathbb{P}\left(\big|f(X)-\mathbb{E}f(X)\big|>t\right)\leq2\exp\left(-\frac{ct^2}{dn^{d-1}\|f\|^2_{Lip}}\right)\,, \] for some constant \(c>0\) depending on the bound for the \(x_k\). Secondly, in the case where the \(x_k\) are sub-Gaussian, it is shown that for a linear operator \(A\) taking values in a Hilbert space \(H\), and all \(0\leq t\leq2\|A\|_{HS}\), we have \[ \mathbb{P}\left(\big|\|AX\|_H-\|A\|_{HS}\big|\geq t\right)\leq2\exp\left(-\frac{ct^2}{dn^{d-1}\|A\|^2_{op}}\right)\,, \] where \(c>0\) again depends on the \(x_k\), and where \(\|A\|_{HS}\) and \(\|A\|_{op}\) are the Hilbert-Schmidt and operator norms of \(A\), respectively. As an application of this latter concentration bound, the author shows that random tensors are well conditioned; that is, if \(d=o(\sqrt{n/\log(n)})\) then with high probability \((1-o(1))n^d\) independent copies of \(X\) are far from linearly dependent.