The lower tail of random quadratic forms, with applications to ordinary least squares and restricted eigenvalue properties

Abstract

Finite sample properties of random covariance-type matrices have been the subject of much research. In this paper we focus on the "lower tail" of such a matrix, and prove that it is subgaussian under a simple fourth moment assumption on the one-dimensional marginals of the random vectors. A similar result holds for more general sums of random positive semidefinite matrices, and the (relatively simple) proof uses a variant of the so-called PAC-Bayesian method for bounding empirical processes. We give two applications of the main result. In the first one we obtain a new finite-sample bound for ordinary least squares estimator in linear regression with random design. Our result is model-free, requires fairly weak moment assumptions and is almost optimal. Our second application is to bounding restricted eigenvalue constants of certain random ensembles with "heavy tails". These constants are important in the analysis of problems in Compressed Sensing and High Dimensional Statistics, where one recovers a sparse vector from a small umber of linear measurements. Our result implies that heavy tails still allow for the fast recovery rates found in efficient methods such as the LASSO and the Dantzig selector. Along the way we strengthen, with a fairly short argument, a recent result of Rudelson and Zhou on the restricted eigenvalue property.

36 pages

Cited by in corpus (13)

• Compressed Sensing with Deep Image Prior and Learned Regularization
• Moving Beyond Sub-Gaussianity in High-Dimensional Statistics: Applications in Covariance Estimation and Linear Regression
• Simpler PAC-Bayesian Bounds for Hostile Data
• On Stein's Identity and Near-Optimal Estimation in High-dimensional Index Models
• Structured Recovery with Heavy-tailed Measurements: A Thresholding Procedure and Optimal Rates
• Sample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso
• Outlier-robust estimation of a sparse linear model using ${\ell }_1$-penalized Huber's $M$-estimator
• Berry-Esseen Bounds for Projection Parameters and Partial Correlations with Increasing Dimension
• Outlier-robust sparse/low-rank least-squares regression and robust matrix completion
• Restricted eigenvalue property for corrupted Gaussian designs
• The Function-on-Scalar LASSO with Applications to Longitudinal GWAS
• II. High Dimensional Estimation under Weak Moment Assumptions: Structured Recovery and Matrix Estimation
• A remark on weaken restricted isometry property in compressed sensing