Thresholded Basis Pursuit: An LP Algorithm for Achieving Optimal Support Recovery for Sparse and Approximately Sparse Signals from Noisy Random Measurements

Details Thresholded Basis Pursuit: An LP Algorithm for Achieving Optimal Support Recovery for Sparse and Approximately Sparse Signals from Noisy Random Measurements Thresholded Basis Pursuit: An LP Algorithm for Achieving Optimal Support Recovery for Sparse and Approximately Sparse Signals from Noisy Random Measurements

2008-09-29

arxiv.org/abs/0809.4883v3

Computer Science

Information Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Thresholded Basis Pursuit: An LP Algorithm for Achieving Optimal Support Recovery for Sparse and Approximately Sparse Signals from Noisy Random Measurements does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Thresholded Basis Pursuit: An LP Algorithm for Achieving Optimal Support Recovery for Sparse and Approximately Sparse Signals from Noisy Random Measurements, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Thresholded Basis Pursuit: An LP Algorithm for Achieving Optimal Support Recovery for Sparse and Approximately Sparse Signals from Noisy Random Measurements will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-48752