Sequential Sparse Matching Pursuit

We propose a new algorithm, called Sequential Sparse Matching Pursuit (SSMP), for solving sparse recovery problems. The algorithm provably recovers a k-sparse approximation to an arbitrary n-dimensional signal vector x from only O(k log(n/k)) linear measurements of x. The recovery process takes time that is only near-linear in n. Preliminary experiments indicate that the algorithm works well on synthetic and image data, with the recovery quality often outperforming that of more complex algorithms, such as l(1) minimization.