Noisy and Missing Data Regression: Distribution-Oblivious Support Recovery
作者： Constantine Caramanis , Yudong Chen
DOI:
关键词:
摘要: 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 case. Worse yet, even estimating statistics of noise (the covariance) can be a central challenge. In paper we develop simple variant orthogonal matching pursuit (OMP) precisely setting. We show knowledge covariance, our algorithm recovers support, provide lower bounds performs at minimax optimal rate. While simple, first (provably) support noise-distribution-oblivious manner. When noise-covariance available, matches best-known l2-recovery available. these too min-max optimal. Along way, also obtain improved performance guarantees OMP standard problem with Gaussian
参考文章(18)
Mathieu Rosenbaum, Alexandre B. Tsybakov, Improved Matrix Uncertainty Selector arXiv: Statistics Theory. pp. 276- 290 ,(2013) , 10.1214/12-IMSCOLL920
Yuhong Yang, Andrew Barron, None, Information-theoretic determination of minimax rates of convergence Annals of Statistics. ,vol. 27, pp. 1564- 1599 ,(1999) , 10.1214/AOS/1017939142
Bin Yu, Assouad, Fano, and Le Cam Festschrift for Lucien Le Cam. pp. 423- 435 ,(1997) , 10.1007/978-1-4612-1880-7_29
Po-Ling Loh, Martin J. Wainwright, Corrupted and missing predictors: Minimax bounds for high-dimensional linear regression international symposium on information theory. pp. 2601- 2605 ,(2012) , 10.1109/ISIT.2012.6283989
Nicolas Städler, Peter Bühlmann, Missing values: sparse inverse covariance estimation and an extension to sparse regression Statistics and Computing. ,vol. 22, pp. 219- 235 ,(2012) , 10.1007/S11222-010-9219-7
V.N. Temlyakov, M. Elad, D.L. Donoho, Stable recovery of sparse overcomplete representations in the presence of noise ,(2004)
Po-Ling Loh, Martin J. Wainwright, High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity arXiv: Statistics Theory. ,(2011) , 10.1214/12-AOS1018
Holger Rauhut, On the Impossibility of Uniform Sparse Reconstruction using Greedy Methods Sampling Theory, Signal Processing, and Data Analysis. ,vol. 7, pp. 197- 215 ,(2008) , 10.1007/BF03549495
J.A. Tropp, Greed is good: algorithmic results for sparse approximation IEEE Transactions on Information Theory. ,vol. 50, pp. 2231- 2242 ,(2004) , 10.1109/TIT.2004.834793
Joel A. Tropp, Anna C. Gilbert, Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit IEEE Transactions on Information Theory. ,vol. 53, pp. 4655- 4666 ,(2007) , 10.1109/TIT.2007.909108