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

By Afonso S. Bandeira, Ramon van Handel. 2014

303 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/b9ab7151862b5f4512151efb61482576384fdb5a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Statistics and Probability

Citations in the corpus

Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, background): “To proceed, we need the following result from Bandeira and van Handel [5]: Proposition 1 (Corollaries 3.6 and 3.12 in [5]).”
CoinPress: Practical Private Mean and Covariance Estimation (2020, unknown): “This is from Theorem 1.1 of [BVH16], fixing the value of ε = log d d .”
Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks (2022, background): “, Chang et al. (2020) showed that SATNet (Wang et al., 2019) could not solve visual Sudoku without using intermediate labels to identify individual Sudoku digit images. Similar limitations were observed in language related compounded tasks, including commonsense reasoning (Liu et al., 2022; Wei et a”
Matrix concentration inequalities and free probability (2021, background): “In this case, [6] showed that E‖X‖ σ(X)+max ij |bij | √ logd, σ (X)2 =max i ∑”
Lower bounds for the smallest singular value of structured random matrices (2016, background): “In connection with problems in computer science and the theory of Banach spaces there has been considerable interest in obtaining non-asymptotic bounds for matrices with independent but non-identically distributed entries; see the recent works [5] and [41] and references therein for an overview.”
Spectral radii of sparse random matrices (2017, background): “We would like to thank Ramon van Handel for many helpful discussions on the articles [2, 22].”
Structured Random Matrices (2016, methodology): “Once this special case has been understood, the reader can extend the proof to the general setting as an exercise, or refer to the general proof given in [4].”
On the spectral norm of Gaussian random matrices (2015, methodology): “1 appears (at least cosmetically) to be tantalizingly close to the right-hand side of (⋆), one might hope at first sight that the latter could be established by a refinement of the methods that were developed in [1].”