Improved Recovery Guarantees and Sampling Strategies for TV Minimization in Compressive Imaging

DOI10.1137/20M136788XMaRDI QIDQ5860357zbMATH OpenOpenAlexFDO

Authors Ben Adcock, Nick C. Dexter, Qinghong Xu

Publication date 19 November 2021

Published in SIAM Journal on Imaging Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.08555

zbMATH Keywords

binary imagingcompressive imagingFourier imagingsampling strategiesTV minimization

Mathematics Subject Classification ID

Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Nontrigonometric harmonic analysis involving wavelets and other special systems (42C40) Analysis of algorithms and problem complexity (68Q25) Computing methodologies for image processing (68U10) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Sampling theory in information and communication theory (94A20)

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 $mgtrsi{m}_{d}scdotlo{g}^2(s)cdotlo{g}^4(N)$ measurements, in $dgeq1$ dimensions. When $d=2$, this improves the current state-of-the-art result by a factor of $log(s)cdotlog(N)$. It also extends it to arbitrary dimensions $dgeq2$. For Walsh sampling, we prove that $mgtrsi{m}_{d}scdotlo{g}^2(s)cdotlo{g}^2(N/s)cdotlo{g}^3(N)$ measurements suffice in $dgeq2$ dimensions. To the best of our knowledge, this is the first recovery guarantee for structured binary sampling with TV minimization.

Recommendations

• Stable and Robust Sampling Strategies for Compressive Imaging
• Near-Optimal Compressed Sensing Guarantees for Total Variation Minimization
• Compressive total variation for image reconstruction and restoration
• On the role of total variation in compressed sensing
• Image compressive sensing reconstruction based on low-rank and total variation regularization
• Compressive imaging: structure, sampling, learning. With contributions by Vegard Antun
• Compressed sensing with 1D total variation: breaking sample complexity barriers via non-uniform recovery
• Compressive Sensing and Recovery for Binary Images

Cites work

• A mathematical introduction to compressive sensing
• A mixed ℓ₁ regularization approach for sparse simultaneous approximation of parameterized PDEs
• An introduction to continuous optimization for imaging
• An introduction to total variation for image analysis
• Breaking the coherence barrier: a new theory for compressed sensing
• Close Encounters of the Binary Kind: Signal Reconstruction Guarantees for Compressive Hadamard Sampling With Haar Wavelet Basis
• Compressed sensing with local structure: uniform recovery guarantees for the sparsity in levels class
• Compressive imaging: structure, sampling, learning. With contributions by Vegard Antun
• Geometric properties of solutions to the total variation denoising problem
• Guarantees of total variation minimization for signal recovery
• scientific article; zbMATH DE number 49667 (Why is no real title available?)
• Multivariate approximation
• Near-Optimal Compressed Sensing Guarantees for Total Variation Minimization
• NESTA: A fast and accurate first-order method for sparse recovery
• On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels
• On the role of total variation in compressed sensing
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Stable and Robust Sampling Strategies for Compressive Imaging
• Stable image reconstruction using total variation minimization
• Uniform recovery in infinite-dimensional compressed sensing and applications to structured binary sampling

Cited in

(11)

• A note on the guarantees of total variation minimization
• NESTANets: stable, accurate and efficient neural networks for analysis-sparse inverse problems
• Stable image reconstruction using total variation minimization
• Optimal compressive imaging of Fourier data
• WARPd: a linearly convergent first-order primal-dual algorithm for inverse problems with approximate sharpness conditions
• Compressed sensing with 1D total variation: breaking sample complexity barriers via non-uniform recovery
• Patch-Based Holographic Image Sensing
• Enhanced total variation minimization for stable image reconstruction
• Discretization of non-uniform rational B-spline (NURBS) models for meshless isogeometric analysis
• Near-optimal tensor recovery guarantees for transformed total variation minimization
• Restarts subject to approximate sharpness: a parameter-free and optimal scheme for first-order methods

Describes a project that uses

Uses Software

• NESTA

This page was built for publication: Improved Recovery Guarantees and Sampling Strategies for TV Minimization in Compressive Imaging

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5860357)