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

We consider the problem of estimating a deterministic sparse vector x₀ from underdetermined measurements A x₀ + 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₂ distance between the estimate and the true value of x₀. 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₀. 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₁ relaxation techniques such as BPDN and the Dantzig selector, as opposed to greedy approaches such as OMP and thresholding.