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

摘要

We consider the problem of estimating a deterministic sparse vector $ {bf x}_{0}$ from underdetermined measurements $ {bf A} {bf x} _{0} + {bf w}$, where $ {bf w}$ represents white Gaussian noise and $ {bf 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 $ell _{2}$ distance between the estimate and the true value of $ {bf 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 $ {bf x}_{0}$. Our results are non-asymptotic and are based only on the coherence of $ {bf A}$, so that they are applicable to arbitrary dictionaries. This provides insight on the advantages and drawbacks of $ell _{1}$ relaxation techniques such as BPDN and the Dantzig selector, as opposed to greedy approaches such as OMP and thresholding.