Bounding the smallest singular value of a random matrix without concentration

DOI10.1093/IMRN/RNV096MaRDI QIDQ3460356zbMATH OpenOpenAlexFDO

Authors Shahar Mendelson, Vladimir Koltchinskii

Publication date 7 January 2016

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

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

zbMATH Keywords

extremal singular valuelower boundrandom matrix

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Inequalities involving eigenvalues and eigenvectors (15A42) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Abstract: Given $X$ a random vector in ${mathbbR}^n$, set $X_1,\mathrm{...},X_N$ to be independent copies of $X$ and let $Gamma=frac1sqrtNsu{m}_{i=1}^N<X_i,cdot>e_i$ be the matrix whose rows are $frac{X}_{1}sqrtN,dots,frac{X}_{N}sqrtN$. We obtain sharp probabilistic lower bounds on the smallest singular value $lambd{a}_{min}(Gamma)$ in a rather general situation, and in particular, under the assumption that $X$ is an isotropic random vector for which $su{p}_{tin{S}^{n-1}}mathbbE|<t,X>{|}^{2+eta}leqL$ for some $L,eta>0$. Our results imply that a Bai-Yin type lower bound holds for $eta>2$, and, up to a log-factor, for $eta=2$ as well. The bounds hold without any additional assumptions on the Euclidean norm $|X{|}_{el{l}_2^n}$. Moreover, we establish a nontrivial lower bound even without any higher moment assumptions (corresponding to the case $eta=0$), if the linear forms satisfy a weak `small ball' property.

Recommendations

• Sharp lower bounds on the least singular value of a random matrix without the fourth moment condition
• Smallest singular value of a random rectangular matrix
• The smallest singular value of heavy-tailed not necessarily i.i.d. random matrices via random rounding
• The smallest singular value of random rectangular matrices with no moment assumptions on entries
• On the singular values of random matrices

Cited in

(67)

• Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries
• The method of perpendiculars of finding estimates from below for minimal singular eigenvalues of random matrices
• The smallest singular value of a shifted d-regular random square matrix
• Regularization and the small-ball method. I: Sparse recovery
• Slope meets Lasso: improved oracle bounds and optimality
• Simplicial faces of the set of correlation matrices
• Estimation from nonlinear observations via convex programming with application to bilinear regression
• Learning from MOM's principles: Le Cam's approach
• Phase retrieval with PhaseLift algorithm
• Approximating \(L_p\) unit balls via random sampling
• The smallest singular value of heavy-tailed not necessarily i.i.d. random matrices via random rounding
• On Monte-Carlo methods in convex stochastic optimization
• Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices
• On the robustness of minimum norm interpolators and regularized empirical risk minimizers
• Proof methods for robust low-rank matrix recovery
• Penalized least square in sparse setting with convex penalty and non Gaussian errors
• Robust statistical learning with Lipschitz and convex loss functions
• On delocalization of eigenvectors of random non-Hermitian matrices
• Robust machine learning by median-of-means: theory and practice
• Robust classification via MOM minimization
• Complex phase retrieval from subgaussian measurements
• Solving equations of random convex functions via anchored regression
• On aggregation for heavy-tailed classes
• On the convergence of the extremal eigenvalues of empirical covariance matrices with dependence
• Empirical risk minimization: probabilistic complexity and stepsize strategy
• Sharp lower bounds on the least singular value of a random matrix without the fourth moment condition
• On the interval of fluctuation of the singular values of random matrices
• The smallest singular value of random rectangular matrices with no moment assumptions on entries
• Generalized notions of sparsity and restricted isometry property. II: Applications
• High-dimensional robust regression with \(L_q\)-loss functions
• Generic error bounds for the generalized Lasso with sub-exponential data
• Learning without concentration
• Performance of empirical risk minimization in linear aggregation
• Controlling the least eigenvalue of a random Gram matrix
• The lower tail of random quadratic forms with applications to ordinary least squares
• Low rank matrix recovery from rank one measurements
• Stable low-rank matrix recovery via null space properties
• Regularization and the small-ball method. II: Complexity dependent error rates
• On higher order isotropy conditions and lower bounds for sparse quadratic forms
• The limit of the smallest singular value of random matrices with i.i.d. entries
• Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization
• Robust width: a characterization of uniformly stable and robust compressed sensing
• scientific article; zbMATH DE number 7625184 (Why is no real title available?)
• Random polytopes obtained by matrices with heavy-tailed entries
• Sparse recovery under weak moment assumptions
• Simultaneous phase retrieval and blind deconvolution via convex programming
• Deep learning: a statistical viewpoint
• Tyler's and Maronna's M-estimators: non-asymptotic concentration results
• Spiked singular values and vectors under extreme aspect ratios
• Non-asymptotic bounds for the \(\ell_{\infty}\) estimator in linear regression with uniform noise
• Dimension-free bounds for sums of independent matrices and simple tensors via the variational principle
• Local convergence rates of the nonparametric least squares estimator with applications to transfer learning
• Extreme singular values of inhomogeneous sparse random rectangular matrices
• Asymptotic geometric analysis: achievements and perspective
• Low-rank matrix recovery via rank one tight frame measurements
• Covariance estimation with direction dependence accuracy
• Robust outlier bound condition to phase retrieval with adversarial sparse outliers
• Robust Regression with Covariate Filtering: Heavy Tails and Adversarial Contamination
• On the robustness of the minimim _2 interpolator
• A note on the convergence of the extreme eigenvalues of a large-dimensional sample covariance matrix
• An upper bound on the smallest singular value of a square random matrix
• Sharp optimality of sparse group LASSO and SLOPE under weaker assumptions
• The half-quadratic approach for high-dimensional robust M-estimation
• Letter to the editor. Stable low-rank matrix recovery from 3-designs
• Comparison theorems for the minimum eigenvalue of a random positive-semidefinite matrix
• Preserving injectivity under subgaussian mappings and its application to compressed sensing
• Lower estimates for the singular values of random matrices

This page was built for publication: Bounding the smallest singular value of a random matrix without concentration

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