Journal article
Guarantees of total variation minimization for signal recovery
Information and inference, Vol.4(4), pp.328-353
12/2015
DOI: 10.1093/imaiai/iav009
Abstract
In this paper, we consider using total variation (TV) minimization to recover signals whose gradients have a sparse support, from a small number of measurements. We establish a proof for the performance guarantee of TV minimization in recovering one-dimensional signal with sparse gradient support. This answers the open question of proving the fidelity of TV minimization in such a setting. We have shown that, when the number of Gaussian measurements
$M\gtrsim \sqrt {NK}\log N$
, the TV minimization guarantees the exact recovery of any signal of size
$N$
with at most
$K$
non-zero gradients with high probability; when
$M\lesssim \sqrt {NK}$
, the TV minimization cannot find the original signal with a moderate probability. Last but not least, when
$M$
grows linearly with the signal dimension, we will also show that the recoverable sparsity
$K$
grows linearly with the signal dimension as well.
Details
- Title: Subtitle
- Guarantees of total variation minimization for signal recovery
- Creators
- Jian-Feng Cai - University of IowaWeiyu Xu - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Information and inference, Vol.4(4), pp.328-353
- Publisher
- Oxford University Press
- DOI
- 10.1093/imaiai/iav009
- ISSN
- 2049-8764
- eISSN
- 2049-8772
- Language
- English
- Date published
- 12/2015
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984197270002771
Metrics
4 Record Views