Sparse random tensors: Concentration, regularization and applications

Abstract

We prove a non-asymptotic concentration inequality for the spectral norm of sparse inhomogeneous random tensors with Bernoulli entries. For an order-$k$ inhomogeneous random tensor $T$ with sparsity $p_{\max }\ge \frac{c\log n}{n}$, we show that $\Vert T-\mathbb{E}T\Vert =O(\sqrt{n{p}_{\max }}{\log }^{k-2}(n))$ with high probability. The optimality of this bound up to polylog factors is provided by an information theoretic lower bound. By tensor unfolding, we extend the range of sparsity to $p_{\max }\ge \frac{c\log n}{n^m}$ with $1\le m\le k-1$ and obtain concentration inequalities for different sparsity regimes. We also provide a simple way to regularize $T$ such that $O(\sqrt{n^m{p}_{\max }})$ concentration still holds down to sparsity $p_{\max }\ge \frac{c}{n^m}$ with $k/2\le m\le k-1$. We present our concentration and regularization results with two applications: (i) a randomized construction of hypergraphs of bounded degrees with good expander mixing properties, (ii) concentration of sparsified tensors under uniform sampling.

arXiv comment24 pages

References in corpus (18)

• Consistency of spectral clustering in stochastic block models
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Provable Tensor Factorization with Missing Data
• Consistency of Spectral Hypergraph Partitioning under Planted Partition Model
• Statistical and computational phase transitions in spiked tensor estimation
• The dimension-free structure of nonhomogeneous random matrices
• Size biased couplings and the spectral gap for random regular graphs
• On the spectral norm of Gaussian random matrices
• Spectral Detection on Sparse Hypergraphs
• Functional limit theorems for random regular graphs
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Exact Recovery in the Hypergraph Stochastic Block Model: a Spectral Algorithm
• Operator Norm Inequalities between Tensor Unfoldings on the Partition Lattice
• Community detection in the sparse hypergraph stochastic block model
• Spectra of random regular hypergraphs
• Deterministic tensor completion with hypergraph expanders
• Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares

Cited by in corpus (3)

• Deterministic tensor completion with hypergraph expanders
• On the second eigenvalue of random bipartite biregular graphs
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model