Overcoming The Limitations of Phase Transition by Higher Order Analysis of Regularization Techniques

All the map makers know that computing a phase transition for a zero noise limit is a first step, the second step, especially when it comes to building some hardware, involves putting some noise in it and see how the new phase transition moves. Today, we have a mathematical approach to that, woohoo !

Overcoming The Limitations of Phase Transition by Higher Order Analysis of Regularization Techniques  by Haolei Weng, Arian Maleki, Le Zheng

We study the problem of estimating $\beta \in \mathbb{R}^p$ from its noisy linear observations $y= X\beta+ w$, where $w \sim N(0, \sigma_w^2 I_{n\times n})$, under the following high-dimensional asymptotic regime: given a fixed number $\delta$, $p \rightarrow \infty$, while $n/p \rightarrow \delta$. We consider the popular class of $\ell_q$-regularized least squares (LQLS) estimators, a.k.a. bridge, given by the optimization problem: \begin{equation*} \hat{\beta} (\lambda, q ) \in \arg\min_\beta \frac{1}{2} \|y-X\beta\|_2^2+ \lambda \|\beta\|_q^q, \end{equation*} and characterize the almost sure limit of $\frac{1}{p} \|\hat{\beta} (\lambda, q )- \beta\|_2^2$. The expression we derive for this limit does not have explicit forms and hence are not useful in comparing different algorithms, or providing information in evaluating the effect of $\delta$ or sparsity level of $\beta$. To simplify the expressions, researchers have considered the ideal "no-noise" regime and have characterized the values of $\delta$ for which the almost sure limit is zero. This is known as the phase transition analysis.
In this paper, we first perform the phase transition analysis of LQLS. Our results reveal some of the limitations and misleading features of the phase transition analysis. To overcome these limitations, we propose the study of these algorithms under the low noise regime. Our new analysis framework not only sheds light on the results of the phase transition analysis, but also makes an accurate comparison of different regularizers possible.

Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.