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

Karahanoğlu, Nazım Burak and Erdoğan, Hakan (2010) A* orthogonal matching pursuit: best-first search for compressed sensing signal recovery. (Submitted)

WarningThere is a more recent version of this item available.

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


Compressed sensing is a recently developing area which is interested in reconstruction of sparse signals acquired in reduced dimensions. Acquiring the data with a small number of samples makes the reconstruction problem 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. Some methods, such as Basis Pursuit (BP) propose casting the problem as an $l_1$ minimization. Greedy pursuit algorithms, such as Orthogonal Matching Pursuit (OMP) and Subspace Pursuit (SP), perform a greedy search among the vectors in the basis with the goal of stagewise constrained minimization of the residual error. This manuscript proposes a new semi-greedy algorithm which employs a best-first search technique, the A* search. This approach searches for the solution on several paths of a search tree, where the paths are evaluated and extended according to some cost function, which should be carefully selected to compensate for paths with different lengths. Each path on the tree grows similar to the Orthogonal Matching Pursuit algorithm, hence this new approach is called A* Orthogonal Matching Pursuit (A*OMP). In this manuscript, A*OMP algorithm is introduced and three different cost functions are discussed. We show that novel dynamic auxiliary cost functions provide improved results as compared to a conventional choice. Finally, we provide reconstruction results on both synthetically generated data and real images which show that the proposed scheme outperforms well-known CS reconstruction methods, BP, SP and OMP.

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:14340
Deposited By:Nazım Burak Karahanoğlu
Deposited On:13 Sep 2010 15:03
Last Modified:22 Jun 2012 13:58

Available Versions of this Item

Repository Staff Only: item control page