On the role of total variation in compressed sensing

Research output: Contribution to journalArticle

17 Citations (Scopus)

Abstract

This paper considers the problem of recovering a one- or two-dimensional 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 one-dimensional 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 languageEnglish
Pages (from-to)682-720
Number of pages39
JournalSIAM Journal on Imaging Sciences
Volume8
Issue number1
Early online date26 Mar 2015
DOIs
Publication statusPublished - 2015

Cite this

On the role of total variation in compressed sensing. / Poon, Clarice.

In: SIAM Journal on Imaging Sciences, Vol. 8, No. 1, 2015, p. 682-720.

Research output: Contribution to journalArticle

@article{0cd77e2b01564036be2e0a7dfec90e88,
title = "On the role of total variation in compressed sensing",
abstract = "This paper considers the problem of recovering a one- or two-dimensional 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 one-dimensional 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$.",
author = "Clarice Poon",
year = "2015",
doi = "10.1137/140978569",
language = "English",
volume = "8",
pages = "682--720",
journal = "SIAM Journal on Imaging Sciences",
issn = "1936-4954",
publisher = "SIAM",
number = "1",

}

TY - JOUR

T1 - On the role of total variation in compressed sensing

AU - Poon, Clarice

PY - 2015

Y1 - 2015

N2 - This paper considers the problem of recovering a one- or two-dimensional 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 one-dimensional 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$.

AB - This paper considers the problem of recovering a one- or two-dimensional 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 one-dimensional 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$.

U2 - 10.1137/140978569

DO - 10.1137/140978569

M3 - Article

VL - 8

SP - 682

EP - 720

JO - SIAM Journal on Imaging Sciences

JF - SIAM Journal on Imaging Sciences

SN - 1936-4954

IS - 1

ER -