Non-asymptotic theory of random matrices: extreme singular values

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).

• Publication year

  2010

• Venue

  arXiv: Functional Analysis

• Publication date

  2010-03-15

• Fields of study

  Mathematics

• Identifiers
  DOI 10.1142/9789814324359_0111arXiv 1003.2990
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Spectral Analysis of Large Dimensional Random Matrices, 2nd edn

  2012cited by this paper
• The circular law

  2012cited by this paper
• ACTA ARITHMETICA

  2011cited by this paper
• Shifting Inequality and Recovery of Sparse Signals

  2010cited by this paper
• The Littlewood-Offord problem in high dimensions and a conjecture of Frankl and Füredi

  2010cited by this paper
• Ramsey properties of random discrete structures

  2010cited by this paper
• How Close is the Sample Covariance Matrix to the Actual Covariance Matrix?

  2010cited by this paper
• Sums of Independent Random Variables

  2010cited by this paper
• A sharp inverse Littlewood‐Offord theorem

  2009cited by this paper
• Random Matrices: the Distribution of the Smallest Singular Values

  2009cited by this paper
• Smallest singular value of a random rectangular matrix

  2009influential reference
• Spectral Analysis of Large Dimensional Random Matrices

  2009cited by this paper
• Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles

  2009cited by this paper
• The least singular value of a random square matrix is O(n−1/2)

  2008cited by this paper
• Random matrices: Universality of ESDs and the circular law

  2008cited by this paper
• A Simple Proof of the Restricted Isometry Property for Random Matrices

  2008influential reference
• An Introduction To Compressive Sampling

  2008cited by this paper
• Spectral norm of products of random and deterministic matrices

  2008influential reference
• On sparse reconstruction from Fourier and Gaussian measurements

  2008influential reference
• ON THE SINGULARITY PROBABILITY OF RANDOM

  2008cited by this paper
• The smallest singular value of a random rectangular matrix

  2008cited by this paper
• From the Littlewood-Offord problem to the Circular Law: universality of the spectral distribution of random matrices

  2008cited by this paper
• A Universality Result for the Smallest Eigenvalues of Certain Sample Covariance Matrices

  2008influential reference
• RANDOM MATRICES: THE CIRCULAR LAW

  2007cited by this paper
• The circular law for random matrices

  2007cited by this paper
• On the Circular Law

  2007cited by this paper
• The Littlewood-Offord problem and invertibility of random matrices

  2007influential reference
• Bounds on the concentration function in terms of Diophantine approximation

  2007influential reference
• Polynomial bounds for large Bernoulli sections of l N 1

  2007cited by this paper
• Polynomial bounds for Large Bernoulli sections of ℓ1N

  2006cited by this paper
• Finding blocks and other patterns in a random coloring of Z

  2006cited by this paper
• Lower estimates for the singular values of random matrices

  2006cited by this paper
• On random ±1 matrices: Singularity and determinant

  2006cited by this paper
• Uniform Uncertainty Principle for Bernoulli and Subgaussian Ensembles

  2006cited by this paper
• Additive Combinatorics: Long arithmetic progressions in sum sets

  2006influential reference
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices

  2005cited by this paper
• On the singularity probability of random Bernoulli matrices

  2005cited by this paper
• Invertibility of random matrices: norm of the inverse

  2005influential reference
• Smallest singular value of random matrices and geometry of random polytopes

  2005cited by this paper
• Euclidean embeddings in spaces of finite volume ratio via random matrices

  2005cited by this paper
• Decoding by linear programming

  2005influential reference
• A Sharp Small Deviation Inequality for the Largest Eigenvalue of a Random Matrix

  2005cited by this paper
• Some estimates of norms of random matrices

  2005cited by this paper
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?

  2004influential reference
• SOME ESTIMATES OF NORMS OF RANDOM MATRICES

  2004influential reference
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices

  2003influential reference
• Very tight embeddings of subspaces of Lp, 1 ≤ p < 2, into lpn

  2003cited by this paper
• A new proof of Федоров theorem

  2003cited by this paper
• Distribution Functions for Largest Eigenvalues and Their Applications

  2002cited by this paper
• Smoothed Analysis of Algorithms

  2002influential reference
• The concentration of measure phenomenon

  2001cited by this paper
• Gaussian processes: Inequalities, small ball probabilities and applications

  2001cited by this paper
• On the distribution of the largest eigenvalue in principal components analysis

  2001cited by this paper
