Sharp spectral norm concentration of sparse random tensors
Not on the map. Why?
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).
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
11 of 34 references.
References · 11
- 2013Consistency of spectral clustering in stochastic block modelscited by 129
- 2014A statistical model for tensor PCAcited by 72
- 2014Provable Tensor Factorization with Missing Datacited by 31
- 2015Concentration and regularization of random graphscited by 25
- 2016Incoherent Tensor Norms and Their Applications in Higher Order Tensor Completioncited by 10
- 2014Spectral norm of random tensorscited by 9
- 2021Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Modelcited by 7
- 2019Deterministic tensor completion with hypergraph expanderscited by 6
- 2017Effective Tensor Sketching via Sparsificationcited by 5
- 2026Wedge Sampling: Efficient Tensor Completion with Nearly-Linear Sample Complexitycited by 3
- 2025On decomposability and subdifferential of the tensor nuclear normcited by 1
Built on by
Not cited yet.