Compressed Sensing with 1D Total Variation: Breaking Sample Complexity Barriers via Non-Uniform Recovery (iTWIST'20)

Abstract

This paper investigates total variation minimization in one spatial dimension for the recovery of gradient-sparse signals from undersampled Gaussian measurements. Recently established bounds for the required sampling rate state that uniform recovery of all $s$-gradient-sparse signals in ${\mathbb{R}}^n$ is only possible with $m\gtrsim \sqrt{sn}\cdot \text{PolyLog}(n)$ measurements. Such a condition is especially prohibitive for high-dimensional problems, where $s$ is much smaller than $n$. However, previous empirical findings seem to indicate that the latter sampling rate does not reflect the typical behavior of total variation minimization. Indeed, this work provides a rigorous analysis that breaks the $\sqrt{sn}$-bottleneck for a large class of natural signals. The main result shows that non-uniform recovery succeeds with high probability for $m\gtrsim s\cdot \text{PolyLog}(n)$ measurements if the jump discontinuities of the signal vector are sufficiently well separated. In particular, this guarantee allows for signals arising from a discretization of piecewise constant functions defined on an interval. The present paper serves as a short summary of the main results in our recent work [arxiv:2001.09952].

in Proceedings of iTWIST'20, Paper-ID: 32, Nantes, France, December, 2-4, 2020. arXiv admin note: substantial text overlap with arXiv:2001.09952