We consider the problem of learning a coefficient vector x0\in{\BBR}^{N} from noisy linear observation y=Ax0+w\in{\BBR}^{n}. In many contexts (ranging from model selection to image processing), it is desirable to construct a sparse estimator \widehat x. In this case, a popular approach consists in solving an \ell1-penalized least-squares problem known as the LASSO or basis pursuit denoising.
