Sharp spectral norm concentration and regularization of sparse random tensors

Abstract

We prove sharp spectral-norm bounds and construct a mean-fitting regularization procedure for sparse random tensors of fixed order $k$. For an $n\times \cdots \times n$ tensor with independentBernoulli$(p)$ entries, the centered norm is $O(\sqrt{np})$ with polynomially high probability whenever $np\ge c\log n$. This removes the logarithmic loss in Zhou and Zhu (2021). We also determine the expected centered norm at every sparsity level: for every $0<p\le 1/2$, it has order $\min \{n^{k}p,\sqrt{d_{\mathrm{eff}}}\}$, where $d_{\mathrm{eff}}$ is an effective degree accounting for unusually large fiber counts. The upper bounds extend to tensors with deterministic entrywise weights and unequal sampling probabilities. Analogous two-sided bounds hold for the Friedman--Wigderson model at every degree; its expected centered norm has order $\sqrt{d_{\mathrm{eff}}}$. We also give an all-sparsity regularization procedure for independent Bernoulli tensors with unknown, possibly unequal means in $[0,p]$. Our light-fitting regularization estimates the original mean with minimax expected spectral-norm error of order $\min \{\sqrt{np},p{n}^{k/2}\}$ for every known $0\le p\le 1$. The procedure fits light multilinear residuals under an entrywise constraint on the candidate mean, rather than deleting high-degree fibers.

arXiv comment27 pages