Non-asymptotic theory of random matrices: extreme singular values

By Mark Rudelson, Roman Vershynin. 2010

449 citations recorded by the source corpus.

The classical random matrix theory is mostly focused on asymptotic spectral properties of random matrices as their dimensions grow to infinity. At the same time many recent applications from convex geometry to functional analysis to information theory operate with random matrices in fixed dimensions. This survey addresses the non-asymptotic theory of extreme singular values of random matrices with independent entries. We focus on recently developed geometric methods for estimating the hard edge of random matrices (the smallest singular value).

Subfields: Applied Mathematics, Mathematical Physics, 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

In Mathematical Physics

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

RUDDER: Return Decomposition for Delayed Rewards (2018, background): “nt. The Marchenko-Pastur quarter circular law for rectangular matrices says that for n= mthe maximal singular value is 2 p p m[79]. Asymptotically we have for the maximal singular value smax(A) / m+ n[104]. A bound on the largest singular value is given by [122]: s2 max(A) 6 ( p m+ p n)2 + O( p nlog”
Convergence Analysis of Two-layer Neural Networks with ReLU Activation (2017, background): “It is also well known that if the entries are initialized with O(1/ √ d), the spectral norm of the random matrix is O(1) [33].”
Introduction to the non-asymptotic analysis of random matrices (2010, background): “The surveys [76, 69] discuss this problem at length, and they offer a glimpse of connections to other problems of random matrix theory and additive combinatorics.”
User-Friendly Tail Bounds for Sums of Random Matrices (2010, background): “For some discussion of this question, see [RV10].”
Exponentially vanishing sub-optimal local minima in multilayer neural networks (2017, background): “(9.4)), so the minimal possible value is attained when u ⊤ 2 ˆ w 1 = ˆ w 1 . k k The minimal nonzero singular value, σ 2 , can be bounded using the following result from (Rudelson & Vershynin, 2010, eq.”
Discrete Gaussian Leftover Hash Lemma over Infinite Domains (2013, background): “While we do not prove this, we refer the reader to [16] for intuitive evidence.”
Small Ball Probabilities for Linear Images of High-Dimensional Distributions (2014, unknown): “44 92 v1 [ m at h. PR ] 1 8 Fe b 20 14 0.9 r(A), where r(A) denotes the stable rank of A.”
Optimal selection of reduced rank estimators of high-dimensional matrices (2010, background): “Standard results on the largest singular value of Gaussian matrices show ) and similar bounds are available for subGaussian matrices, see, for instance, Rudelson and Vershynin (2010).”
Sharp nonasymptotic bounds on the norm of random matrices with independent entries (2014, background): “This question is most naturally phrased in a nonasymptotic setting: can we obtain upper and lower bounds on ‖X‖, in terms of natural parameters that capture the structure of X, that differ only by universal constants? Nonasymptotic bounds on the norm of a random matrix have long been developed in a ”
Concentration inequalities for random tensors (2019, unknown): “For d = 1, this problem has been extensively studied in random matrix theory [16, 31, 23, 32, 25, 3, 26, 34, 27, 13, 10, 35, 36].”
Sub‐Weibull distributions: Generalizing sub‐Gaussian and sub‐Exponential properties to heavier tailed distributions (2019, unknown): “, 2017), bandit problems (Bubeck and Cesa-Bianchi, 2012) and singular values of random matrices (Rudelson and Vershynin, 2010).”
Learning Two Layer Rectified Neural Networks in Polynomial Time (2018, unknown): “1 in Rudelson and Vershynin (2010), with probability 1−δ, σmin(T) ≥ kδ.”
Randomized Algorithms for Low-Rank Matrix Factorizations: Sharp Performance Bounds (2013, background): “These bounds are recalled in [8], though known earlier.”
Bayesian Optimization in a Billion Dimensions via Random Embeddings (2013, methodology): “On the other hand, we have together with the following probabilistic bound on s min ( G ) (cf. Equation 3.2 in (Rudelson & Vershynin, 2010)): So, with probability 1 − 2 , we have and so In what follows, we will use the notation: Now, with these estimates in hand, we can go ahead and show that the…”
How Close is the Sample Covariance Matrix to the Actual Covariance Matrix? (2010, background): “For more on the extreme eigenvalues in both asymptotic regime (N, n → ∞) and non-asymptotic regime (N, n fixed), see [24].”
Random matrices: Universality of local spectral statistics of non-Hermitian matrices (2012, background): “Interestingly, this is, at this point, the only way to obtain good lower bound on the least singular values of random matrices when the ensemble is discrete (see also [42, 43, 53] for more results and discussion).”