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

DOI10.1214/15-AOP1025MaRDI QIDQ317469zbMATH OpenOpenAlexFDO

Authors Afonso S. Bandeira, Ramon van Handel

Publication date 30 September 2016

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.6185, https://projecteuclid.org/euclid.aop/1470139147

zbMATH Keywords

spectral normrandom matricesnon-asymptotic boundstail inequalities

Mathematics Subject Classification ID

Large deviations (60F10) Random matrices (probabilistic aspects) (60B20) Probabilistic methods in Banach space theory (46B09)

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 $nimesn$ symmetric matrix with $X_{ij}simN(0,b_{ij}^2)$, we show that [mathbf{E}Vert XVert lesssimmax_isqrt{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.

Recommendations

• Spectral norm of products of random and deterministic matrices
• On the lower bound of the spectral norm of symmetric random matrices with independent entries
• On the spectral norm of Gaussian random matrices
• Spectral norm of random matrices
• On the expectation of the norm of random matrices with non-identically distributed entries

Cites work

• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 1993745 (Why is no real title available?)
• scientific article; zbMATH DE number 6026126 (Why is no real title available?)
• A limit theorem for the norm of random matrices
• About the constants in Talagrand's concentration inequalities for empirical processes.
• An introduction to random matrices
• Concentration inequalities. A nonasymptotic theory of independence
• Estimates for moments of random matrices with Gaussian elements
• Largest eigenvalues and eigenvectors of band or sparse random matrices
• Lifts, discrepancy and nearly optimal spectral gap
• Local operator theory, random matrices and Banach spaces.
• Moment inequalities for functions of independent random variables
• Necessary and sufficient conditions for almost sure convergence of the largest eigenvalue of a Wigner matrix
• Non-asymptotic theory of random matrices: extreme singular values
• On the expectation of the norm of random matrices with non-identically distributed entries
• Sampling convex bodies: a random matrix approach
• Some estimates of norms of random matrices
• Sums of random Hermitian matrices and an inequality by Rudelson
• The Expected Norm of Random Matrices
• The Tracy-Widom law for some sparse random matrices
• The eigenvalues of random symmetric matrices
• The spectral edge of some random band matrices
• Upper and lower bounds for stochastic processes. Modern methods and classical problems
• User-friendly tail bounds for sums of random matrices

Cited in

(77)

• Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model
• CLT for non-Hermitian random band matrices with variance profiles
• scientific article; zbMATH DE number 7415085 (Why is no real title available?)
• Some estimates of norms of random matrices
• Random sections of ellipsoids and the power of random information
• On the spectral norm of Gaussian random matrices
• Spectral norm of random matrices
• Joint community detection and rotational synchronization via semidefinite programming
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• Concentration of the spectral norm of Erdős-Rényi random graphs
• Sparse random tensors: concentration, regularization and applications
• Scalable subspace methods for derivative-free nonlinear least-squares optimization
• Structured matrix estimation and completion
• Density and spacings for the energy levels of quadratic Fermi operators
• On the lower bound of the spectral norm of symmetric random matrices with independent entries
• The dimension-free structure of nonhomogeneous random matrices
• Matrix concentration inequalities and free probability
• Two-sample hypothesis testing for inhomogeneous random graphs
• Convex relaxation methods for community detection
• Lower bounds for the smallest singular value of structured random matrices
• Invertibility of sparse non-Hermitian matrices
• Adaptive estimation of nonparametric geometric graphs
• scientific article; zbMATH DE number 7626708 (Why is no real title available?)
• Constructive regularization of the random matrix norm
• Convex optimization for the densest subgraph and densest submatrix problems
• Wigner random matrices with non-symmetrically distributed entries
• Relative perturbation bounds with applications to empirical covariance operators
• Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
• A Hoeffding inequality for Markov chains
• Finding planted subgraphs with few eigenvalues using the Schur-Horn relaxation
• Circular law for random block band matrices with genuinely sublinear bandwidth
• scientific article; zbMATH DE number 7370536 (Why is no real title available?)
• scientific article; zbMATH DE number 7626779 (Why is no real title available?)
• Spectral radii of sparse random matrices
• Markov random geometric graph, MRGG: a growth model for temporal dynamic networks
• Norms of certain random matrices with dependent entries
• Optimal graphon estimation in cut distance
• Fluctuations in mean-field Ising models
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• A combinatorial result on asymptotic independence relations for random matrices with non-commutative entries
• On the non-asymptotic concentration of heteroskedastic Wishart-type matrix
• A refined non-asymptotic tail bound of sub-Gaussian matrix
• Singularity of sparse Bernoulli matrices
• A unified approach to synchronization problems over subgroups of the orthogonal group
• Adaptive confidence sets for matrix completion
• A simple spectral algorithm for recovering planted partitions
• The spectral norm of random lifts of matrices
• Random Laplacian matrices and convex relaxations
• Feasibility of sparse large Lotka-Volterra ecosystems
• Model-free nonconvex matrix completion: local minima analysis and applications in memory-efficient kernel PCA
• Low-rank model with covariates for count data with missing values
• On the expectation of operator norms of random matrices
• Exact clustering of weighted graphs via semidefinite programming
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Large deviations for the largest eigenvalue of Gaussian networks with constant average degree
• An extension of the angular synchronization problem to the heterogeneous setting
• Applied harmonic analysis and data science. Abstracts from the workshop held November 28 -- December 4, 2021 (hybrid meeting)
• Norms of random matrices: local and global problems
• Linear eigenvalue statistics of random matrices with a variance profile
• Universality and sharp matrix concentration inequalities
• Random geometric graph: some recent developments and perspectives
• Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
• Collective matrix completion
• Extreme singular values of inhomogeneous sparse random rectangular matrices
• Benign landscapes of low-dimensional relaxations for orthogonal synchronization on general graphs
• On the distance to low-rank matrices in the maximum norm
• Asymptotic geometric analysis: achievements and perspective
• A UNIFORM BOUND ON THE OPERATOR NORM OF SUB-GAUSSIAN RANDOM MATRICES AND ITS APPLICATIONS
• Tail Bounds on the Spectral Norm of Sub-Exponential Random Matrices
• Stochastic trust-region algorithm in random subspaces with convergence and expected complexity analyses
• Emergence of near-TAP free energy functional in the SK model at high temperature
• Norms of structured random matrices
• scientific article; zbMATH DE number 7626745 (Why is no real title available?)
• Approximate message passing for sparse matrices with application to the equilibria of large ecological Lotka-Volterra systems
• A localization-delocalization transition for nonhomogeneous random matrices
• Principles for initialization and architecture selection in graph neural networks with ReLU activations
• Direct Search Based on Probabilistic Descent in Reduced Spaces

This page was built for publication: Sharp nonasymptotic bounds on the norm of random matrices with independent entries

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