We propose a novel greedy algorithm to recover a sparse signal from a small number of noisy measurements. In the proposed method, a new support index is identified for each iteration, based on bit-wise maximum a posteriori (B-MAP) detection. This approach is optimal in the sense of detecting one of the remaining support indices, provided that all the indices during the previous iterations are perfectly recovered. Unfortunately, the exact computation of B-MAP detection is not practical since it requires a heavy marginalization of a high-dimensional sparse vector to compute a posteriori probability of each remaining support. Our major contribution is to present a good proxy, named B-MAP proxy, on the a posteriori probability. The proposed proxy is easily evaluated only using vector correlations as in popular orthogonal matching pursuit (OMP) and accurate enough to represent a relative ordering on the probabilities. Via simulations, we demonstrate that the proposed greedy algorithm yields a higher recovery accuracy than the existing benchmark methods as OMP and MAP-OMP, having the same computational complexity.


Jeongmin Chae

Ajou University

Song-Nam Hong

Ajou University

Session Chair

Sundeep Rangan

New York University