Phase transition and higher order analysis of Lq regularization under dependence.

ABSTRACT

We study the problem of estimating a [Formula see text]-sparse signal [Formula see text] from a set of noisy observations [Formula see text] under the model [Formula see text], where [Formula see text] is the measurement matrix the row of which is drawn from distribution [Formula see text]. We consider the class of [Formula see text]-regularized least squares (LQLS) given by the formulation [Formula see text], where [Formula see text]  [Formula see text] denotes the [Formula see text]-norm. In the setting [Formula see text] with fixed [Formula see text] and [Formula see text], we derive the asymptotic risk of [Formula see text] for arbitrary covariance matrix [Formula see text] that generalizes the existing results for standard Gaussian design, i.e. [Formula see text]. The results were derived from the non-rigorous replica method. We perform a higher-order analysis for LQLS in the small-error regime in which the first dominant term can be used to determine the phase transition behavior of LQLS. Our results show that the first dominant term does not depend on the covariance structure of [Formula see text] in the cases [Formula see text] and [Formula see text] which indicates that the correlations among predictors only affect the phase transition curve in the case [Formula see text] a.k.a. LASSO. To study the influence of the covariance structure of [Formula see text] on the performance of LQLS in the cases [Formula see text] and [Formula see text], we derive the explicit formulas for the second dominant term in the expansion of the asymptotic risk in terms of small error. Extensive computational experiments confirm that our analytical predictions are consistent with numerical results.