Research & Software

Sparse Signal Recovery via A*OMP

Download AStarOMP (binary only, Windows XP/7 32-bit): AStarOMP_v1.1.zip.

Downlad MATLAB implementation: AStarOMP_MATLAB_v1.1.zip.

AStarOMP code (Windows):  AStarOMP_library_v1.1.zip.

AStarOMP documentation: html, pdf

Linux and Mac OS X versions: Thanks to Sarfraz Nawaz ( Sarfraz.Nawaz at cl.cam.ac.uk), AStarOMP library is now also available for Linux and Mac OS X!

A* Orthogonal Matching Pursuit (A*OMP) is a semi-greedy approach to solve the l₀ minimization problem for finding sparse representations. The method is based on applying best-first search in combination with the orthogonal matching pursuit aiming at selecting the best representation among the paths of the A* search tree.

Incorporation of a search tree should not mislead the reader: A*OMP does not exploit any structure (and especially tree-based structure) of nonzero coefficients of the target signal. In contrast to tree-based OMP and similar methods, the search tree in A*OMP does not represent any structured or model-based sparsity.  A*OMP search tree allows all configurations of nonzero coefficients, making A*OMP a general sparse signal recovery algorithm.

Details of the approach may be found in:

A* orthogonal matching pursuit: best-first search for compressed sensing signal recovery (Digital Signal Processing, 2012)

A comparison of termination criteria for A*OMP (EUSIPCO’2012)

Improving A⋆OMP: Theoretical and Empirical Analyses With a Novel Dynamic Cost Model

Here, you can download the Matlab implementation of A*OMP:  AStarOMP_MATLAB_v1.1.zip

C++ implementation is also available:AStarOMP_v1.1.zip. The package provides the binary, which can easily be configured via a config file, and I/O files. The input data can easily be exported from MATLAB, while output can also be easily imported to MATLAB. Examples of data creation via MATLAB is also provided in the package, together with sample test data and config file.

The code for AStarOMP is also available for download:  AStarOMP_library_v1.1.zip. Detailed documentation can be found at http://students.sabanciuniv.edu/~karahanoglu/AStarOMP/library/doc/html/. This software package has been written for general purpose, and it can be easily extended to solve search problems other than compressed sensing, by replacing the OMP-like functions that evaluate and expand the paths in the search tree. The detailed documentation addresses this issue. Please do not hesitate to contact me in case of any problems or suggestions.

Sparse Signal Recovery via FBP

Downlad MATLAB implementation: FBP.zip

Forward-backward pursuit is a two-stage iterative algorithm for sparse recovery. The idea is intuitive: The forward step enlarges the estimated support, while backward step shrinks it. The forward step size (i.e. the number of elements inserted into the support estimate) is larger than the backward step size (the number of elements removed from the support set), hence the support set is enlarged at each iteration.

FBP has a fundamental advantage over other two-stage thresholding algorithms such as Subspace Pursuit (SP) or Compressive Sampling Matching Pursuit (CoSaMP). Both CoSaMP and SP necessitate the number of nonzero elements, or at least an estimate of it, a priori since this number drives the number of selected indices at each iteration. However, FBP has no such requirement. The involved forward-backward strategy allows for removal of possibly incorrect indices in the backward step while  the support estimate is enlarged after each iteration of the forward and backward steps.

Details may be found in

Compressed sensing signal recovery via forward-backward pursuit (Digital Signal Processing, 2013)[arxiv:1210.5626]