Sharp Phase Transition for Joint Sparse Recovery (MMV)

Jeff Blanchard just sent me the following

Dear Igor, 

I saw in your January 22 post that you posed the question, "Isn't it time, we devise a universal phase transition diagram for MMV computations?" If you haven't seen it, I think you might be interested in a paper I wrote with three of my students,

Jeffrey D. Blanchard, Michael Cermak, David Hanle, Yirong Jing. "Greedy algorithms for Joint Sparse Recovery", IEEE Trans. Sig. Proc., in press, 2014.

While it does not resolve your question, we present weak, empirical recovery phase transitions for the MMV setting for simultaneous recovery variants of NIHT, HTP, and CoSaMP in addition to RIP-based, uniform recovery guarantees.

It should be online at TSP in the next week or so as the preprint version. In the meantime, you can get the preprint from my webpage.

www.math.grinnell.edu/~blanchaj/Research/Research.html

All the best,

Jeff

Thanks Jeff ! Here is the paper: Greedy Algorithms for Joint Sparse Recovery by Jeff Blanchard, Michael Cermak, David Hanle, and , Yirong Jing

Abstract—Five known greedy algorithms designed for the single measurement vector setting in compressed sensing and sparse approximation are extended to the multiple measurement vector scenario: Iterative Hard Thresholding (IHT), Normalized IHT (NIHT), Hard Thresholding Pursuit (HTP), Normalized HTP (NHTP), and Compressive Sampling Matching Pursuit (CoSaMP). Using the asymmetric restricted isometry property (ARIP), sufficient conditions for all five algorithms establish bounds on the discrepancy between the algorithms’ output and the optimal row-sparse representation. When the initial multiple measurement vectors are jointly sparse, ARIP-based guarantees for exact recovery are also established. The algorithms are then compared via the recovery phase transition framework. The strong phase transitions describing the family of Gaussian matrices which satisfy the sufficient conditions are obtained via known bounds on the ARIP constants. The algorithms’ empirical weak phase transitions are compared for various numbers of multiple measurement vectors. Finally, the performance of the algorithms is compared against a known rank aware greedy algorithm, Rank Aware Simultaneous Orthogonal Matching Pursuit + MUSIC. Simultaneous recovery variants of NIHT, NHTP, and CoSaMP all outperform the rank-aware algorithm.

One figure, in particular, triggered my interest: figure 3c

Figure 3c of Greedy Algorithms for Joint Sparse Recovery

because it has the same shape as the one we found experimentally in the lab with a random medium used as measurement matrix.

Figure 4 from this preprint

Those are not exact match because Jeff  et al's paper: 

• produces phase transition for l=2, 5 and 10 while ours is for l = 3 (it is between their l=2 and l=5)
• focuses on noiseless phase transitions (lab experiments are not noiseless).

it is noteworthy that if the phase transition showed l*m/n on the x-axis , it would show exact recovery for x (l*m/n)  less than 1 and this for l =2 or 3. We noted before that there is something interesting at l = 2 and 3 in a computational-only study featuring Imaging strong localized scatterers with sparsity promoting optimization.

As an aside, maybe the Advanced Matrix Factorization Jungle page ought to have a place for each of the factorization and papers covering their phase transitions. In fact, I just added these templates for each factorization:

Phase Transitions:

• None so far.

Implementations:

Please kindly let me know by which paper I should remove the current "None so far" item.

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.