Sparse recovery under matrix uncertainty

By Mathieu Rosenbaum, Alexandre B. Tsybakov. 2008

174 citations recorded by the source corpus.

We consider the model y - Y0 +, Z- X + 3? where the random vector y ∈ ℝ n and the random n × p matrix Z are observed, the n x p matrix X is unknown, Θ is an n x p random noise matrix, ξ ∈ ℝ n is a noise independent of Θ, and θ * 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 θ * . 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 θ * ), 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 θ * 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.

Subfields: Computational Mechanics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/f5676d7a129ce1100737a719794a2aefec46ce42

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

High-dimensional regression with noisy and missing data: Provable guarantees with non-convexity (2011, background): “In this work, Rosenbaum and Tsybakov derive similar concentration bounds on sub-Gaussian matrices.”
Numerical construction of Green's functions in high dimensional elliptic problems with variable coefficients and analysis of renewable energy data via sparse and separable approximations (2012, methodology): “In [119], the authors develop a Dantzig-like estimator that they argue is more stable than the standard lasso or Dantzig.”
Linear and conic programming estimators in high dimensional errors‐in‐variables models (2014, methodology): “Several aspects of the compensated MU selector were studied in Rosenbaum and Tsybakov (2013), in particular the rates of convergence in lq-norm, the prediction risk and the design of confidence intervals.”
Least squares after model selection in high-dimensional sparse models (2009, background): “See [4, 6, 7, 8, 15, 19, 20, 24] for many other interesting developments and a detailed review of the existing literature.”
Measurement error in Lasso: impact and likelihood bias correction (2012, background): “The same was observed by Rosenbaum and Tsybakov (2010) for censored and missing data.”
High-dimensional instrumental variables regression and confidence sets (2011, methodology): “(2012) who use Lasso type methods to estimate the so-called optimal instruments and obtain optimal conﬁdence for low dimensional structural equations. Caner (2009) studies a Lasso-type GMM estimator. Rosenbaum and Tsybakov (2010) deal with the high-dimensional errors-in-variables problem. The high-d”
Robust Sparse Regression under Adversarial Corruption (2013, background): “It accounts for the effect of the corruption in X being multiplied by β; a similar formulation appears in (Rosenbaum & Tsybakov, 2010; 2011) under a different context.”
Improved Matrix Uncertainty Selector (2011, methodology): “Lemma 1 in Rosenbaum and Tsybakov [12]) and the definition of the sensitivities κq(s), κ ∗ k(s).”
Robust Subspace Clustering (2013, methodology): “3) as the bias-corrected Dantzig selector, which resembles the proposal in [44, 45] for which the constraint is a bit more complicated and of the form ‖Y(−i)(yi − Yβ) + D(−i)β‖ ∞ ≤ μ‖β‖ 1 + λ.”
Network Reconstruction From High-Dimensional Ordinary Differential Equations (2016, unknown): “We extend the recent work of Loh and Wainwright (2012) for lasso regression; related results can be found in Ma and Li (2010) and Rosenbaum and Tsybakov (2010).”
Robust High Dimensional Sparse Regression and Matching Pursuit (2013, background): “Another line of work has developed approaches to handle stochastic noise or small bounded noise in the covariates [17], [26], [27], [23], [9].”
Pivotal estimation via square-root Lasso in nonparametric regression (2011, background): “We refer to [6, 8, 9, 7, 12, 16, 17, 24, 30] for a more detailed review of the existing literature which has been focusing on the homoskedastic case.”
Valid post-selection inference in model-free linear regression (2020, methodology): “The estimator of Rosenbaum and Tsybakov (2010) and Chen et al. (2013) is defined as follows. minimize ‖β‖1 subject to }Γ̂n Σ̂nβ}8 ¤ λn δn ‖β‖1 , for some tuning parameters λn and δn both converging to zero as n increases.”