Coherence-based near-oracle performance guarantees for sparse estimation under Gaussian noise

We consider the problem of estimating a deterministic sparse vector x₀ from underdetermined measurements Ax₀ + w, where w represents white Gaussian noise and A is a given deterministic dictionary. We analyze the performance of three sparse estimation algorithms: basis pursuit denoising, orthogonal matching pursuit, and thresholding. These approaches are shown to achieve near-oracle performance with high probability, assuming that x₀ is sufficiently sparse. Our results are non-asymptotic and are based only on the coherence of A, so that they are applicable to arbitrary dictionaries.