Sparse estimation from noisy observations of an overdetermined linear system

This note studies a method for the estimation of a finite number of unknown parameters from linear equations, which are perturbed by Gaussian noise. In the case the unknown parameters have only few nonzero entries, the proposed estimator performs more efficiently than a traditional approach. The method consists of three steps: (1) a classical Least Squares Estimate (LSE); (2) the support is recovered through a Linear Programming (LP) optimization problem which can be computed using a soft-thresholding step; (3) a de-biasing step using a LSE on the estimated support set. The main contribution of this note is a formal derivation of an associated ORACLE property of the final estimate. That is, with probability 1, the estimate equals the LSE based on the support of the true parameters when the number of observations goes to infinity.