A* orthogonal matching pursuit: best-first search for compressed sensing signal recovery

Karahanoğlu, Nazım Burak and Erdoğan, Hakan (2012) A* orthogonal matching pursuit: best-first search for compressed sensing signal recovery. Digital Signal Processing, 22 (4). pp. 555-568. ISSN 1051-2004

This is the latest version of this item.

[img]PDF - Registered users only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1016/j.dsp.2012.03.003


Compressed sensing is a developing field aiming at the reconstruction of sparse signals acquired in reduced dimensions, which make the recovery process under-determined. The required solution is the one with minimum l(0) norm due to sparsity, however it is not practical to solve the l(0) minimization problem. Commonly used techniques include l(1) minimization, such as Basis Pursuit (BP) and greedy pursuit algorithms such as Orthogonal Matching Pursuit (OMP) and Subspace Pursuit (SP). This manuscript proposes a novel semi-greedy recovery approach, namely A* Orthogonal Matching Pursuit (A*OMP). A*OMP performs A* search to look 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 a cost function, which should compensate for different path lengths. For this purpose, three different auxiliary structures are defined, including novel dynamic ones. A*OMP also incorporates pruning techniques which enable practical applications of the algorithm. Moreover, the adjustable search parameters provide means for a complexity-accuracy trade-off. We demonstrate the reconstruction ability of the proposed scheme on both synthetically generated data and images using Gaussian and Bernoulli observation matrices, where A*OMP yields less reconstruction error and higher exact recovery frequency than BP, OMP and SP. Results also indicate that novel dynamic cost functions provide improved results as compared to a conventional choice.

Item Type:Article
Uncontrolled Keywords:compressed sensing, best-first search, A* search, orthogonal matching pursuit, sparse representations, sparse signal reconstruction, auxiliary functions for A* search
Subjects:T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK5101-6720 Telecommunication
T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics
ID Code:19126
Deposited By:Nazım Burak Karahanoğlu
Deposited On:22 Jun 2012 13:58
Last Modified:31 Jul 2019 11:04

Available Versions of this Item

Repository Staff Only: item control page