  In this paper, we consider the use of Total Variation (TV) minimization for
compressive imaging; that is, image reconstruction from subsampled
measurements. Focusing on two important imaging modalities -- namely, Fourier
imaging and structured binary imaging via the Walsh--Hadamard transform -- we
derive uniform recovery guarantees asserting stable and robust recovery for
arbitrary random sampling strategies. Using this, we then derive a class of
theoretically-optimal sampling strategies. For Fourier sampling, we show
recovery of an image with approximately $s$-sparse gradient from $m \gtrsim_d s
\cdot \log^2(s) \cdot \log^4(N)$ measurements, in $d \geq 1$ dimensions. When
$d = 2$, this improves the current state-of-the-art result by a factor of
$\log(s) \cdot \log(N)$. It also extends it to arbitrary dimensions $d \geq 2$.
For Walsh sampling, we prove that $m \gtrsim_d s \cdot \log^2(s) \cdot
\log^2(N/s) \cdot \log^3(N) $ measurements suffice in $d \geq 2$ dimensions. To
the best of our knowledge, this is the first recovery guarantee for structured
binary sampling with TV minimization.
