Backtracking matching pursuit with supplement set of arbitrary size

The idea of backtracking has been incorporated into the matching pursuit algorithms in sparse recovery, for example, subspace pursuit (SP) and compressive sampling matching pursuit (CoSaMP), to improve the recovery performance. In each iteration, a supplement set of size K or 2K is added to the candidate set to re-evaluate their reliability and then discard the unreliable indices, where K is the sparsity level of the original sparse signal. Yet the optimal choice of the size of the supplement set is still unclear. This paper aims to provide comprehensive analysis on the optimal choice of the size. The optimality is twofold: performance guarantees and computational complexity. By two theorems,we provide theoretical guarantees for the supplement set of arbitrary size, and computational complexity needed for perfect recovery. Numerical simulations demonstrate that a moderate size, such as 0.25K, results in computational efficiency without loss of recovery quality.