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.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), sufﬁcient conditions for all ﬁve 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 sufﬁcient 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
- 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:
Please kindly let me know by which paper I should remove the current "None so far" item.
- None so far.