289	RWTH Publication No: 47089        2008        IGPM289.pdf
TITLE	Instance Optimal Decoding by Thresholding in Compressed Sensing
AUTHORS	Albert Cohen, Wolfgang Dahmen, Ronald DeVore
ABSTRACT	Compressed Sensing seeks to capture a discrete signal x ∈ I RN with a small number n of linear measurements. The information captured about x from such measurements is given by the vector y = Φx ∈ I R n where Φ is an n × 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 decorders 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‾ := ∆(y) such that ||x−x‾ || ≤ C0σk(x)l2 for all k ≤ an/ log N provided a is sufficiently small (depending on the probability of failure). Here σ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 = Φx + e where e is some noise vector. In this case σk(x)l2 is replaced by σk (x)l2 + ||e||l2 .
KEYWORDS	Compressed sensing, best k-term approximation, instance optimal decoders, thresholding, noisy measurements, random matrices.
PUBLICATION	8th International Conference on Harmonic Analysis and Partial Differential Equations, June 16 - 20, 2008, El Escorial, Madrid, Spain / Patricio Cifuentes ... ed. Contemporary mathematics 505, 28 S. (2010)