SPARSE RECOVERY UNDER MATRIX UNCERTAINTY

• 成果类型: Article
• 署名作者: Rosenbaum, Mathieu; Tsybakov, Alexandre B.
• 署名单位: Institut Polytechnique de Paris; Ecole Polytechnique; Institut Polytechnique de Paris; ENSAE Paris; Sorbonne Universite
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/10-AOS793
• 发表日期: 2010
• 页码: 2620-2651
• 关键词: INVERSE PROBLEMS; DANTZIG SELECTOR; Lasso; aggregation

摘要

We consider the model y = X theta* + xi, Z = X + Xi, where the random vector y is an element of R-n and the random n x p matrix Z are observed, the n x p matrix X is unknown, Xi is an n x p random noise matrix, xi is an element of R-n is a noise independent of Xi, and theta* 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*. 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*), 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* 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.