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.