Restricted Eigenvalue Conditions on Subgaussian Random Matrices

Abstract

It is natural to ask: what kinds of matrices satisfy the Restricted Eigenvalue (RE) condition? In this paper, we associate the RE condition (Bickel-Ritov-Tsybakov 09) with the complexity of a subset of the sphere in ${\mathbb{R}}^p$, where $p$ is the dimensionality of the data, and show that a class of random matrices with independent rows, but not necessarily independent columns, satisfy the RE condition, when the sample size is above a certain lower bound. Here we explicitly introduce an additional covariance structure to the class of random matrices that we have known by now that satisfy the Restricted Isometry Property as defined in Candes and Tao 05 (and hence the RE condition), in order to compose a broader class of random matrices for which the RE condition holds. In this case, tools from geometric functional analysis in characterizing the intrinsic low-dimensional structures associated with the RE condition has been crucial in analyzing the sample complexity and understanding its statistical implications for high dimensional data.

24 Pages

References in corpus (2)

• Adaptive Lasso for High Dimensional Regression and Gaussian Graphical Modeling
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling

Cited by in corpus (28)

• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Loss minimization and parameter estimation with heavy tails
• High-dimensional covariance estimation based on Gaussian graphical models
• Wireless Compressive Sensing for Energy Harvesting Sensor Nodes
• Global and Simultaneous Hypothesis Testing for High-Dimensional Logistic Regression Models
• Thresholded Lasso for high dimensional variable selection and statistical estimation
• Statistically and Computationally Efficient Change Point Localization in Regression Settings
• Reconstruction from anisotropic random measurements
• A general theory of regression adjustment for covariate-adaptive randomization: OLS, Lasso, and beyond
• Transfer Learning for High-dimensional Linear Regression: Prediction, Estimation, and Minimax Optimality
• Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression
• Minimax Optimal Sparse Signal Recovery with Poisson Statistics
• Confidence Intervals for Causal Effects with Invalid Instruments using Two-Stage Hard Thresholding with Voting
• Sparse Signal Recovery under Poisson Statistics
• Two-step estimation of high dimensional additive models
• On the consistency theory of high dimensional variable screening
• Optimal Estimation of Co-heritability in High-dimensional Linear Models
• ${\ell }_1$-penalized Multinomial Regression: Estimation, inference, and prediction, with an application to risk factor identification for different dementia subtypes
• Minimax optimal convex methods for Poisson inverse problems under ${\ell }_q$-ball sparsity
• Simultaneous prediction and community detection for networks with application to neuroimaging
• Calibrated Multivariate Regression with Application to Neural Semantic Basis Discovery
• Energy-Efficient Sensor Censoring for Compressive Distributed Sparse Signal Recovery
• Statistical Inference for High-Dimensional Linear Regression with Blockwise Missing Data
• On Quadratic Convergence of DC Proximal Newton Algorithm for Nonconvex Sparse Learning in High Dimensions
• Non-Asymptotic Bounds for the ${\ell }_{\infty }$ Estimator in Linear Regression with Uniform Noise
• Testing Mediation Effects Using Logic of Boolean Matrices
• New Error Analysis for Lasso
• A Smoothed Analysis of Online Lasso for the Sparse Linear Contextual Bandit Problem