• Extremal Problems in Number Theory

  2001cited by this paper
• Chapter 8 - Local Operator Theory, Random Matrices and Banach Spaces

  2001cited by this paper
• A Note on Universality of the Distribution of the Largest Eigenvalues in Certain Sample Covariance Matrices

  2001cited by this paper
• Dimensionality reduction techniques for proximity problems

  2000cited by this paper
• Shape Fluctuations and Random Matrices

  1999cited by this paper
• METHODOLOGIES IN SPECTRAL ANALYSIS OF LARGE DIMENSIONAL RANDOM MATRICES , A REVIEW

  1999cited by this paper
• A new look at independence

  1996cited by this paper
• Se p 19 95 On Orthogonal and Symplectic Matrix Ensembles

  1996cited by this paper
• On the probability that a random ±1-matrix is singular

  1995cited by this paper
• Mathematical Physics © Springer-Verlag 1996 On Orthogonal and Symplectic Matrix Ensembles

  1995cited by this paper
• Concentration of measure and isoperimetric inequalities in product spaces

  1994cited by this paper
• Limit of the smallest eigenvalue of a large dimensional sample covariance matrix

  1993influential reference
• Majorization of Gaussian processes and geometric applications

  1992influential reference
• Mathematical Physics © Springer-Verlag 1994 Level-Spacing Distributions and the Airy Kernel

  1992cited by this paper
• Condition numbers of random matrices

  1991cited by this paper
• Probability in Banach Spaces: Isoperimetry and Processes

  1991cited by this paper
• On the limit of the largest eigenvalue of the large dimensional sample covariance matrix

  1988cited by this paper
• Eigenvalues and condition numbers of random matrices

  1988influential reference
• A note on the largest eigenvalue of a large dimensional sample covariance matrix

  1988cited by this paper
• Solution of the Littlewood-Offord problem in high dimensions

  1988cited by this paper
• Asymptotic Theory Of Finite Dimensional Normed Spaces

  1986influential reference
• The Smallest Eigenvalue of a Large Dimensional Wishart Matrix

  1985influential reference
• On the efficiency of algorithms of analysis

  1985cited by this paper
• Some inequalities for Gaussian processes and applications

  1985cited by this paper
• Random embeddings of Euclidean spaces in sequence spaces

  1981influential reference
• A Limit Theorem for the Norm of Random Matrices

  1980cited by this paper
• Probability on Banach spaces

  1978influential reference
• On uncomplemented subspaces ofLp, 1

  1977cited by this paper
• Estimates for the concentration function of combinatorial number theory and probability

  1977cited by this paper
• On the spectrum of random matrices

  1972cited by this paper
• On the Kolmogorov-Rogozin inequality for the concentration function

  1966cited by this paper
• Über ein Problem von Erdös und Moser

  1965cited by this paper
• The one-sided barrier problem for Gaussian noise

  1962cited by this paper
• On the Distribution of the Roots of Certain Symmetric Matrices

  1958cited by this paper
• Théorie de l'addition des variables aléatoires

  1955cited by this paper
• Numerical inverting of matrices of high order

  1947cited by this paper
• Fourier analysis of distribution functions. A mathematical study of the Laplace-Gaussian law

  1945cited by this paper
• On a lemma of Littlewood and Offord

  1945cited by this paper
• The accuracy of the Gaussian approximation to the sum of independent variates

  1941cited by this paper
• On the number of real roots of a random algebraic equation. II

  1939influential reference
• On the Number of Real Roots of a Random Algebraic Equation

  1938cited by this paper
• Compressive Sampling

  year unknowncited by this paper
• Presented by?????

  year unknowncited by this paper

• Preconditioning Benefits of Spectral Orthogonalization in Muon

  2026influential citation
• LDLT L-Lipschitz Network Weight Parameterization Initialization

  2026cites this paper
• Extending $\mu$P: Spectral Conditions for Feature Learning Across Optimizers

  2026cites this paper
• Training Dynamics of Softmax Self-Attention: Fast Global Convergence via Preconditioning

  2026cites this paper
• The condition number of a random banded Toeplitz matrix is typically large

  2026cites this paper
• Diffusion Generative Models Meet Compressed Sensing, with Applications to Imaging and Finance

  2025cites this paper
• Random Matrices, Intrinsic Freeness, and Sharp Non-Asymptotic Inequalities

  2025cites this paper
