# Guarantees of Total Variation Minimization for Signal Recovery

arXiv: https://arxiv.org/abs/1301.6791 · HTML: https://mlsanity.com/paper/1301.6791/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2013.

## Built on by (most cited first, 3 of 3)

- [Guaranteed Tensor Recovery Fused Low-rankness and Smoothness](https://mlsanity.com/paper/2302.02155/) (2023)
- [Enhanced total variation minimization for stable image reconstruction](https://mlsanity.com/paper/2201.02979/) (2022)
- [Low Complexity Regularized Phase Retrieval](https://mlsanity.com/paper/2407.16413/) (2024)

## Abstract (arXiv)

In this paper, we consider using total variation minimization to recover signals whose gradients have a sparse support, from a small number of measurements. We establish the proof for the performance guarantee of total variation (TV) minimization in recovering one-dimensional signal with sparse gradient support. This partially answers the open problem of proving the fidelity of total variation minimization in such a setting citeTVMulti. In particular, we have shown that the recoverable gradient sparsity can grow linearly with the signal dimension when TV minimization is used. Recoverable sparsity thresholds of TV minimization are explicitly computed for 1-dimensional signal by using the Grassmann angle framework. We also extend our results to TV minimization for multidimensional signals. Stability of recovering signal itself using 1-D TV minimization has also been established through a property called "almost Euclidean property for 1-dimensional TV norm". We further give a lower bound on the number of random Gaussian measurements for recovering 1-dimensional signal vectors with N elements and K-sparse gradients. Interestingly, the number of needed measurements is lower bounded by Omega((NK)^frac12), rather than the O(Klog(N/K)) bound frequently appearing in recovering K-sparse signal vectors.