# Sharp spectral norm concentration of sparse random tensors

arXiv: https://arxiv.org/abs/2609.20520 · HTML: https://mlsanity.com/paper/2609.20520/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 34 references that are in the map.
- First posted on arXiv 17 Sep 2026.

## Builds on (most cited first, 11 of 11)

- [Consistency of spectral clustering in stochastic block models](https://mlsanity.com/paper/1312.2050/) (2013)
- [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014)
- [Provable Tensor Factorization with Missing Data](https://mlsanity.com/paper/1406.2784/) (2014)
- [Concentration and regularization of random graphs](https://mlsanity.com/paper/1506.00669/) (2015)
- [Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completion](https://mlsanity.com/paper/1606.03504/) (2016)
- [Spectral norm of random tensors](https://mlsanity.com/paper/1407.1870/) (2014)
- [Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model](https://mlsanity.com/paper/2112.11671/) (2021)
- [Deterministic tensor completion with hypergraph expanders](https://mlsanity.com/paper/1910.10692/) (2019)
- [Effective Tensor Sketching via Sparsification](https://mlsanity.com/paper/1710.11298/) (2017)
- [Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexity](https://mlsanity.com/paper/2602.05869/) (2026)
- [On decomposability and subdifferential of the tensor nuclear norm](https://mlsanity.com/paper/2510.04647/) (2025)

## Abstract (arXiv)

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×cdots× n with independent Bernoulli(p) entries, where k is fixed. For any c,r>0, we show that |T-mathbb E T|≤ Ck,r,c√np with probability at least 1-n-r whenever np≥ clog 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'edi 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).