Asymptotic Linear Convergence of ADMM for Isotropic TV Norm Compressed Sensing

2025/05/02 by Torres, Emmanuel Gil, Matt Jacobs, Xiangxiong Zhang +2 · 2 citations
Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Photoacoustic and Ultrasonic Imaging #Image and Signal Denoising Methods

paper · pdf · doi:10.48550/arxiv.2505.01240

Abstract

We prove an explicit local linear rate for ADMM solving the isotropic Total Variation (TV) norm compressed sensing problem in multiple dimensions, by analyzing the auxiliary variable in the equivalent Douglas-Rachford splitting on a dual problem. Numerical verification on large 3D problems and real MRI data will be shown. Though the proven rate is not sharp, it is close to the observed ones in numerical tests. The proven rate is not sharp, but it provides an explicit upper bound that appears close to the observed convergence rate in numerical experiments, although we do not claim this behavior holds in general.

Cited by

• Efficient optimization-based invariant-domain-preserving limiters in solving gas dynamics equations
• Exact Total Variation Minimizers as Non-Oscillatory Limiters in High-Order Methods for Conservation Laws

Related

• ADMM-MCP Framework for Sparse Recovery with Global Convergence
• On asymptotic structure in compressed sensing
• An Approximate Message Passing Algorithm for Rapid Parameter-Free\n Compressed Sensing MRI
• Analysis of The Ratio of ℓ₁ and ℓ₂ Norms in Compressed Sensing
• The Replica-Symmetric Prediction for Compressed Sensing with Gaussian Matrices is Exact