The generic approach to beat the Donoho-Tanner phase transition delimiting the region beween no possible signal recovery and full signal recovery with sparsity seeking solvers, is to add an additional structure to the signal beyond sparsity. Block sparsity is one way to help these solvers, another is to design the right measurement matrix and another one is to expect the signal to be decomposable in a tree like structure. Much like block sparsity, tree based sparsity is an example of structured sparsity. This is the focus on today's solver:
A Fast Approximation Algorithm for Tree-Sparse Recovery by Chinmay Hegde, Piotr Indyk, Ludwig Schmidt
An implementation of Tree_approx can be found here.Sparse signals whose nonzeros obey a tree-like structure occur in a range of applications such as image modeling, genetic data analysis, and compressive sensing. An important problem encountered in recovering signals is that of optimal tree-projection, i.e., finding the closest tree-sparse signal for a given query signal. However, this problem can be computationally very demanding: for optimally projecting a length-n signal onto a tree with sparsity k, the best existing algorithms incur a high runtime of O(nk). This can often be impractical. We suggest an alternative approach to tree-sparse recovery. Our approach is based on a specific approximation algorithm for tree-projection and provably has a near-linear runtime of O(n log(kr)) and a memory cost of O(n), where r is the dynamic range of the signal. We leverage this approach in a fast recovery algorithm for tree-sparse compressive sensing that scales extremely well to high-dimensional datasets. Experimental results on several test cases demonstrate the validity of our approach.
In order to get a sense of how much improvment this brings, I went onto Jared Tanner's site featuring the Phase Transitions of the Regular Polytopes and Cone and used the numbers from figure 4 of the paper. The red dot features a 'normal' recovery below the L1 recovery phase transition line (CoSaMP, SPGL1), something that is expected when all we kow about the signal is that it is sparse. The blue dot represents the recovery of the signal above the L1 recovery phase transition line because the algorithm ( Tree_approx ) uses the additional information that the signal is tree based.
I'd love to see the phase transition for the full diagram.
I used n = 1024, k = 41 and from figure 4, full recovery was had with m/k = 5 for the L1 minimization solvers and m/k = 3 for the tree based algorithm. It should be noted that in the noiseless case, this is an Ok result as compared to the belief propagation/AMP solvers and specific measurement matrices. Most probably, as shown in figure 5, it seems to be pretty robust to shot noise.
Other relevant papers:
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:
Post a Comment