Introduction to the non-asymptotic analysis of random matrices
By Roman Vershynin. 2010
3,081 citations recorded by the source corpus.
This is a tutorial on some basic non-asymptotic methods and concepts in random matrix theory. The reader will learn several tools for the analysis of the extreme singular values of random matrices with independent rows or columns. Many of these methods sprung off from the development of geometric functional analysis since the 1970's. They have applications in several fields, most notably in theoretical computer science, statistics and signal processing. A few basic applications are covered in this text, particularly for the problem of estimating covariance matrices in statistics and for validating probabilistic constructions of measurement matrices in compressed sensing. These notes are written particularly for graduate students and beginning researchers in different areas, including functional analysts, probabilists, theoretical statisticians, electrical engineers, and theoretical computer scientists.
Subfields: Applied Mathematics, Computational Mechanics, Statistics and Probability, Statistical Learning Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Applied Mathematics
- Karim Lounici
- Roman Vershynin
- Martin J. Wainwright
- Yonina C. Eldar
- E.J. Candes
- Ramon van Handel
- Jaouad Mourtada
- Tong Zhang
In Computational Mechanics
- Martin J. Wainwright
- Tong Zhang
- Prateek Jain
- Francis R. Bach
- Michael I. Jordan
- E.J. Candes
- Jason D. Lee
- Peter Richtárik
In Statistics and Probability
- Martin J. Wainwright
- Victor Chernozhukov
- Sara A. van de Geer
- Francis R. Bach
- Peter Buhlmann
- Cun-Hui Zhang
- Bin Yu
- Stefan Wager
In Statistical Learning Theory
- Martin J. Wainwright
- Tong Zhang
- John C. Duchi
- Jason D. Lee
- Francis R. Bach
- Michael I. Jordan
- Samet Oymak
- Bin Yu
Citations in the corpus
- rTop-k: A Statistical Estimation Approach to Distributed SGD (2020, background): “‖X‖ 2 = inf { K ∈ (0,∞) | E[ 2(|X|/K) ] ≤ 1} where 2(x) = exp(x2)− 1, and that a random variable with finite 2-Orlicz norm is sub-Gaussian [51].”
- Learning Distributions from their Samples under Communication Constraints (2019, background): “For any unit vector u = ( v 1 , . . . , v d ) , By the rotation invariance of the Ψ 2 norm [15], this implies for some absolute constant C .”
- Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, background): “According to the standard covering net results (Vershynin, 2010), we know that N δ ≤ (1 + ) d .”
- Geometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints (2018, background): “There are also some equivalent definitions of ψ2-norm, and ‖X‖ψ2 ≤ σ if and only if X is sub-Gaussian with parameter C0σ for some absolute constant C0 > 0 Vershynin (2010).”
- Distributed Statistical Machine Learning in Adversarial Settings (2017, background): “To this end, we need to impose a few technical assumptions that are rather standard [30].”
- The Shattered Gradients Problem: If resnets are the answer, then what is the question? (2017, background): “The effective rank is r (∆) = tr (∆ > ∆) / k ∆ k 22 and measures the intrinsic dimension of a matrix (Vershynin, 2012).”
- Gradient Descent Finds Global Minima of Deep Neural Networks (2018, background): “The lemma is a consequence of well-known deviations bounds concerning the singular values of Gaussian random matrices (Vershynin, 2010)”
- Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “Then by Lemma 5.2 in Vershynin (2010), we have A key observation is that, for any i , l and any fixed vector α ∈ R m l − 1 , although Σ l,i is defined by where .”
- Diverse Neural Network Learns True Target Functions (2016, background): “Note that both a and b are sub-gaussian random variables with sub-gaussian norm c/ √ d where c is some constant [Vershynin, 2010].”
- Being Robust (in High Dimensions) Can Be Practical (2017, methodology): “After translating by µ G , we note that (iii) follows immediately from Lemmas 4.3 of [DKK + 16] and (iv) follows from Theorem 5.50 of [Ver10], as long as N = Ω( ν 4 d log(1 /τ ) /ε 2 ), with probability at least 1 − τ/ 3.”
- Distributed Multi-Task Learning (2015, methodology): “We assume the subguassian random vectors for every task have bounded subgaussian norm: max t max k (cid:107) X tk (cid:107) ψ 2 ≤ σ X [Vershynin, 2012].”
- Robust Regression via Hard Thresholding (2015, methodology): “The proof technique used in [14, Theorem 5.39] (see also Remark 5.40 (1) therein) can be used to establish the following result: with probability at least 1 − δ , with t set as mentioned in the theorem statement, we have This implies that for any v ∈ S p − 1 , we have The results then follow from…”
- The landscape of empirical risk for nonconvex losses (2016, methodology): “18 in [20], we have ‖βX − E[βX]‖ψ1 ≤ 2‖βX‖ψ1 ≤ 2‖X‖ψ1 , (29) which is essentially a symmetrization argument.”
- SGD Learns the Conjugate Kernel Class of the Network (2017, neutral): “2 Initial conditions Lemma 20 ([31] Cor.”