Abstract
This paper considers the problem of recovering a one or twodimensional discrete signal which is approximately sparse in its gradient from an incomplete subset of its Fourier coefficients which have been corrupted with noise. We prove that in order to obtain a reconstruction which is robust to noise and stable to inexact gradient sparsity of order $s$ with high probability, it suffices to draw ${\cal O}$ $\!{(s {\rm log} N)}$ of the available Fourier coefficients uniformly at random. However, we also show that if one draws ${\cal O}$ ${\!(s {\rm log} N)}$ samples in accordance with a particular distribution which concentrates on the low Fourier frequencies, then the stability bounds which can be guaranteed are optimal up to log factors. Finally, we prove that in the onedimensional case where the underlying signal is gradient sparse and its sparsity pattern satisfies a minimum separation condition, to guarantee exact recovery with high probability, for some $M<N$, it suffices to draw ${\cal O}$ ${\!(s{\rm log} M {\rm log} s)}$ samples uniformly at random from the Fourier coefficients whose frequencies are no greater than $M$.
Original language  English 

Pages (fromto)  682720 
Number of pages  39 
Journal  SIAM Journal on Imaging Sciences 
Volume  8 
Issue number  1 
Early online date  26 Mar 2015 
DOIs  
Publication status  Published  2015 
Fingerprint
Dive into the research topics of 'On the role of total variation in compressed sensing'. Together they form a unique fingerprint.Profiles

Clarice Poon
Person: Research & Teaching