Reconstruction from anisotropic random measurements

Abstract

Random matrices are widely used in sparse recovery problems, and the relevant properties of matrices with i.i.d. entries are well understood. The current paper discusses the recently introduced Restricted Eigenvalue (RE) condition, which is among the most general assumptions on the matrix, guaranteeing recovery. We prove a reduction principle showing that the RE condition can be guaranteed by checking the restricted isometry on a certain family of low-dimensional subspaces. This principle allows us to establish the RE condition for several broad classes of random matrices with dependent entries, including random matrices with subgaussian rows and non-trivial covariance structure, as well as matrices with independent rows, and uniformly bounded entries.

30 Pages

References in corpus (7)

• Simultaneous analysis of Lasso and Dantzig selector
• High-dimensional covariance estimation based on Gaussian graphical models
• Adaptive Lasso for High Dimensional Regression and Gaussian Graphical Modeling
• Restricted Eigenvalue Conditions on Subgaussian Random Matrices
• Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements
• Approximating the moments of marginals of high-dimensional distributions
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling

Cited by in corpus (9)

• Statistical Inference for Model Parameters in Stochastic Gradient Descent
• Bayesian Sparse Linear Regression with Unknown Symmetric Error
• Inference for high-dimensional instrumental variables regression
• LASSO-Driven Inference in Time and Space
• Detection and estimation of parameters in high dimensional multiple change point regression models via ${\ell }_1/{\ell }_0$ regularization and discrete optimization
• High-dimensional Inference for Dynamic Treatment Effects
• A Knowledge Transfer Framework for Differentially Private Sparse Learning
• High Dimensional Logistic Regression Under Network Dependence
• Adaptive Estimation In High-Dimensional Additive Models With Multi-Resolution Group Lasso