Critical Behavior and Universality Classes for an Algorithmic Phase Transition in Sparse Reconstruction.

Recovery of an N-dimensional, K-sparse solution x from an M-dimensional vector of measurements y for multivariate linear regression can be accomplished by minimizing a suitably penalized least-mean-square cost | | y - H x | | 2 2 + λ V (x) . Here H is a known matrix and V (x) is an algorithm-dependent sparsity-inducing penalty. For 'random' H , in the limit λ → 0 and M , N , K → ∞ , keeping ρ = K / N and α = M / N fixed, exact recovery is possible for α past a critical value α c = α (ρ) . Assuming x has iid entries, the critical curve exhibits some universality, in that its shape does not depend on the distribution of x . However, the algorithmic phase transition occurring at α = α c and associated universality classes remain ill-understood from a statistical physics perspective, i.e. in terms of scaling exponents near the critical curve. In this article, we analyze the mean-field equations for two algorithms, Basis Pursuit ( V (x) = | | x | | 1 ) and Elastic Net ( V (x) = | | x | | 1 + g 2 | | x | | 2 2 ) and show that they belong to different universality classes in the sense of scaling exponents, with mean squared error (MSE) of the recovered vector scaling as λ 4 3 and λ respectively, for small λ on the critical line. In the presence of additive noise, we find that, when α > α c , MSE is minimized at a non-zero value for λ , whereas at α = α c , MSE always increases with λ . [ABSTRACT FROM AUTHOR]