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.