Optimal Forward-Backward Pursuit for the Sparse Signal Recovery Problem

Forward-backward pursuit (FBP) is an iterative two stage thresholding method (TST) for sparse signal recovery. Due to the selection of more indices during the forward step than the ones pruned by the backward step, FBP iteratively enlarges the support estimate. With this structure, FBP does not necessitate the sparsity level to be known a priori in contrast to other TST algorithms such as subspace pursuit (SP) or compressive sampling matching pursuit. In this work, we address optimal selection of forward and backward step sizes for FBP. We analyse the empirical recovery performance of FBP with different step sizes via phase transitions. Moreover, we compare phase transitions of FBP with those of basis pursuit, SP and orthogonal matching pursuit.