  We propose a novel greedy algorithm for the support recovery of 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 is optimal in the sense of detecting one of
the remaining support indices, provided that all the detected indices in the
previous iterations are correct. Despite its optimality, it requires an
expensive complexity for computing the maximization metric (i.e., a posteriori
probability of each remaining support) due to the marginalization of
high-dimensional sparse vector. We address this problem by presenting a good
proxy (named B-MAP proxy) on the maximization metric which is accurate enough
to find the maximum index, rather than an exact probability, Moreover, it is
easily evaluated only using vector correlations as in orthogonal matching
pursuit (OMP), but the use completely different proxy matrices for
maximization. We demonstrate that the proposed B-MAP detection provides a
significant gain compared with the existing methods as OMP and MAP-OMP, having
the same complexity. Subsequently, we construct the advanced greedy algorithms,
based on B-MAP proxy, by leveraging the idea of compressive sampling matching
pursuit (CoSaMP) and subspace pursuit (SP). Via simulations, we show that the
proposed method outperforms also OMP and MAP-OMP under the frameworks of the
advanced greedy algorithms.
