Concentration inequalities for random tensors

By Roman Vershynin. Bernoulli, 2019

51 citations recorded by the source corpus.

We show how to extend several basic concentration inequalities for simple random tensors $X = x_1 \otimes \cdots \otimes x_d$ where all $x_k$ are independent random vectors in $\mathbb{R}^n$ with independent coefficients. The new results have optimal dependence on the dimension $n$ and the degree $d$. As an application, we show that random tensors are well conditioned: $(1-o(1)) n^d$ independent copies of the simple random tensor $X \in \mathbb{R}^{n^d}$ are far from being linearly dependent with high probability. We prove this fact for any degree $d = o(\sqrt{n/\log n})$ and conjecture that it is true for any $d = O(n)$.

Subfields: Mathematical Physics, Numerical Analysis, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/c7a52518a889be69376b914b88555126744e4359

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Physics

1. Per-Gunnar Martinsson
2. Joel A. Tropp
3. Justin K. Romberg
4. Stanislav Minsker
5. Aaditya Ramdas
6. Jon D. McAuliffe
7. Steven R. Howard
8. Jasjeet S. Sekhon

In Numerical Analysis

1. Per-Gunnar Martinsson
2. Joel A. Tropp
3. Justin K. Romberg

In Statistics and Probability

1. Per-Gunnar Martinsson
2. Joel A. Tropp
3. Ramon van Handel
4. Aaditya Ramdas
5. Justin K. Romberg
6. Prateek Jain
7. Peter Richtárik
8. Steven R. Howard

Citations in the corpus

• Randomized numerical linear algebra: Foundations and algorithms (2020, background): “…H. van der Vorst (1987), Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide (Software, Environments and Tools), 1st edn, SIAM, Philadelphia, PA. P. Baldi and R. Vershynin (2019), ‘Polynomial threshold functions, hyperplane arrangements, and random tensors’, SIAM J. Math.”