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

Abstract

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.

Available Versions of this Item

• A* orthogonal matching pursuit: best-first search for compressed sensing signal recovery. (deposited 13 Sep 2010 15:03) [Currently Displayed]
  • A* orthogonal matching pursuit: best-first search for compressed sensing signal recovery. (deposited 22 Jun 2012 13:58)