• Impact of Coded Excitation Transmits on Singular Value Decomposition for Power Doppler Filtering

  2025cites this paper
• On the Emergence of Linear Analogies in Word Embeddings

  2025cites this paper
• Toward Efficient Influence Function: Dropout as a Compression Tool

  2025cites this paper
• Distributed Kalman Filter With Ultimately Accurate Fused Measurement Covariance

  2025cites this paper
• On the Clustering of Padé Zeros and Poles of Random Power Series

  2025cites this paper
• Sequences of Logits Reveal the Low Rank Structure of Language Models

  2025cites this paper
• Tightness of SDP and Burer–Monteiro Factorization for Phase Synchronization in a High-Noise Regime

  2025influential citation
• Adaptive Robustness of Hypergrid Johnson-Lindenstrauss

  2025cites this paper
• On the Smallest Singular Value of Log-Concave Random Matrices

  2025cites this paper
• Symmetric Perceptrons, Number Partitioning and Lattices

  2025cites this paper
• Explaining Concept Shift with Interpretable Feature Attribution

  2025influential citation
• High-Probability Polynomial-Time Complexity of Restarted PDHG for Linear Programming

  2025cites this paper
• Convergence of Adam in Deep ReLU Networks via Directional Complexity and Kakeya Bounds

  2025cites this paper
• Optimal sub-Gaussian variance proxy for 3-mass distributions

  2025cites this paper
• Deep Learning for Computational Imaging

  2025cites this paper
• "Univariate-Guided Sparse Regression": Rejoinder

  2025influential citation
• Probability inequalities for sums of partly acceptable random variables with finite moments

  2025cites this paper
• A structural bound for cluster robustness of randomized small-block Lanczos

  2025influential citation
• Multilook Coherent Imaging: Theoretical Guarantees and Algorithms

  2025cites this paper
• Sparse Linear Regression and Lattice Problems

  2024cites this paper
• Bagged Deep Image Prior for Recovering Images in the Presence of Speckle Noise

  2024cites this paper
• On the clustering of Pad\'e zeros and poles of random power series

  2024cites this paper
• Concentration inequality and the weak law of large numbers for the sum of partly negatively dependent φ-subgaussian random variables

  2024cites this paper
• Multiple augmented reduced rank regression for pan-cancer analysis.

  2024cites this paper
• Dynamic relationship between the XRP price and correlation tensor spectra of transaction networks

  2024cites this paper
• Empirical Bayes linked matrix decomposition

  2024cites this paper
• eGAD! double descent is explained by Generalized Aliasing Decomposition

  2024influential citation
• Spectral Guarantees for Adversarial Streaming PCA

  2024cites this paper
• The smallest singular value for rectangular random matrices with L\'evy entries

  2024cites this paper
• Estimating Neural Network Robustness via Lipschitz Constant and Architecture Sensitivity

  2024cites this paper
• MotionTTT: 2D Test-Time-Training Motion Estimation for 3D Motion Corrected MRI

  2024influential citation
• Least non-zero singular value and the distribution of eigenvectors of non-Hermitian random matrices

  2024cites this paper
• Simple Relative Deviation Bounds for Covariance and Gram Matrices

  2024influential citation
• Arbitrage Impact on the Relationship Between XRP Price and Correlation Tensor Spectra of Transaction Networks

  2024cites this paper
• On the sparsity of non-diagonalisable integer matrices and matrices with a given discriminant

  2023cites this paper
• Precise Asymptotic Generalization for Multiclass Classification with Overparameterized Linear Models

  2023influential citation
• A Spectral Condition for Feature Learning

  2023cites this paper
• Optimal Embedding Dimension for Sparse Subspace Embeddings

  2023cites this paper
• Dynamic relationship between XRP price and correlation tensor spectra of the transaction network

  2023cites this paper
• Subspace Change Point Detection Under Spiked Wigner Model

  2023cites this paper
• The Inductive Bias of Flatness Regularization for Deep Matrix Factorization

  2023cites this paper
• Optimal Subspace Perturbation Bounds under Gaussian Noise

  2023cites this paper
• On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation

  2023cites this paper
• Joint Message Detection and Channel Estimation for Unsourced Random Access in Cell-Free User-Centric Wireless Networks

  2023cites this paper
• Exploiting Observation Bias to Improve Matrix Completion

  2023cites this paper
• Multiple Augmented Reduced Rank Regression for Pan-Cancer Analysis.

  2023cites this paper
