Randomized iterative hard thresholding for sparse approximations

Typical greedy algorithms for sparse reconstruction problems, such as orthogonal matching pursuit and iterative thresholding, seek strictly sparse solutions. Recent work in the literature suggests that given a priori knowledge of the distribution of the sparse signal coefficients, better results can be obtained by a weighted averaging of several sparse solutions. Such a combination of solutions, while not strictly sparse, approximates an MMSE estimator and can outperform strictly sparse solvers in terms of l-2 reconstruction error. We introduce a novel method for obtaining such an approximate MMSE estimator by replacing the deterministic thresholding operator of Iterative Hard Thresholding with a randomized version. We demonstrate the improvement in performance experimentally for both synthetic 1D signals and real images.