  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. The present work provides a rigorous analysis that
breaks the $\sqrt{s n}$-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 key ingredient of the proof is a
novel upper bound for the associated conic Gaussian mean width, which is based
on a signal-dependent, non-dyadic Haar wavelet transform. Furthermore, a
natural extension to stable and robust recovery is addressed.
