Sharp spectral norm concentration of sparse random tensors
math.PR, math.CO, math.ST, stat.ML, stat.TH
Submitted: 2026-09-17
Updated: 2026-09-17
Comments: 18 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: We prove a sharp concentration inequality for the spectral norm of sparse random tensors with independent Bernoulli entries.
Terminology
Abstract
We prove a sharp concentration inequality for the spectral norm of sparse random tensors with independent Bernoulli entries. Let T be an order- k tensor of dimension n times times n with independent Bernoulli (p) entries, where k is fixed. For any c,r>0, we show that T- E T C k,r,c sqrt np with probability at least 1-n-r whenever np c n. We extend this bound to inhomogeneous Bernoulli sampling with deterministic entrywise weights. This removes the logarithmic factor in the work of Zhou and Zhu (2021). The proof follows the Kahn--Szemerédi light--heavy decomposition with a refined estimate on the heavy tuple part. We also obtain a log-free second eigenvalue bound for the random hypergraph model of Friedman and Wigderson (1995).
Sources
- A Geometric Perspective on the Injective Norm of Sums of Random Tensors
- Injective norm of random tensors with independent entries
- Injective norm of real and complex random tensors I: From spin glasses to geometric entanglement
- A moment-based approach to the injective norm of random tensors
- On decomposability and subdifferential of the tensor nuclear norm
- Provable Tensor Factorization with Missing Data
- Norm Bounds for Sparse Random Tensors and Spectral Gap of Random Hypergraphs
- Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity
- A statistical model for tensor PCA
- Spectral norm of random tensors
- Sparse random tensors: Concentration, regularization and applications
Related papers
- Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithms
- Local Anticoncentration for Gaussian Boson Sampling via Conditional Wishart Geometry
- Beyond the Semicircle: Free Diffusion Models with Prescribed Equilibria
- A New Bound on the Cumulant Generating Function of Dirichlet Processes
- The Site Frequency Spectrum in an Exponentially Growing Population with Selection
- Statistical inference for a multiscale stochastic model of enzyme kinetics via propagation of chaos