Forward-backward search for compressed sensing signal recovery

Abstract

Reconstruction of sparse signals from reduced dimensions requires the solution of an l0 norm minimization, which is unpractical. A number of algorithms have appeared in literature, including ℓ1 minimization, greedy pursuit algorithms, Bayesian methods and nonconvex optimization. This manuscript introduces a greedy approach, called the Forward-Backward Pursuit (FBP), which iteratively enlarges the support by consecutive forward and backward steps. At each iteration, the forward step first expands the support, while the following backward step prunes it. The number of atoms selected by the forward step is selected higher than the number of removals, hence the support is expanded at the end of each iteration. The recovery performance of the proposed method is demonstrated via simulations including different nonzero coefficient distributions in noisy and noise-free scenarios.