Orthogonal Matching Pursuit with Noisy and Missing Data: Low and High Dimensional Results

Abstract

Many models for sparse regression typically assume that the covariates are known completely, and without noise. Particularly in high-dimensional applications, this is often not the case. This paper develops efficient OMP-like algorithms to deal with precisely this setting. Our algorithms are as efficient as OMP, and improve on the best-known results for missing and noisy data in regression, both in the high-dimensional setting where we seek to recover a sparse vector from only a few measurements, and in the classical low-dimensional setting where we recover an unstructured regressor. In the high-dimensional setting, our support-recovery algorithm requires no knowledge of even the statistics of the noise. Along the way, we also obtain improved performance guarantees for OMP for the standard sparse regression problem with Gaussian noise.

Minor revision. Appeared at ICML 2013 under the title "Noisy and Missing Data Regression: Distribution-Oblivious Support Recovery"

References in corpus (1)

• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity

Cited by in corpus (6)

• Measurement Error in Lasso: Impact and Correction
• Fast and Robust Least Squares Estimation in Corrupted Linear Models
• On Robustness of Principal Component Regression
• Pivotal Estimation via Self-Normalization for High-Dimensional Linear Models with Error in Variables
• Robust High Dimensional Sparse Regression and Matching Pursuit
• An $\{l_1,l_2,l_{\infty }\}$-Regularization Approach to High-Dimensional Errors-in-variables Models