Before revision:  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 . In addition, these results are extended to low rank trace regression. The proofs rely on new lower tail bounds for maxima of Gaussians vectors and the spectral norm of Gaussian matrices, respectively, and might be of independent interest as they are significantly stronger than the corresponding upper tail bounds .
After revision:  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 .