Sharp nonasymptotic bounds on the norm of random matrices with independent entries

Abstract

We obtain nonasymptotic bounds on the spectral norm of random matrices with independent entries that improve significantly on earlier results. If $X$ is the $n\times n$ symmetric matrix with $X_{ij}\sim N(0,b_{ij}^2)$, we show that \[\mathbf{E}\Vert X\Vert \lesssim\max_i\sqrt{\sum_jb_{ij}^2}+\max _{ij}\vert b_{ij}\vert \sqrt{\log n}.\] This bound is optimal in the sense that a matching lower bound holds under mild assumptions, and the constants are sufficiently sharp that we can often capture the precise edge of the spectrum. Analogous results are obtained for rectangular matrices and for more general sub-Gaussian or heavy-tailed distributions of the entries, and we derive tail bounds in addition to bounds on the expected norm. The proofs are based on a combination of the moment method and geometric functional analysis techniques. As an application, we show that our bounds immediately yield the correct phase transition behavior of the spectral edge of random band matrices and of sparse Wigner matrices. We also recover a result of Seginer on the norm of Rademacher matrices.

Published at http://dx.doi.org/10.1214/15-AOP1025 in the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Moment inequalities for functions of independent random variables

Cited by in corpus (80)

• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• On the low-rank approach for semidefinite programs arising in synchronization and community detection
• Beyond Low Rank + Sparse: Multi-scale Low Rank Matrix Decomposition
• The dimension-free structure of nonhomogeneous random matrices
• On the spectral norm of Gaussian random matrices
• A Permutation-based Model for Crowd Labeling: Optimal Estimation and Robustness
• Mixed Membership Estimation for Social Networks
• Structured Random Matrices
• Matrix Concentration Inequalities and Free Probability
• Random sections of ellipsoids and the power of random information
• Two-sample Hypothesis Testing for Inhomogeneous Random Graphs
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Hierarchical community structure in networks
• Reducibility and Statistical-Computational Gaps from Secret Leakage
• Fast Compressive Sensing Recovery Using Generative Models with Structured Latent Variables
• Community Recovery in Graphs with Locality
• Ranking and synchronization from pairwise measurements via SVD
• Network cross-validation by edge sampling
• Unified ${\ell }_{2\to \infty }$ Eigenspace Perturbation Theory for Symmetric Random Matrices
• Quantum-classical algorithms for skewed linear systems with optimized Hadamard test
• Spectral radii of sparse random matrices
• Time Matters: Multi-scale Temporalization of Social Media Popularity
• Robust and efficient multi-way spectral clustering
• Network Representation Using Graph Root Distributions
• Low-rank matrix completion and denoising under Poisson noise
• CLT for non-Hermitian random band matrices with variance profiles
• Sparse random tensors: Concentration, regularization and applications
• Nonconvex Rectangular Matrix Completion via Gradient Descent without ${\ell }_{2,\infty }$ Regularization
• On the power of iid information for linear approximation
• Sparse Popularity Adjusted Stochastic Block Model
• PAC-Bayesian Margin Bounds for Convolutional Neural Networks
• On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation
• Exact Minimax Estimation for Phase Synchronization
• A useful criterion on studying consistent estimation in community detection
• Detecting Latent Communities in Network Formation Models
• Spectral clustering via adaptive layer aggregation for multi-layer networks
• Benign landscapes of low-dimensional relaxations for orthogonal synchronization on general graphs
• Stochastic trust-region algorithm in random subspaces with convergence and expected complexity analyses
• Latent Distance Estimation for Random Geometric Graphs
• On the distance to low-rank matrices in the maximum norm
• Hypothesis Testing for Equality of Latent Positions in Random Graphs
• Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices
• Density and spacings for the energy levels of quadratic Fermi operators
• The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks
• Markov Random Geometric Graph (MRGG): A Growth Model for Temporal Dynamic Networks
• Relative Density and Exact Recovery in Heterogeneous Stochastic Block Models
• Confidence Region of Singular Subspaces for Low-rank Matrix Regression
• Expander graphs are globally synchronizing
• Norms of Randomized Circulant Matrices
• Circular Law for Random Block Band Matrices with Genuinely Sublinear Bandwidth
• Investigate Invertibility of Sparse Symmetric Matrix
• Estimation and Clustering in Popularity Adjusted Stochastic Block Model
• Simultaneous prediction and community detection for networks with application to neuroimaging
• Algorithms and Complexity for some Multivariate Problems
• Extreme singular values of inhomogeneous sparse random rectangular matrices
• Expected Chromatic Number of Random Subgraphs
• Euclidean Representation of Low-Rank Matrices and Its Statistical Applications
• For Manifold Learning, Deep Neural Networks can be Locality Sensitive Hash Functions
• A note on quantum expanders
• Robust Estimation for Random Graphs
• Exponential error rates of SDP for block models: Beyond Grothendieck's inequality
• Large deviations for the largest eigenvalue of Gaussian networks with constant average degree
• The "Power of Few" Phenomenon: The Sparse Case
• Nonconvex Matrix Completion with Linearly Parameterized Factors
• The role of invariance in spectral complexity-based generalization bounds
• Online codes for analog signals
• A Note on the Concentration of Spectral Measure of Wigner's Matrices
• A Hoeffding inequality for Markov chains
• A Uniform Bound on the Operator Norm of Sub-Gaussian Random Matrices and Its Applications
• A special case of the existential version of the Non Commutative Khintchine inequality
• Outliers Detection in Networks with Missing Links
• Random Geometric Graphs on Euclidean Balls
• Robust spectral compressive sensing via vanilla gradient descent
• Online network change point detection with missing values and temporal dependence
• Norms of structured random matrices
• A Unified Framework for Community Detection and Model Selection in Blockmodels
• Optimizing Sparse SYK
• Optimal rates for ranking a permuted isotonic matrix in polynomial time
• Emergence of near-TAP free energy functional in the SK model at high temperature
• Learning with Semi-Definite Programming: new statistical bounds based on fixed point analysis and excess risk curvature