Simple algorithms for sparse linear regression with uncertain covariates

In this short paper we consider sparse linear regression with missing or noisy covariates. This problem has recently attracted some attention, with the best known results given in [1], where they use a projected gradient approach to approximately solve a non convex optimization problem. Here we show that an extremely simple, lower complexity algorithm that achieves the same (or better) bounds for support recovery.