A moment-based approach to the injective norm of random tensors

Abstract

In this paper, we present a technically simple method to establish upper bounds on the expected injective norm of real and complex random tensors. Our approach is somewhat analogous to the moment method in random matrix theory, and is based on a deterministic upper bound on the injective norm of a tensor which might be of independent interest. Compared to previous approaches to these problems (spin-glass methods, epsilon-net techniques, Sudakov-Fernique arguments, and PAC-Bayesian proofs), our method has the benefit of being nonasymptotic, relatively elementary, and applicable to non-Gaussian models. We illustrate our approach on various models of random tensors, recovering some previously known (and conjecturally tight) bounds with simpler arguments, and presenting new bounds, some of which are provably tight. From the perspective of statistical physics, our results yield rigorous estimates on the ground-state energy of real and complex, possibly non-Gaussian, spin glass models. From the perspective of quantum information, they establish bounds on the geometric entanglement of random bosonic states and of random states with bounded multipartite Schmidt rank, both in the thermodynamic limits as well as the regimes of large local dimensions.