Sparsity adaptive matching pursuit algorithm for practical compressed sensing

TLDR

SAMP extends greedy compressed‑sensing reconstruction by operating without prior sparsity knowledge, generalizing OMP and SP as special cases. The paper introduces SAMP, an iterative greedy algorithm designed for practical compressed sensing. SAMP alternates between estimating sparsity and support, following an EM‑like framework. Without requiring sparsity information, SAMP delivers theoretical guarantees comparable to optimization‑based methods and, in simulations, outperforms many iterative algorithms—especially for compressible signals—while elucidating the trade‑off between computational complexity and reconstruction performance.

Abstract

This paper presents a novel iterative greedy reconstruction algorithm for practical compressed sensing (CS), called the sparsity adaptive matching pursuit (SAMP). Compared with other state-of-the-art greedy algorithms, the most innovative feature of the SAMP is its capability of signal reconstruction without prior information of the sparsity. This makes it a promising candidate for many practical applications when the number of non-zero (significant) coefficients of a signal is not available. The proposed algorithm adopts a similar flavor of the EM algorithm, which alternatively estimates the sparsity and the true support set of the target signals. In fact, SAMP provides a generalized greedy reconstruction framework in which the orthogonal matching pursuit and the subspace pursuit can be viewed as its special cases. Such a connection also gives us an intuitive justification of trade-offs between computational complexity and reconstruction performance. While the SAMP offers a comparably theoretical guarantees as the best optimization-based approach, simulation results show that it outperforms many existing iterative algorithms, especially for compressible signals.