Sparse random tensors: concentration, regularization and applications

DOI10.1214/21-EJS1838MaRDI QIDQ2044387zbMATH OpenOpenAlexWikidataFDO

Authors Zhixin Zhou, Yizhe Zhu

Publication date 9 August 2021

Published in Electronic Journal of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.09063

zbMATH Keywords

spectral normhypergraph expandersparse random tensortensor sparsification

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Random matrices (algebraic aspects) (15B52) Combinatorial probability (60C05)

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}geqfracclognn$, we show that $|T-mathbbET|=O(sqrtn{p}_{max}lo{g}^{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}geqfracclogn{n}^m$ with $1leqmleqk-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}geqfracc{n}^m$ with $k/2leqmleqk-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.

Recommendations

• Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1.
• Concentration inequalities for random tensors
• On Tensors, Sparsity, and Nonnegative Factorizations
• Tensor decompositions and sparse log-linear models
• Sparse and Low-Rank Tensor Estimation via Cubic Sketchings
• Random Projections for Low Multilinear Rank Tensors
• Generalized Low-Rank Plus Sparse Tensor Estimation by Fast Riemannian Optimization
• Provable sparse tensor decomposition
• A randomized algorithm for a tensor-based generalization of the singular value decomposition
• Phase transition in the spiked random tensor with Rademacher prior

Cites work

• A graphon approach to limiting spectral distributions of Wigner-type matrices
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Concentration and regularization of random graphs
• Concentration inequalities for random tensors
• Concentration inequalities. A nonasymptotic theory of independence
• Consistency of spectral clustering in stochastic block models
• Consistency of spectral hypergraph partitioning under planted partition model
• Consistent community detection in multi-layer network data
• Constructive regularization of the random matrix norm
• Deterministic algorithms for matrix completion
• Eigenvalues and linear quasirandom hypergraphs
• Exact recovery in the hypergraph stochastic block model: a spectral algorithm
• Functional limit theorems for random regular graphs
• HIGH DIMENSIONAL EXPANDERS
• High-dimensional probability. An introduction with applications in data science
• Inverse expander mixing for hypergraphs
• Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
• Loose Laplacian spectra of random hypergraphs
• Matrix Completion From a Few Entries
• Most tensor problems are NP-hard
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Norms of random matrices: local and global problems
• On codes from hypergraphs.
• On the second eigenvalue of hypergraphs
• On the spectral norm of Gaussian random matrices
• Operator norm inequalities between tensor unfoldings on the partition lattice
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• Phase transition in the spiked random tensor with Rademacher prior
• Polynomial threshold functions, hyperplane arrangements, and random tensors
• Random matrices and complexity of spin glasses
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Size biased couplings and the spectral gap for random regular graphs
• Spectra of lifted Ramanujan graphs
• Spectral algorithms for tensor completion
• Spectral analysis of large dimensional random matrices
• Spectral norm of random matrices
• Spectral radii of sparse random matrices
• Spectral techniques applied to sparse random graphs
• SpicyMKL: a fast algorithm for multiple kernel learning with thousands of kernels
• Tensor Decompositions and Applications
• Tensor decompositions for learning latent variable models
• Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1.
• The Largest Eigenvalue of Sparse Random Graphs
• The dimension-free structure of nonhomogeneous random matrices
• The landscape of the spiked tensor model
• The spectral gap of dense random regular graphs

Cited in

(12)

• Deterministic tensor completion with hypergraph expanders
• Marchenko–Pastur law with relaxed independence conditions
• Tensor Bernstein concentration inequalities with an application to sample estimators for high-order moments
• Concentration inequalities for random tensors
• On the second eigenvalue of random bipartite biregular graphs
• Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1.
• Random Tensors and Planted Cliques
• Sharp concentration of simple random tensors
• Partial recovery and weak consistency in the non-uniform hypergraph stochastic block model
• On the estimation of Gaussian moment tensors
• Concentration and regularization of random graphs
• Sparse random hypergraphs: non-backtracking spectra and community detection

This page was built for publication: Sparse random tensors: concentration, regularization and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2044387)