Monday, May 04, 2015

Phase Transition of Joint-Sparse Recovery from Multiple Measurements Via Convex Optimization

On January 22, 2014, I wondered whether there was much progress in the phase transition for MMV type of problems as it had a direct bearing on our paper on Compressive Imaging Using a Multiply Scattering Medium: It turrned out, that  Jeff Blanchard, Michael Cermak, David Hanle and, Yirong Jing had laready provided an answer in Greedy Algorithms for Joint Sparse Recovery.

Today, there is a new attempt at map making: the axes are note the same so I need to figure out if they are telling the same story. I also note there is no reference to the two works I just mentioned. At the very least, I will add this figure to the Advanced Matrix Factorization Jungle Page in the MMV section.

Phase Transition of Joint-Sparse Recovery from Multiple Measurements Via Convex Optimization by Shih-Wei Hu, Gang-Xuan Lin, Sung-Hsien Hsieh, and Chun-Shien Lu
In sparse signal recovery of compressive sensing, the phase transition determines the edge, which separates successful recovery and failed recovery.  Moreover, the width of phase transition determines the vague region, where sparse recovery is achieved in a probabilistic manner. Earlier works on phase transition analysis in either single measurement vector (SMV) or multiple measurement vectors (MMVs) is too strict or ideal to be satisfied in real world. Recently, phase transition analysis based on conic geometry has been found to close the gap between theoretical analysis and practical recovery result for SMV. In this paper, we explore a rigorous analysis on phase transition of MMVs. Such an extension is not intuitive at all since we need to redefine the null space and descent cone, and evaluate the statistical dimension for ℓ2;1-norm. By presenting the necessary and sufficient condition of successful recovery from MMVs, we can have a boundary on the probability that the solution of a MMVs recovery problem by convex programming is successful or not. Our theoretical analysis is verified to accurately predict the practical phase transition diagram of MMVs.
Earlier from the same authors: A practical subspace multiple measurement vectors algorithm for cooperative spectrum sensing, Tsung-Hsun Chien ; Wei-Jie Liang ; Chun-Shien Lu
Join the CompressiveSensing subreddit or the Google+ Community 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.

No comments: