Before revision:  The main result is that under these conditions the Euclidean error of recovering the true regressor is of the order of the average noise level . Hence, the regressor recovered by basis pursuit is close to the truth if the average noise level is small . Lower bounds that show near optimality of the results complement the analysis .
After revision:  The main result is that under these conditions the Euclidean error of recovering the true regressor is of the order of the average noise level , provided that the overparameterization is at least a logarithmic factor larger than the number of samples . Lower bounds that show near optimality of the results complement the analysis .