  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 (BPDN), orthogonal
matching pursuit (OMP), and thresholding. These algorithms 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. Differences in the
precise conditions required for the performance guarantees of each algorithm
are manifested in the observed performance at high and low signal-to-noise
ratios. This provides insight on the advantages and drawbacks of convex
relaxation techniques such as BPDN as opposed to greedy approaches such as OMP
and thresholding.
