Restricted Eigenvalue Conditions on Subgaussian Random Matrices

2009/12/21 by Shuheng Zhou, Zhou, Shuheng · 4 citations
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Machine Learning (stat.ML) #Point processes and geometric inequalities #Random Matrices and Applications #Statistics Theory (math.ST) #Topological and Geometric Data Analysis #math.FA #math.ST #stat.ML #stat.TH

paper · pdf · doi:10.48550/arxiv.0912.4045

24 Pages

openalex publication_date 2009/12/21 · arxiv created 2009/12/27 · arxiv updated 2010/01/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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

Citations

• Atomic Decomposition by Basis Pursuit
• Stable signal recovery from incomplete and inaccurate measurements
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling

Cited by

• Two-step estimation of high dimensional additive models
• A Smoothed Analysis of Online Lasso for the Sparse Linear Contextual Bandit Problem
• Debiasing the Lasso under Weaker Tail Assumptions
• Global and Simultaneous Hypothesis Testing for High-Dimensional Logistic Regression Models

Related

• Reconstruction from anisotropic random measurements
• Random matrices acting on sets: Independent columns
• Restricted Isometry Property under High Correlations
• The lower tail of random quadratic forms, with applications to ordinary least squares and restricted eigenvalue properties
• Bounds on restricted isometry constants of random matrices