  We consider the linear regression model with observation error in the design.
In this setting, we allow the number of covariates to be much larger than the
sample size. Several new estimation methods have been recently introduced for
this model. Indeed, the standard Lasso estimator or Dantzig selector turn out
to become unreliable when only noisy regressors are available, which is quite
common in practice. We show in this work that under suitable sparsity
assumptions, the procedure introduced in Rosenbaum and Tsybakov (2013) is
almost optimal in a minimax sense and, despite non-convexities, can be
efficiently computed by a single linear programming problem. Furthermore, we
provide an estimator attaining the minimax efficiency bound. This estimator is
written as a second order cone programming minimisation problem which can be
solved numerically in polynomial time.
