Arian Maleki, Columbia University
Phase Transitions in Compressed Sensing

Extensive research performed in the last decade has proved that “structured” signals can be recovered “accurately” from their ill-posed or undersampled set of linear measurements. This area of research, a.k.a. compressed sensing, has led to major advances in the technology of sampling and imaging devices, such as magnetic resonance imaging (MRI). One of the basic problems in this area is the recovery of a ‎$‎p‎$‎-dimensional ‎$‎k‎$‎-sparse vector ‎$‎x‎$‎ from ‎$‎n<p‎$‎ response variables ‎$‎y=Ax‎$‎, where ‎$‎w‎$‎ represents the errors (noise).  


In this talk, we consider a class of algorithms for recovering ‎$‎x‎$‎ from ‎$‎y‎$‎, known as ‎$‎q‎$‎-norm regularized least squares (QNLS), and study their performance under the asymptotic setting ‎$‎k/n‎ \rightarrow‎\epsilon‎‎$‎ and ‎$‎n/p\rightarrow\delta‎$‎. In this asymptotic regime, one of the fundamental quantities is the phase transition diagram. Phase transition diagrams characterize the minimum value of $\delta‎$‎ (for a given $‎\epsilon‎‎$‎) for which ‎$‎x‎$‎ can be exactly recovered when the response variables are noise-free. We will show that: (i) For ‎$‎q<1‎$‎ the phase transition occurs at ‎$‎\delta=‎\epsilon‎‎$‎, (ii) For ‎$‎q>1‎$‎ the phase transition occurs at ‎$‎\delta=1‎$‎, and (iii) For ‎$‎q=1‎$‎ the phase transition happens at Donoho-Tanner phase transition curve. We then explore a limitation of phase transition diagrams and propose a solution by extending our analysis to the noisy response variables.

Date & Time: 
Wednesday, January 4, 2014, 15:00
Room 221, Dept. Math. Sci., Sharif University of Technology