  Recovery of an $N$-dimensional, $K$-sparse solution $\mathbf{x}$ from an
$M$-dimensional vector of measurements $\mathbf{y}$ for multivariate linear
regression can be accomplished by minimizing a suitably penalized
least-mean-square cost $||\mathbf{y}-\mathbf{H} \mathbf{x}||_2^2+\lambda
V(\mathbf{x})$. Here $\mathbf{H}$ is a known matrix and $V(\mathbf{x})$ is an
algorithm-dependent sparsity-inducing penalty. For `random' $\mathbf{H}$, in
the limit $\lambda \rightarrow 0$ and $M,N,K\rightarrow \infty$, keeping
$\rho=K/N$ and $\alpha=M/N$ fixed, exact recovery is possible for $\alpha$ past
a critical value $\alpha_c = \alpha(\rho)$. Assuming $\mathbf{x}$ has iid
entries, the critical curve exhibits some universality, in that its shape does
not depend on the distribution of $\mathbf{x}$. However, the algorithmic phase
transition occurring at $\alpha=\alpha_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(\mathbf{x})=||\mathbf{x}||_{1} $) and Elastic Net ($V(\mathbf{x})=
||\mathbf{x}||_{1} + \tfrac{g}{2} ||\mathbf{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
$\lambda^\frac{4}{3}$ and $\lambda$ respectively, for small $\lambda$ on the
critical line. In the presence of additive noise, we find that, when
$\alpha>\alpha_c$, MSE is minimized at a non-zero value for $\lambda$, whereas
at $\alpha=\alpha_c$, MSE always increases with $\lambda$.
