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

DOI10.1214/15-AOP1025zbMATH Open1372.60004arXiv1408.6185OpenAlexW1553284371MaRDI QIDQ317469FDOQ317469

Afonso S. Bandeira, Ramon van Handel

Publication date: 30 September 2016

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

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.

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Local operator theory, random matrices and Banach spaces.
• The eigenvalues of random symmetric matrices
• About the constants in Talagrand's concentration inequalities for empirical processes.
• Some estimates of norms of random matrices
• User-friendly tail bounds for sums of random matrices
• An Introduction to Random Matrices
• Upper and Lower Bounds for Stochastic Processes
• Lifts, discrepancy and nearly optimal spectral gap
• Moment inequalities for functions of independent random variables
• The Tracy-Widom law for some sparse random matrices
• Non-asymptotic theory of random matrices: extreme singular values
• Necessary and sufficient conditions for almost sure convergence of the largest eigenvalue of a Wigner matrix
• A limit theorem for the norm of random matrices
• Sampling convex bodies: a random matrix approach
• On the expectation of the norm of random matrices with non-identically distributed entries
• The Expected Norm of Random Matrices
• The spectral edge of some random band matrices
• Sums of random Hermitian matrices and an inequality by Rudelson
• Largest eigenvalues and eigenvectors of band or sparse random matrices

Cited In (70)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Large deviations for the largest eigenvalue of Gaussian networks with constant average degree
• Feasibility of sparse large Lotka-Volterra ecosystems
• Low-rank model with covariates for count data with missing values
• Singularity of sparse Bernoulli matrices
• Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model
• Relative perturbation bounds with applications to empirical covariance operators
• Structured matrix estimation and completion
• Title not available (Why is that?)
• On the Expectation of Operator Norms of Random Matrices
• Spectral radii of sparse random matrices
• CLT for non-Hermitian random band matrices with variance profiles
• Adaptive estimation of nonparametric geometric graphs
• Random Laplacian matrices and convex relaxations
• Scalable subspace methods for derivative-free nonlinear least-squares optimization
• The dimension-free structure of nonhomogeneous random matrices
• On the non-asymptotic concentration of heteroskedastic Wishart-type matrix
• Markov random geometric graph, MRGG: a growth model for temporal dynamic networks
• Model-free Nonconvex Matrix Completion: Local Minima Analysis and Applications in Memory-efficient Kernel PCA
• On the spectral norm of Gaussian random matrices
• Exact Clustering of Weighted Graphs via Semidefinite Programming
• Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
• An extension of the angular synchronization problem to the heterogeneous setting
• Convex relaxation methods for community detection
• Lower bounds for the smallest singular value of structured random matrices
• Invertibility of sparse non-Hermitian matrices
• Sparse random tensors: concentration, regularization and applications
• Density and spacings for the energy levels of quadratic Fermi operators
• Circular law for random block band matrices with genuinely sublinear bandwidth
• Optimal graphon estimation in cut distance
• The spectral norm of random lifts of matrices
• Finding Planted Subgraphs with Few Eigenvalues using the Schur--Horn Relaxation
• A simple spectral algorithm for recovering planted partitions
• Linear eigenvalue statistics of random matrices with a variance profile
• Joint Community Detection and Rotational Synchronization via Semidefinite Programming
• A combinatorial result on asymptotic independence relations for random matrices with non-commutative entries
• Title not available (Why is that?)
• Constructive regularization of the random matrix norm
• Random sections of ellipsoids and the power of random information
• A UNIFORM BOUND ON THE OPERATOR NORM OF SUB-GAUSSIAN RANDOM MATRICES AND ITS APPLICATIONS
• A Hoeffding inequality for Markov chains
• A unified approach to synchronization problems over subgroups of the orthogonal group
• Applied harmonic analysis and data science. Abstracts from the workshop held November 28 -- December 4, 2021 (hybrid meeting)
• Title not available (Why is that?)
• Two-sample Hypothesis Testing for Inhomogeneous Random Graphs
• Convex optimization for the densest subgraph and densest submatrix problems
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• Matrix concentration inequalities and free probability
• Concentration of the spectral norm of Erdős-Rényi random graphs
• Fluctuations in mean-field Ising models
• Adaptive confidence sets for matrix completion
• Norms of random matrices: local and global problems
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Random geometric graph: some recent developments and perspectives
• Stochastic trust-region algorithm in random subspaces with convergence and expected complexity analyses
• Extreme singular values of inhomogeneous sparse random rectangular matrices
• Asymptotic geometric analysis: achievements and perspective
• Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
• Direct Search Based on Probabilistic Descent in Reduced Spaces
• Emergence of near-TAP free energy functional in the SK model at high temperature
• On the distance to low-rank matrices in the maximum norm
• Universality and sharp matrix concentration inequalities
• Benign landscapes of low-dimensional relaxations for orthogonal synchronization on general graphs
• Principles for initialization and architecture selection in graph neural networks with ReLU activations
• Title not available (Why is that?)
• 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
• Norms of structured random matrices

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)