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×⋯× n tensor with independentBernoulli(p) entries, the centered norm is O(√(np)) with polynomially high probability whenever np≥ clog 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≤1/2, it has order min{nkp,√(deff)}, where deff 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 √(deff). 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{√(np),pnk/2} for every known 0≤ p≤1. The procedure fits light multilinear residuals under an entrywise constraint on the candidate mean, rather than deleting high-degree fibers.
Related
- Concentration of Regularized Sparse Random Matrices: Spectral Edge Bounds via Nonbacktracking Operators
- Spectral aspects of random heavy-tailed tensors
- Sharp Injective Norm Bounds for Inhomogeneous Gaussian Tensors and Sparse Extensions
- Joint distributions of eigenvectors of symmetric random tensors
- Optimal fiber comparisons for random tensors
BibTeX
@misc{zhou2026sharp,
title = {{Sharp spectral norm concentration and regularization of sparse random tensors}},
author = {Zhixin Zhou and Yizhe Zhu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.20520},
eprint = {2609.20520},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20520},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Sharp spectral norm concentration and regularization of sparse random tensors
AU - Zhixin Zhou
AU - Yizhe Zhu
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2609.20520
UR - https://arxiv.org/abs/2609.20520
AB - We prove sharp spectral-norm bounds and construct a mean-fitting regularization procedure for sparse random tensors of fixed order k. For an n×⋯× n tensor with independentBernoulli(p) entries, the centered norm is O(√(np)) with polynomially high probability whenever np≥ clog 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≤1/2, it has order min{n^kp,√(d_eff)}, where d_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 √(d_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{√(np),pn^k/2} for every known 0≤ p≤1. The procedure fits light multilinear residuals under an entrywise constraint on the candidate mean, rather than deleting high-degree fibers.
ER -