Average case analysis of Lasso under ultra-sparse conditions

We analyze the performance of the least absolute shrinkage and selection operator (Lasso) for the linear model when the number of regressors N grows larger keeping the true support size d finite, i.e., the ultra-sparse case. The result is based on a novel treatment of the non-rigorous replica method in statistical physics, which has been applied only to problem settings where N ,d and the number of observations M tend to infinity at the same rate. Our analysis makes it possible to assess the average performance of Lasso with Gaussian sensing matrices without assumptions on the scaling of N and M, the noise distribution, and the profile of the true signal. Under mild conditions on the noise distribution, the analysis also offers a lower bound on the sample complexity necessary for partial and perfect support recovery when M diverges as M = O(log N). The obtained bound for perfect support recovery is a generalization of that given in previous literature, which only considers the case of Gaussian noise and diverging d. Extensive numerical experiments strongly support our analysis.