Randomized simultaneous orthogonal matching pursuit

In this paper, we develop randomized simultaneous orthogonal matching pursuit (RandSOMP) algorithm which computes an approximation of the Bayesian minimum mean-squared error (MMSE) estimate of an unknown rowsparse signal matrix. The approximation is based on greedy iterations, as in SOMP, and it elegantly incorporates the prior knowledge of the probability distribution of the signal and noise matrices into the estimation process. Unlike the exact MMSE estimator which is computationally intractable to solve, the Bayesian greedy pursuit approach offers a computationally feasible way to approximate the MMSE estimate. Our simulations illustrate that the proposed RandSOMP algorithm outperforms SOMP both in terms of mean-squared error and probability of exact support recovery. The benefits of RandSOMP are further illustrated in direction-of-arrival estimation with sensor arrays and image denoising.