Guarantees of total variation minimization for signal recovery

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 [1]. We also extend our results to TV minimization for multidimensional signals. Recoverable sparsity thresholds of TV minimization are explicitly computed for 1-dimensional signal by using the Grassmann angle framework. In particular, we have shown that the recoverable gradient sparsity can grow linearly with the signal dimension when TV minimization is used. 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'.