2020/09/17 by Adcock, Ben, Dexter, Nick, Xu, Qinghong
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2009.08555
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 \gtrsimd s ⋅ log2(s) ⋅ log4(N) measurements, in d ≥ 1 dimensions. When d = 2, this improves the current state-of-the-art result by a factor of log(s) ⋅ log(N). It also extends it to arbitrary dimensions d ≥ 2. For Walsh sampling, we prove that m \gtrsimd s ⋅ log2(s) ⋅ log2(N/s) ⋅ log3(N) measurements suffice in d ≥ 2 dimensions. To the best of our knowledge, this is the first recovery guarantee for structured binary sampling with TV minimization.