Tensor Concentration Inequalities: A Geometric Approach

Matrix concentration inequalities, commonly used in the forms of non-commutative Khintchine inequalities or matrix Chernoff bounds, are central to a wide range of applications in computer science and mathematics. However, they fall short in many applications where tensor versions of these inequalities are needed. In this work, we study the ℓp injective norms of sums of independent tensors. We obtain the first non-trivial concentration inequalities in this setting, and our inequalities are nearly tight in certain regimes of p and the order of the tensors. Previously, tensor concentration inequalities were known only in the special cases of rank-1 tensors or p=2. Our results are obtained via a geometric argument based on estimating the covering numbers for the natural stochastic processes corresponding to tensor injective norms. Our approach is quite general and might be applicable to other settings of matrix and tensor concentration. We discuss applications and connections of our inequalities to various other problems, including tensor principle component analysis, various models of random tensors and matrices, type-2 constants of certain Banach spaces, and locally decodable codes.