A* Orthogonal Matching Pursuit papers and code implementation

I just received this email from Nazim Burak Karahanoglu:

....

We have recently launched the AStarOMP software for compressed sensing signal recovery via A* Orthogonal Matching Pursuit (A*OMP) algorithm. We will be glad if you could link to our software.The software, code, documentation and a brief introduction to A*OMP are available at

http://myweb.sabanciuniv.edu/karahanoglu/research/.

A suitable description for the link would be "AStarOMP: Compressed Sensing via A* search".

A*OMP was first presented in ICASSP 2011. It is a general sparse recovery algorithm employing A* search on a hypothesis tree where the paths are extended and evaluated in a way similar to OMP.

To avoid some possible misunderstanding, we would like to note that the tree search concept in A*OMP is completely general to all sparse signals. A*OMP is an algorithm that aims to find a closer result to the true L0 solution (regardless of the RIP condition), thus the objective is to improve reconstruction quality not to decrease computational complexity to find a greedy solution (such as in list decoding). Furthermore, A*OMP is neither specific for tree-sparse signals nor does it make use of a tree-structured over-complete basis (such as in the tree-based OMP algorithm). The algorithm is not specific for structured sparse signals as well. The algorithm is simply aiming to (approximately) solve the NP-complete L0 problem in an efficient manner. There are parameters that can be adjusted for reduced complexity or increased accuracy as desired. Experimental results show that A*OMP improves general recovery as compared to convex relaxation and greedy pursuits (for publications, see http://myweb.sabanciuniv.edu/karahanoglu/publications/).

The new software is capable of performing a fast A*OMP reconstruction via an efficient implementation of the search tree. Moreover, the code can also be easily expanded to perform A* search in any other subset search problem just by binding it to the new problem class that covers evaluation and growth of tree branches with respect to the new problem.

We would be glad to hear any comments and suggestions from you. Please also feel free to report any bugs or problems with the software.

Best regards,

Nazim Burak Karahanoglu and Hakan Erdogan

Here are the attendant publications:

A* Orthogonal Matching Pursuit: Best-First Search for Compressed Sensing Signal Recovery by Nazim Burak Karahanoglu and Hakan Erdogan. The abstract reads:

Compressed sensing aims at reconstruction of sparse signals following acquisition in reduced dimensions, which makes the recovery process under-determined. Due to sparsity, required solution becomes the one with minimum $\ell_0$ norm, which is untractable to solve for. Commonly used reconstruction techniques include $\ell_1$ norm minimization and greedy algorithms. This manuscript proposes a novel semi-greedy approach, namely A* Orthogonal Matching Pursuit (A*OMP), which performs A* search for the sparsest solution on a tree whose paths grow similar to the Orthogonal Matching Pursuit (OMP) algorithm. Paths on the tree are evaluated according to an auxiliary cost function, which should compensate for different path lengths. For this purpose, we suggest three different structures. We show that novel dynamic cost functions provide improved results as compared to a conventional choice. Finally, we provide reconstruction results on both synthetically generated data and images showing that A*OMP outperforms well-known CS reconstruction methods, Basis Pursuit (BP), OMP and Subspace Pursuit (SP).

COMPRESSED SENSING SIGNAL RECOVERY VIA A* ORTHOGONAL MATCHING PURSUIT

by Nazim Burak Karahanoglu and Hakan Erdogan. The abstract reads:

Reconstruction of sparse signals acquired in reduced dimensions requires the solution with minimum l0 norm. As solving the l0 minimization directly is unpractical, a number of algorithms have appeared for finding an indirect solution. A semi-greedy approach, A*Orthogonal Matching Pursuit (A*OMP), is proposed in [1] where the solution is searched on several paths of a search tree. Paths of the tree are evaluated and extended according to some cost function, for which novel dynamic auxiliary cost functions are suggested. This paper describes the A*OMP algorithm and the proposed cost functions briefly. The novel dynamic auxiliary cost functions are shown to provide improved results as compared to a conventional choice. Reconstruction performance is illustrated on both synthetically generated data and real images, which show that the proposed scheme outperforms well-known CS reconstruction methods.

A Comparison of Termination Criteria for A*OMP by Nazim Burak Karahanoglu and Hakan Erdogan. The abstract reads:

Heuristic search has recently been utilized for compressed sensing (CS) signal recovery problem by A* Orthogonal Matching Pursuit (A*OMP) algorithm.A*OMP employs A* search on a tree with an OMP-based evaluation of the tree branches, where the search is terminated when the desired path length is achieved. Here, we utilize a different termination criterion, which stops the search when ℓ2 norm of the residue is small enough. We show this residue-based termination is superior to the other one in terms of both reconstruction accuracy and computation times. We demonstrate A*OMP in a noisy scenario, stating its better reconstruction performance than mainstream CS algorithms.

Thaniks Nazim and Hakan.

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.