Thresholded Basis Pursuit: LP Algorithm for Order-Wise Optimal Support Recovery for Sparse and Approximately Sparse Signals From Noisy Random Measurements

Venkatesh Saligrama, Manqi ZhaoIEEE Trans. Information Theory 2011 · OpenReview

Abstract

In this paper, we present a linear programming solution for sign pattern recovery of a sparse signal, x, 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 ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> problem, namely, min ||β|| <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> s.t. y - Gβ 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 - Ω(log n) and measurements scaling as m = Ώ,(log n /k) for all sparsity levels k satisfying 0 <; k ≤ an, where a is a sufficiently small positive constant. Surprisingly, this bound matches the optimal Max-Likelihood performance bounds in terms of SNR, re quired 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, sub-linear sparsity levels or restrictive assumptions on signal sets. Our proof technique is based on noisy perturbation of the noiseless ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> problem, in that, we estimate the maximum admissible noise level before sign pattern recovery fails.
BibTeX
@article{saligrama2011thresholded,
  author = {Venkatesh Saligrama and Manqi Zhao},
  title = {{Thresholded Basis Pursuit: LP Algorithm for Order-Wise Optimal Support Recovery for Sparse and Approximately Sparse Signals From Noisy Random Measurements}},
  journal = {IEEE Trans. Information Theory},
  year = {2011},
  url = {https://openreview.net/forum?id=kkRGa-RvnAF},
}

Loading related content...

Figure