On the interval of fluctuation of the singular values of random matrices

DOI10.4171/JEMS/697MaRDI QIDQ2628338zbMATH OpenFDO

Authors Olivier Guédon, Alain Pajor, Alexander E. Litvak, Nicole Tomczak-Jaegermann

Publication date 1 June 2017

Published in Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

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

zbMATH Keywords

approximation of covariance matricescompressed sensingconcentration inequalitiesdeviation inequalitiesheavy tailslog-concave random vectorsnorm of random matricesorder statisticsrandom matricesrestricted isometry propertysingular valuesspectrum

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Probabilistic methods in Banach space theory (46B09) Random matrices (probabilistic aspects) (60B20)

Abstract: Let $A$ be a matrix whose columns $X_1,dots,X_N$ are independent random vectors in $mathbb{R}^n$. Assume that the tails of the 1-dimensional marginals decay as $mathbbP(|langle{X}_i,aangle|geqt)leq{t}^{-p}$ uniformly in $ain{S}^{n-1}$ and $ileqN$. Then for $p>4$ we prove that with high probability $A/sqrtn$ has the Restricted Isometry Property (RIP) provided that Euclidean norms $|X_i|$ are concentrated around $sqrtn$. We also show that the covariance matrix is well approximated by the empirical covariance matrix and establish corresponding quantitative estimates on the rate of convergence in terms of the ratio $n/N$. Moreover, we obtain sharp bounds for both problems when the decay is of the type $exp(-t^{alpha})$ with $alphain(0,2]$, extending the known case $alphain[1,2]$.

Review text

Summary: Let \(A\) be a matrix whose columns \(X_1,\ldots, X_N\) are independent random vectors in \(\mathbb R^n\). Assume that the tails of the 1-dimensional marginals decay as \(\mathbb{P}(|\langle X_i, a\rangle|\geq t)\leq C t^{-p}\) uniformly in \(a\in S^{n-1}\) and \(i\leq N\). Then for \(p4\) we prove that with high probability \(A/\sqrt{n}\) has the restricted isometry property (RIP) provided that Euclidean norms \(|X_i|\) are concentrated around \(\sqrt{n}\). We also show that the covariance matrix is well approximated by empirical covariance matrices and establish corresponding quantitative estimates on the rate of convergence in terms of the ratio \(nN\). Moreover, we obtain sharp bounds for both problems when the decay is of the type exp \((-t^{\alpha})\), with \(\alpha \in (0,2]\), extending the known case \(\alpha \in (1,2]\).

Recommendations

• Restricted isometry property for random matrices with heavy-tailed columns
• Sharp bounds on the rate of convergence of the empirical covariance matrix
• On the singular values of random matrices
• The smallest singular value of heavy-tailed not necessarily i.i.d. random matrices via random rounding
• Strong Law for the singular values and eigenvectors of random matrices I

Cites work

• A note on the largest eigenvalue of a large dimensional sample covariance matrix
• Best constants in moment inequalities for linear combinations of independent and exchangeable random variables
• Bounding the smallest singular value of a random matrix without concentration
• Compressed sensing
• Concentration of mass on convex bodies
• Condition numbers of random matrices
• Covariance estimation for distributions with \({2+\varepsilon}\) moments
• Decoding by Linear Programming
• Eigenvalues and Condition Numbers of Random Matrices
• Geometry of log-concave ensembles of random matrices and approximate reconstruction
• How close is the sample covariance matrix to the actual covariance matrix?
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 1302647 (Why is no real title available?)
• Interpolating thin-shell and sharp large-deviation estimates for isotropic log-concave measures
• Limit of the smallest eigenvalue of a large dimensional sample covariance matrix
• Lower bounds on the smallest eigenvalue of a sample covariance matrix.
• On generic chaining and the smallest singular value of random matrices with heavy tails
• On higher order isotropy conditions and lower bounds for sparse quadratic forms
• On the singular values of random matrices
• On the subspaces of \(L^p\) \((p > 2)\) spanned by sequences of independent random variables
• On the weak limit of the largest eigenvalue of a large dimensional sample covariance matrix
• Power-law estimates for the central limit theorem for convex sets
• Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles
• Quantitative Version of a Silverstein’s Result
• Reconstruction and subgaussian operators in asymptotic geometric analysis
• Restricted isometry property for random matrices with heavy-tailed columns
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
• Sharp bounds on the rate of convergence of the empirical covariance matrix
• Small ball probability estimates for log-concave measures
• Smallest singular value of random matrices with independent columns
• Sparse recovery under weak moment assumptions
• Stable signal recovery from incomplete and inaccurate measurements
• The lower tail of random quadratic forms with applications to ordinary least squares
• The smallest singular value of random rectangular matrices with no moment assumptions on entries

Cited in

(18)

• Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries
• The smallest singular value of a shifted d-regular random square matrix
• Singularity dominated strong fluctuations for some random matrix averages
• Sampling discretization and related problems
• The lower tail of random quadratic forms with applications to ordinary least squares
• Invertibility of random submatrices via tail-decoupling and a matrix Chernoff inequality
• Fluctuation of Matrix Entries and Application to Outliers of Elliptic Matrices
• Random polytopes obtained by matrices with heavy-tailed entries
• Quantitative Version of a Silverstein’s Result
• Local tail statistics of heavy-tailed random matrix ensembles with unitary invariance
• Sharp bounds on the rate of convergence of the empirical covariance matrix
• Extreme singular values of inhomogeneous sparse random rectangular matrices
• Covariance estimation under missing observations and L₄ - L₂ moment equivalence
• Asymptotic geometric analysis: achievements and perspective
• Covariance estimation: optimal dimension-free guarantees for adversarial corruption and heavy tails
• A geometrical analysis of kernel ridge regression and its applications
• An upper bound on the smallest singular value of a square random matrix
• Concentration and moment inequalities for sums of independent heavy-tailed random matrices

This page was built for publication: On the interval of fluctuation of the singular values of random matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2628338)