• Randomly Projected Convex Clustering Model: Motivation, Realization, and Cluster Recovery Guarantees

  2023influential citation
• Scaling Laws For Deep Learning Based Image Reconstruction

  2022cites this paper
• Optimal Query Complexities for Dynamic Trace Estimation

  2022cites this paper
• On convergence and optimality of maximum-likelihood APA

  2022cites this paper
• From Optimization Dynamics to Generalization Bounds via Łojasiewicz Gradient Inequality

  2022influential citation
• Regularization Trade-offs with Fake Features

  2022cites this paper
• Quantum tomography using state-preparation unitaries

  2022cites this paper
• One-dimensional Tensor Network Recovery

  2022influential citation
• Extreme singular values of inhomogeneous sparse random rectangular matrices

  2022cites this paper
• Revisiting the hierarchical construction of higher-order exceptional points

  2022cites this paper
• Declarative nets that are equilibrium models

  2022cites this paper
• Faster Rates of Convergence to Stationary Points in Differentially Private Optimization

  2022cites this paper
• Fluctuations of The Symmetric Perceptron

  2022cites this paper
• Overparametrized linear dimensionality reductions: From projection pursuit to two-layer neural networks

  2022cites this paper
• Blind Estimation of a Doubly Selective OFDM Channel: A Deep Learning Algorithm and Theory

  2022cites this paper
• Manifold Principle Component Analysis for Large-Dimensional Matrix Elliptical Factor Model

  2022cites this paper
• LoCoV: low dimension covariance voting algorithm for portfolio optimization

  2022cites this paper
• High-Dimensional Projection Pursuit: Outer Bounds and Applications to Interpolation in Neural Networks

  2022cites this paper
• Estimation and Model Misspecification: Fake and Missing Features

  2022cites this paper
• From multilinear SVD to multilinear UTV decomposition

  2022cites this paper
• A Class of Sparse Johnson-Lindenstrauss Transforms and Analysis of their Extreme Singular Values

  2022influential citation
• Distributed Optimization for Overparameterized Problems: Achieving Optimal Dimension Independent Communication Complexity

  2022cites this paper
• Bayesian simultaneous factorization and prediction using multi-omic data

  2022cites this paper
• Estimation Under Model Misspecification With Fake Features

  2022cites this paper
• Regularization with Fake Features

  2022cites this paper
• Recover the spectrum of covariance matrix: a non-asymptotic iterative method

  2022cites this paper
• Concentration inequality of sums of dependent subexponential random variables and application to bounds for value-at-risk

  2022cites this paper
• Connecting Optimization and Generalization via Gradient Flow Path Length

  2022cites this paper
• Inference in latent factor regression with clusterable features

  2022cites this paper
• Why Is Everyone Training Very Deep Neural Network With Skip Connections?

  2022cites this paper
• A new perspective for understanding generalization gap of deep neural networks trained with large batch sizes

  2022cites this paper
• Critical window of the symmetric perceptron

  2022cites this paper
• Projecting XRP price burst by correlation tensor spectra of transaction networks

  2022cites this paper
• A Randomised Subspace Gauss-Newton Method for Nonlinear Least-Squares

  2022cites this paper
• Symphony in the Latent Space: Provably Integrating High-dimensional Techniques with Non-linear Machine Learning Models

  2022cites this paper
• Improved analysis of randomized SVD for top-eigenvector approximation

  2022cites this paper
• Characteristics-Driven Returns in Equilibrium

  2022cites this paper
• Inverse Feasibility in Over-the-Air Federated Learning

  2022cites this paper
• Polynomial-time sparse measure recovery

  2022cites this paper
• Quantitative invertibility of non-Hermitian random matrices

  2022cites this paper
• Robust recovery of low-rank matrices and low-tubal-rank tensors from noisy sketches

  2022cites this paper
• Efficient greedy coordinate descent via variable partitioning

  2021cites this paper
• Successful Recovery Performance Guarantees of Noisy SOMP

  2021cites this paper
• The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks

  2021cites this paper
• A NEW ROBUST SCALABLE SINGULAR VALUE DECOMPOSITION ALGORITHM FOR VIDEO SURVEILLANCE BACKGROUND MODELLING BY SUBHRAJYOTY ROY*,

  2021cites this paper
• Non-Asymptotic Bounds for the `∞ Estimator in Linear Regression with Uniform Noise

  2021cites this paper
• The Smallest Singular Value of a Shifted Random Matrix

  2021cites this paper