Compressed Sensing with 1D Total Variation: Breaking Sample Complexity Barriers via Non-Uniform Recovery

Understand

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{s n} \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 this sampling rate does not reflect the typical behavior of total variation minimization.