Coherence-Based Performance Guarantees for Estimating a Sparse Vector Under Random Noise

We consider the problem of estimating a deterministic sparse vector x 0 from underdetermined measurements A x 0 + w, where w represents white Gaussian noise and A is a given deterministic dictionary. We provide theoretical performance guarantees for three sparse estimation algorithms: basis pursuit denoising (BPDN), orthogonal matching pursuit (OMP), and thresholding. The performance of these techniques is quantified as the l 2 distance between the estimate and the true value of x 0 . We demonstrate that, with high probability, the analyzed algorithms come close to the behavior of the oracle estimator, which knows the locations of the nonzero elements in x 0 . Our results are non-asymptotic and are based only on the coherence of A, so that they are applicable to arbitrary dictionaries. This provides insight on the advantages and drawbacks of l 1 relaxation techniques such as BPDN and the Dantzig selector, as opposed to greedy approaches such as OMP and thresholding.