Improved recovery guarantees and sampling strategies for TV minimization in compressive imaging

Abstract

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\ge 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\ge 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\ge 2$ dimensions. To the best of our knowledge, this is the first recovery guarantee for structured binary sampling with TV minimization.

References in corpus (1)

• On asymptotic structure in compressed sensing