Sparse recovery under matrix uncertainty

Abstract

We consider the model {eqnarray*}y=Xθ^*+ξ, Z=X+Ξ,{eqnarray*} where the random vector $y\in {\mathbb{R}}^n$ and the random $n\times p$ matrix $Z$ are observed, the $n\times p$ matrix $X$ is unknown, $\Xi$ is an $n\times p$ random noise matrix, $\xi \in {\mathbb{R}}^n$ is a noise independent of $\Xi$, and ${\theta }^{\ast }$ is a vector of unknown parameters to be estimated. The matrix uncertainty is in the fact that $X$ is observed with additive error. For dimensions $p$ that can be much larger than the sample size $n$, we consider the estimation of sparse vectors ${\theta }^{\ast }$. Under matrix uncertainty, the Lasso and Dantzig selector turn out to be extremely unstable in recovering the sparsity pattern (i.e., of the set of nonzero components of ${\theta }^{\ast }$), even if the noise level is very small. We suggest new estimators called matrix uncertainty selectors (or, shortly, the MU-selectors) which are close to ${\theta }^{\ast }$ in different norms and in the prediction risk if the restricted eigenvalue assumption on $X$ is satisfied. We also show that under somewhat stronger assumptions, these estimators recover correctly the sparsity pattern.

Published in at http://dx.doi.org/10.1214/10-AOS793 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (13)

• High-dimensional graphs and variable selection with the Lasso
• Simultaneous analysis of Lasso and Dantzig selector
• The sparsity and bias of the Lasso selection in high-dimensional linear regression
• Sparse and stable Markowitz portfolios
• High-dimensional generalized linear models and the lasso
• Sparsity oracle inequalities for the Lasso
• Aggregation for Gaussian regression
• The Dantzig selector and sparsity oracle inequalities
• Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators
• Some sharp performance bounds for least squares regression with $L_1$ regularization
• Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity
• Sparse Regression Learning by Aggregation and Langevin Monte-Carlo
• High-dimensional stochastic optimization with the generalized Dantzig estimator

Cited by in corpus (46)

• Least squares after model selection in high-dimensional sparse models
• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• Robust subspace clustering
• Joint Sparse Recovery Method for Compressed Sensing with Structured Dictionary Mismatches
• Pivotal estimation via square-root Lasso in nonparametric regression
• High-dimensional instrumental variables regression and confidence sets
• Learning partial differential equations for biological transport models from noisy spatiotemporal data
• Measurement Error in Lasso: Impact and Correction
• L1-Penalized Quantile Regression in High-Dimensional Sparse Models
• Sparse Portfolio Selection via Quasi-Norm Regularization
• Covariate Selection in High-Dimensional Generalized Linear Models With Measurement Error
• Precise Performance Analysis of the Box-Elastic Net under Matrix Uncertainties
• Compressed Sensing under Matrix Uncertainty: Optimum Thresholds and Robust Approximate Message Passing
• Pivotal Estimation via Self-Normalization for High-Dimensional Linear Models with Error in Variables
• Robust High Dimensional Sparse Regression and Matching Pursuit
• Orthogonal Matching Pursuit with Noisy and Missing Data: Low and High Dimensional Results
• Two Stage Non-penalized Corrected Least Squares for High Dimensional Linear Models with Measurement error or Missing Covariates
• Valid Post-selection Inference in Assumption-lean Linear Regression
• High dimensional errors-in-variables models with dependent measurements
• CoCoLasso for High-dimensional Error-in-variables Regression
• Online and Distributed Robust Regressions under Adversarial Data Corruption
• Model-Based Calibration of Filter Imperfections in the Random Demodulator for Compressive Sensing
• An $\{l_1,l_2,l_{\infty }\}$-Regularization Approach to High-Dimensional Errors-in-variables Models
• Non-separable covariance models for spatio-temporal data, with applications to neural encoding analysis
• Alternating minimization for dictionary learning: Local Convergence Guarantees
• Keeping greed good: sparse regression under design uncertainty with application to biomass characterization
• RIDS: Robust Identification of Sparse Gene Regulatory Networks from Perturbation Experiments
• Scalable Interpretable Learning for Multi-Response Error-in-Variables Regression
• Adaptive Feature Selection: Computationally Efficient Online Sparse Linear Regression under RIP
• Inference in High-Dimensional Linear Measurement Error Models
• Vector Approximate Message Passing Algorithm for Structured Perturbed Sensing Matrix
• High-dimensional Log-Error-in-Variable Regression with Applications to Microbial Compositional Data Analysis
• Sparse Density Estimation with Measurement Errors
• Calibrated zero-norm regularized LS estimator for high-dimensional error-in-variables regression
• Debiasing Stochastic Gradient Descent to handle missing values
• Low-rank matrix estimation in multi-response regression with measurement errors: Statistical and computational guarantees
• A Simple Correction Procedure for High-Dimensional Generalized Linear Models with Measurement Error
• Imputation for High-Dimensional Linear Regression
• High-Dimensional Semiparametric Selection Models: Estimation Theory with an Application to the Retail Gasoline Market
• High-dimensional instrumental variables regression and confidence sets -- v2/2012
• Errors-in-variables models with dependent measurements
• Network Reconstruction From High Dimensional Ordinary Differential Equations
• Neighborhood selection with application to social networks
• HMLasso: Lasso with High Missing Rate
• Deep learning for inverse problems with unknown operator
• Robust Elastic Net Regression