Minimax Rates of <i>ℓ</i>_<i>p</i>-Losses for High-Dimensional Linear Errors-in-Variables Models over <i>ℓ</i>_<i>q</i>-Balls

Abstract

In this paper, the high-dimensional linear regression model is considered, where the covariates are measured with additive noise. Different from most of the other methods, which are based on the assumption that the true covariates are fully obtained, results in this paper only require that the corrupted covariate matrix is observed. Then, by the application of information theory, the minimax rates of convergence for estimation are investigated in terms of the ℓp(1≤p∞)-losses under the general sparsity assumption on the underlying regression parameter and some regularity conditions on the observed covariate matrix. The established lower and upper bounds on minimax risks agree up to constant factors when p=2, which together provide the information-theoretic limits of estimating a sparse vector in the high-dimensional linear errors-in-variables model. An estimator for the underlying parameter is also proposed and shown to be minimax optimal in the ℓ2-loss.

Keywords

• sparse linear regression
• errors-in-variables model
• minimax rate
• Kullback–Leibler divergence
• information-theoretic limitations