Thresholded Basis Pursuit: An LP Algorithm for Achieving Optimal Support
  Recovery for Sparse and Approximately Sparse Signals from Noisy Random
  Measurements
  In this paper we present a linear programming solution for sign pattern
recovery of a sparse signal from noisy random projections of the signal. We
consider two types of noise models, input noise, where noise enters before the
random projection; and output noise, where noise enters after the random
projection. Sign pattern recovery involves the estimation of sign pattern of a
sparse signal. Our idea is to pretend that no noise exists and solve the
noiseless $\ell_1$ problem, namely, $\min \|\beta\|_1 ~ s.t. ~ y=G \beta$ and
quantizing the resulting solution. We show that the quantized solution
perfectly reconstructs the sign pattern of a sufficiently sparse signal.
Specifically, we show that the sign pattern of an arbitrary k-sparse,
n-dimensional signal $x$ can be recovered with $SNR=\Omega(\log n)$ and
measurements scaling as $m= \Omega(k \log{n/k})$ for all sparsity levels $k$
satisfying $0< k \leq \alpha n$, where $\alpha$ is a sufficiently small
positive constant. Surprisingly, this bound matches the optimal
\emph{Max-Likelihood} performance bounds in terms of $SNR$, required number of
measurements, and admissible sparsity level in an order-wise sense. In contrast
to our results, previous results based on LASSO and Max-Correlation techniques
either assume significantly larger $SNR$, sublinear sparsity levels or
restrictive assumptions on signal sets. Our proof technique is based on noisy
perturbation of the noiseless $\ell_1$ problem, in that, we estimate the
maximum admissible noise level before sign pattern recovery fails.
