Accession Number:



Instance Optimal Decoding by Thresholding in Compressed Sensing

Descriptive Note:

Research rept.

Corporate Author:


Report Date:


Pagination or Media Count:



Compressed Sensing seeks to capture a discrete signal x included in RN 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 Rn 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 Rn into RN. 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 RN, then with high probability applying to y x gives a vector x delta-y such that x -xhat less than or equal to C0-sigmakxL2 for all k less than or equal to anlogN provided a is sufficiently small depending on the probability of failure. Here sigma-kxL2 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-kxL2 is replaced by sigma-kxL2 eL2 .

Subject Categories:

  • Numerical Mathematics
  • Computer Programming and Software
  • Miscellaneous Detection and Detectors

Distribution Statement: