Instance Optimal Decoding by Thresholding in Compressed Sensing
Abstract
Compressed Sensing seeks to capture a discrete signal x included in R(N_ with a small number n of linear measurements. The information captured about x from such measurements is given by the vector y = Phi-x included in R(n) where Phi is an n x N matrix. The best matrices, from the viewpoint of capturing sparse or compressible signals are generated by random processes, e.g. their entries are given by i.i.d. Bernoulli or Gaussian random variables. The information y holds about x is extracted by a decoder mapping R(n) into R(N). Typical decoders are based on L1-minimization and greedy pursuit. The present paper studies the performance of decoders based on thresholding. For quite general random families of matrices , decoders are constructed which are instance-optimal in probability by which we mean the following. If x is any vector in R(N), then with high probability applying to y = x gives a vector x := delta-(y) such that ||x -x(hat)|| less than or equal to C(0)-sigma(k)(x)L2 for all k less than or equal to an/logN provided a is sufficiently small (depending on the probability of failure). Here sigma-k(x)L2 is the error that results when x is approximated by the k sparse vector which equals x in its k largest coordinates and is otherwise zero. It is also shown that results of this type continue to hold even if the measurement vector y is corrupted by additive noise: y = Phi-x + e where e is some noise vector. In this case sigma-k(x)L2 is replaced by sigma-k(x)L2 + ||e||L2 .
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 2008
- Accession Number
- ADA528526
Entities
People
- Albert Cohen
- Ronald DeVore
- Wolfgang Dahmen