Publication Detail

Sequential Sparse Matching Pursuit

Radu Berinde, Piotr Indyk
8 pp.

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 l1 minimization.

type: Technical reports

This publication is not currently available from MIT Sea Grant. Please try again later or contact MIT Sea Grant for more information.

Parent Project

Project No.: 2008-ESRDC-01-LEV
Title: Electric Ship Research and Development Consortium (ESRDC)