pith. sign in

arxiv: 2505.01240 · v3 · submitted 2025-05-02 · 🧮 math.OC · cs.NA· math.NA

Asymptotic Linear Convergence of ADMM for Isotropic TV Norm Compressed Sensing

Emmanuel Gil Torres , Matt Jacobs , Xiangxiong Zhang This is my paper

Pith reviewed 2026-05-22 17:12 UTC · model grok-4.3

classification 🧮 math.OC cs.NAmath.NA
keywords ADMMlinear convergenceisotropic total variationcompressed sensingDouglas-Rachford splittingMRI reconstructionoptimization
0
0 comments X

The pith

ADMM achieves an explicit local linear convergence rate for isotropic total variation compressed sensing in multiple dimensions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the alternating direction method of multipliers converges linearly at an explicit local rate when applied to compressed sensing problems that use the isotropic total variation norm in two or more dimensions. The proof works by rewriting the original problem as an equivalent dual and then applying Douglas-Rachford splitting, after which the evolution of one auxiliary variable is tracked through the iterations. A reader would care because the result supplies a concrete, a priori bound on how quickly a practical algorithm settles for a family of reconstruction problems that appear in imaging and medical data processing, and numerical checks on large three-dimensional cases and real MRI scans show the bound sits close to the speeds actually observed.

Core claim

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.

What carries the argument

The auxiliary variable in the Douglas-Rachford splitting of the dual problem, which is tracked across iterations to establish the local linear rate.

If this is right

  • ADMM converges linearly for the isotropic TV problem in two and three dimensions.
  • The analysis supplies an explicit upper bound on the convergence factor.
  • The bound lies close to the contraction rates measured in large-scale numerical tests.
  • The same rate applies to reconstructions performed on real MRI data.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same auxiliary-variable tracking strategy could be tried on other splitting methods or on related regularizers such as anisotropic total variation.
  • A sharper version of the rate might be obtainable by tightening the estimates on the auxiliary variable, which would be directly useful for choosing algorithm parameters in practice.
  • The dual reformulation approach may connect to convergence proofs for ADMM on other convex imaging problems that lack current rate guarantees.

Load-bearing premise

The isotropic TV compressed sensing problem admits an equivalent dual formulation whose Douglas-Rachford splitting has an auxiliary variable whose behavior can be tracked to produce a local linear rate.

What would settle it

Run ADMM on a concrete 3D isotropic TV compressed sensing instance, compute the observed contraction factor of the error, and check whether it remains bounded by the explicit rate given in the analysis.

Figures

Figures reproduced from arXiv: 2505.01240 by Emmanuel Gil Torres, Matt Jacobs, Xiangxiong Zhang.

Figure 1
Figure 1. Figure 1: The local linear rate of uk−u∗ for TVCS. Here, u∗ is the true image, and uk is the image at k-th iteration of ADMM. Left: 2D Shepp–Logan phantom (64×64), step size γ = 1 τ = 100, K = 4300. Right: 3D Shepp–Logan phantom (5123 ), step size γ = 1 τ = 10, K = 600. In both tests, about 30% of the Fourier frequencies are observed. posed as a linear program [1], for which the results in [22] applies. By the idea … view at source ↗
Figure 2
Figure 2. Figure 2: Algorithm 1 with γ = 1 τ for (1a) with 30% observed frequencies for a 2D Shepp-Logan image of size 64 × 64. Here k is not the iteration number. Instead, k +l is the iteration number where l is the number of iteration needed to enter the linear convergence regime. 5.2 Effects of Regularization and Relaxation Consider a generalized version of ADMM by applying the general DRS op￾erator Hλ τ = (1 − λ)I + λ I+R… view at source ↗
Figure 3
Figure 3. Figure 3: Local convergence rate of generalized ADMM (corresponding to the [PITH_FULL_IMAGE:figures/full_fig_p024_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Left: The initial guess in ADMM. Middle: the non-zero entries of [PITH_FULL_IMAGE:figures/full_fig_p024_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: 3D MR image of size 5123 . Left: slices of the initial condition for the primal variable in ADMM. Middle: slices of the primal variable of ADMM with γ = 1 22 after 50 iterations. Right: slices of the true MR image. 0 25 50 75 100 125 150 175 200 Iterations 10 12 10 10 10 8 10 6 10 4 10 2 10 0 10 2 Error Precision Comparison FP64 TF32 FP32 [PITH_FULL_IMAGE:figures/full_fig_p025_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: 3D Shepp-Logan image of size 1283 with 30% observed frequencies. ADMM with γ = 1 τ = 1 22 . Performance of the algorithm using Double Precision vs Single Precision (FP32 and TF32) in Python Jax on Nvidia A100 [PITH_FULL_IMAGE:figures/full_fig_p025_6.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims to prove an explicit local linear convergence rate for ADMM applied to the isotropic Total Variation norm compressed sensing problem in multiple dimensions. The proof proceeds by reformulating the problem as an equivalent dual problem and tracking the auxiliary variable in the corresponding Douglas-Rachford splitting; numerical experiments on large 3D instances and real MRI data are mentioned to support the result, although the proven rate is stated to be non-sharp.

Significance. An explicit local linear rate for ADMM on this class of problems would be a useful theoretical contribution in optimization for imaging, as it supplies a concrete upper bound on the asymptotic behavior even if the bound is not tight. The numerical verification on 3D and MRI data provides some practical grounding, but the absence of error bars or exhaustive test-suite details limits the strength of the empirical support.

major comments (2)
  1. [Abstract] Abstract, paragraph 1: The central claim is an explicit local linear rate obtained by analyzing the auxiliary variable in the dual Douglas-Rachford splitting. However, the manuscript does not supply a quantitative radius for the neighborhood in which the asserted contraction holds, nor does it show that this radius is positive independently of the sensing matrix A and the regularization parameter. This is load-bearing for the applicability of the rate to the generated iterates.
  2. [Proof section] Proof section (presumably §3 or §4 containing the main theorem): The local contraction property for the auxiliary-variable map is invoked after the nonlinear projection onto the dual ball of the gradient operator. No explicit Lipschitz constant or error-bound modulus is derived that would guarantee the contraction factor is strictly less than one inside a verifiable ball; without this, the explicit rate remains conditional on an unverified local regime.
minor comments (2)
  1. [Numerical experiments] Numerical experiments: The abstract mentions verification on 3D problems and MRI data, yet provides no information on the number of trials, error bars, or the range of problem dimensions and undersampling ratios tested. Adding these details would strengthen the empirical section.
  2. [Notation] Notation: The distinction between the primal ADMM iterates and the auxiliary variable of the dual Douglas-Rachford splitting should be made clearer in the statement of the main theorem to avoid reader confusion.

Simulated Author's Rebuttal

2 responses · 1 unresolved

We thank the referee for the careful reading and constructive major comments. We address each point below and will revise the manuscript to strengthen the presentation of the local regime while preserving the core contribution of an explicit (though non-sharp) linear rate.

read point-by-point responses

  1. Referee: [Abstract] Abstract, paragraph 1: The central claim is an explicit local linear rate obtained by analyzing the auxiliary variable in the dual Douglas-Rachford splitting. However, the manuscript does not supply a quantitative radius for the neighborhood in which the asserted contraction holds, nor does it show that this radius is positive independently of the sensing matrix A and the regularization parameter. This is load-bearing for the applicability of the rate to the generated iterates.

    Authors: We agree that an explicit quantitative radius would make the local result more readily applicable. The proof establishes contraction of the auxiliary-variable map in a sufficiently small ball by exploiting the non-expansiveness of the projection onto the dual ball of the gradient operator together with the spectral properties of the linear Douglas-Rachford operator. Deriving a radius that is positive and independent of A and λ without additional assumptions on A (e.g., RIP-type conditions) is not straightforward and may not hold in full generality. In the revision we will add a clarifying remark after the main theorem that states the local nature explicitly and indicates how the ball radius can be estimated from the distance of the initial iterate to the fixed point when such estimates are available. revision: partial

  2. Referee: [Proof section] Proof section (presumably §3 or §4 containing the main theorem): The local contraction property for the auxiliary-variable map is invoked after the nonlinear projection onto the dual ball of the gradient operator. No explicit Lipschitz constant or error-bound modulus is derived that would guarantee the contraction factor is strictly less than one inside a verifiable ball; without this, the explicit rate remains conditional on an unverified local regime.

    Authors: The referee is correct that the current write-up invokes the contraction after the projection step without supplying an explicit modulus. In the analysis we bound the map by a linear operator whose norm is strictly less than one plus the non-expansive projection; the resulting composite is therefore contractive inside a small enough neighborhood. To address the concern we will insert a short lemma in the revised proof section that derives a concrete (conservative) error-bound modulus for the projection step and thereby produces an explicit, albeit possibly small, ball radius expressed in terms of the operator norms appearing in the Douglas-Rachford iteration. This will make the local regime verifiable from the problem data. revision: yes

standing simulated objections not resolved
  • Showing that the radius is positive independently of the sensing matrix A and the regularization parameter without further assumptions on A.

Circularity Check

0 steps flagged

No circularity: derivation is a self-contained local contraction analysis

full rationale

The paper derives an explicit local linear rate for ADMM by reformulating the isotropic TV compressed sensing problem as an equivalent dual problem and applying Douglas-Rachford splitting, then tracking the auxiliary variable to obtain a contraction. This is a standard analytic argument in operator splitting theory that does not reduce any claimed prediction or rate to a fitted parameter, self-citation chain, or definitional tautology. The abstract and reader's summary indicate the proof proceeds from the dual proximal mapping and local error bounds without invoking prior results by the same authors as load-bearing uniqueness theorems or smuggling ansatzes. No quoted equation equates a derived quantity to its own input by construction, so the central claim retains independent mathematical content.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the existence of an equivalent dual formulation that permits Douglas-Rachford splitting and on standard convexity and subdifferential properties of the isotropic TV norm; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption The isotropic TV compressed sensing problem admits an equivalent dual formulation to which Douglas-Rachford splitting applies.
    Invoked in the abstract to enable the auxiliary-variable analysis.
  • standard math Standard properties of convex subdifferentials and proximal operators hold for the TV norm and the data-fidelity term.
    Background assumption required for any ADMM or Douglas-Rachford convergence argument.

pith-pipeline@v0.9.0 · 5626 in / 1422 out tokens · 65444 ms · 2026-05-22T17:12:04.181837+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages

  1. [1]

    and Goldfarb, D.: Second-order cone programming, Math

    Alizadeh, F. and Goldfarb, D.: Second-order cone programming, Math. Program.95(1), 3–51 (2003). Local Convergence Rate for TV Compressed Sensing 31

    work page 2003

  2. [2]

    R.: Local linear convergence of the ADMM/Douglas–Rachford algorithms without strong convexity and application to statistical imaging, SIAM J

    Aspelmeier, T., Charitha, C., and Luke, D. R.: Local linear convergence of the ADMM/Douglas–Rachford algorithms without strong convexity and application to statistical imaging, SIAM J. Imaging Sci.9(2), 842– 868 (2016)

    work page 2016

  3. [3]

    H., Cruz, J

    Bauschke, H. H., Cruz, J. B., Nghia, T. T., Phan, H. M., and Wang, X.: The rate of linear convergence of the Douglas–Rachford algorithm for subspaces is the cosine of the Friedrichs angle, J. Approx. Theory185, 63–79 (2014)

    work page 2014

  4. [4]

    SIAM, (2017)

    Beck, A.: First-Order Methods in Optimization. SIAM, (2017)

    work page 2017

  5. [5]

    and Golub, G

    Bj¨ orck, ˚A. and Golub, G. H.: Numerical methods for computing angles between linear subspaces, Math. Comp.27(123), 579–594 (1973)

    work page 1973

  6. [6]

    Optim.23(4), 2183–2207 (2013)

    Boley, D.: Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs, SIAM J. Optim.23(4), 2183–2207 (2013)

    work page 2013

  7. [7]

    J., Romberg, J., and Tao, T.: Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency informa- tion, IEEE Trans

    Cand` es, E. J., Romberg, J., and Tao, T.: Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency informa- tion, IEEE Trans. Inform. Theory52(2), 489–509 (2006)

    work page 2006

  8. [8]

    and Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging, J

    Chambolle, A. and Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision 40, 120–145 (2011)

    work page 2011

  9. [9]

    and Yin, W

    Davis, D. and Yin, W. Convergence rate analysis of several splitting schemes. In: Splitting Methods in Communication, Imaging, Science, and Engineering. Ed. by Glowinski, R., Osher, S. J., and Yin, W. Cham: Springer International Publishing, 2016, 115–163

    work page 2016

  10. [10]

    and Zhang, X.: Eventual linear convergence of the Douglas- Rachford iteration for basis pursuit, Math

    Demanet, L. and Zhang, X.: Eventual linear convergence of the Douglas- Rachford iteration for basis pursuit, Math. Comp.85(297), 209–238 (2016)

    work page 2016

  11. [11]

    Esser, E.: Applications of Lagrangian-based alternating direction meth- ods and connections to split Bregman, CAM report9, 31 (2009)

    work page 2009

  12. [12]

    F.: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM J

    Esser, E., Zhang, X., and Chan, T. F.: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM J. Imaging Sci.3(4), 1015–1046 (2010)

    work page 2010

  13. [13]

    and Glowinski, R.: Augmented Lagrangian Methods: Appli- cations to the Numerical Solution of Boundary-Value Problems

    Fortin, M. and Glowinski, R.: Augmented Lagrangian Methods: Appli- cations to the Numerical Solution of Boundary-Value Problems. North- Holland Publishing Co., Amsterdam, (1983)

    work page 1983

  14. [14]

    Friedlander, M. P. and Tseng, P.: Exact regularization of convex pro- grams, SIAM J. Optim.18(4), 1326–1350 (2008)

    work page 2008

  15. [15]

    Fuchs, J.-J.: On sparse representations in arbitrary redundant bases, IEEE Trans. Inform. Theory50(6), 1341–1344 (2004)

    work page 2004

  16. [16]

    M´ ethodes num´ eriques pour l’optimisation non lin´ eaire

    Gabay, D. M´ ethodes num´ eriques pour l’optimisation non lin´ eaire. Th` ese d’´Etat. Universit´ e Pierre et Marie Curie, 1979

    work page 1979

  17. [17]

    Applications of the method of multipliers to variational in- equalities

    Gabay, D. Applications of the method of multipliers to variational in- equalities. In: Augmented Lagrangian Methods: Applications to the nu- merical solution of boundary-value problems. Ed. by Fortin, M. and Glowinski, R. North-Holland Publishing Co., Amsterdam, 1983, 299– 331. 32 Emmanuel Gil Torres et al

    work page 1983

  18. [18]

    and Boyd, S.: Linear convergence and metric selection for Douglas-Rachford splitting and ADMM, IEEE Trans

    Giselsson, P. and Boyd, S.: Linear convergence and metric selection for Douglas-Rachford splitting and ADMM, IEEE Trans. Automat. Control 62(2), 532–544 (2016)

    work page 2016

  19. [19]

    and Le Tallec, P.: Augmented Lagrangian and operator- splitting methods in nonlinear mechanics

    Glowinski, R. and Le Tallec, P.: Augmented Lagrangian and operator- splitting methods in nonlinear mechanics. SIAM, (1989)

    work page 1989

  20. [20]

    and Yin, W.: Second-order cone programming methods for total variation-based image restoration, SIAM J

    Goldfarb, D. and Yin, W.: Second-order cone programming methods for total variation-based image restoration, SIAM J. Sci. Comput.27(2), 622–645 (2005)

    work page 2005

  21. [21]

    and Osher, S.: The split Bregman method for L1-regularized problems, SIAM J

    Goldstein, T. and Osher, S.: The split Bregman method for L1-regularized problems, SIAM J. Imaging Sci.2(2), 323–343 (2009)

    work page 2009

  22. [22]

    and Yuan, X.: Local linear convergence of the alternating di- rection method of multipliers for quadratic programs, SIAM J

    Han, D. and Yuan, X.: Local linear convergence of the alternating di- rection method of multipliers for quadratic programs, SIAM J. Numer. Anal.51(6), 3446–3457 (2013)

    work page 2013

  23. [23]

    Jacobs, M., L´ eger, F., Li, W., and Osher, S.: Solving large-scale op- timization problems with a convergence rate independent of grid size, SIAM J. Numer. Anal.57(3), 1100–1123 (2019)

    work page 2019

  24. [24]

    P., Koistinen, P., Lassas, M., Pirttil¨ a, J., and Somersalo, E.: Statistical inversion for med- ical X-ray tomography with few radiographs: II

    Kolehmainen, V., Siltanen, S., J¨ arvenp¨ a¨ a, S., Kaipio, J. P., Koistinen, P., Lassas, M., Pirttil¨ a, J., and Somersalo, E.: Statistical inversion for med- ical X-ray tomography with few radiographs: II. Application to dental radiology, Physics in Medicine & Biology48(10), 1465 (2003)

    work page 2003

  25. [25]

    A., and Holland, D

    Leary, R., Saghi, Z., Midgley, P. A., and Holland, D. J.: Compressed sensing electron tomography, Ultramicroscopy131, 70–91 (2013)

    work page 2013

  26. [26]

    S.: Active sets, nonsmoothness, and sensitivity, SIAM J

    Lewis, A. S.: Active sets, nonsmoothness, and sensitivity, SIAM J. Op- tim.13(3), 702–725 (2002)

    work page 2002

  27. [27]

    Li, M., Yang, H., and Kudo, H.: An accurate iterative reconstruction algorithm for sparse objects: Application to 3D blood vessel reconstruc- tion from a limited number of projections, Physics in Medicine & Biology 47(15), 2599 (2002)

    work page 2002

  28. [28]

    Liang, J., Fadili, J., and Peyr´ e, G.: Local convergence properties of Douglas–Rachford and alternating direction method of multipliers, J. Optim. Theory Appl.172, 874–913 (2017)

    work page 2017

  29. [29]

    and Mercier, B.: Splitting algorithms for the sum of two nonlinear operators, SIAM J

    Lions, P.-L. and Mercier, B.: Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal.16(6), 964–979 (1979)

    work page 1979

  30. [30]

    Liu, X., Shen, J., and Zhang, X.: A simple GPU implementation of spectral-element methods for solving 3D Poisson type equations on rect- angular domains and its applications, Commun. Comput. Phys.36(5), 1157–1185 (2024)

    work page 2024

  31. [31]

    M.: Sparse MRI: The application of compressed sensing for rapid MR imaging, Magnetic Resonance in Medicine58(6), 1182–1195 (2007)

    Lustig, M., Donoho, D., and Pauly, J. M.: Sparse MRI: The application of compressed sensing for rapid MR imaging, Magnetic Resonance in Medicine58(6), 1182–1195 (2007)

    work page 2007

  32. [32]

    Persson, M., Bone, D., and Elmqvist, H.: Total variation norm for three- dimensional iterative reconstruction in limited view angle tomography, Physics in Medicine & Biology46(3), 853 (2001)

    work page 2001

  33. [33]

    Imaging Sci.8(1), 682–720 (2015)

    Poon, C.: On the role of total variation in compressed sensing, SIAM J. Imaging Sci.8(1), 682–720 (2015)

    work page 2015

  34. [34]

    T.: Convex Analysis

    Rockafellar, R. T.: Convex Analysis. Princeton University Press, (1970). Local Convergence Rate for TV Compressed Sensing 33

    work page 1970

  35. [35]

    I., Osher, S., and Fatemi, E.: Nonlinear total variation based noise removal algorithms, Phys

    Rudin, L. I., Osher, S., and Fatemi, E.: Nonlinear total variation based noise removal algorithms, Phys. D60(1-4), 259–268 (1992)

    work page 1992

  36. [36]

    and Symes, W

    Santosa, F. and Symes, W. W.: Linear inversion of band-limited reflec- tion seismograms, SIAM J. Sci. Statist. Comput.7(4), 1307–1330 (1986)

    work page 1986

  37. [37]

    Shepp, L. A. and Logan, B. F.: The Fourier reconstruction of a head section, IEEE Transactions on Nuclear Science21(3), 21–43 (1974)

    work page 1974

  38. [38]

    Medical Imaging 2007: Physics of Medical Imaging6510

    Velikina, J., Leng, S., and Chen, G.-H.: Limited view angle tomographic image reconstruction via total variation minimization. Medical Imaging 2007: Physics of Medical Imaging6510. SPIE, 709–720 (2007)

    work page 2007

  39. [39]

    M., and Vandergheynst, P.: Compressed sensing imaging techniques for radio interferometry, Monthly Not

    Wiaux, Y., Jacques, L., Puy, G., Scaife, A. M., and Vandergheynst, P.: Compressed sensing imaging techniques for radio interferometry, Monthly Not. Roy. Astr. Soc.395(3), 1733–1742 (2009)

    work page 2009

  40. [40]

    Imaging Sci.3(4), 856–877 (2010)

    Yin, W.: Analysis and generalizations of the linearized Bregman method, SIAM J. Imaging Sci.3(4), 856–877 (2010)

    work page 2010

  41. [41]

    Zhang, H., Yin, W., and Cheng, L.: Necessary and sufficient conditions of solution uniqueness in 1-norm minimization, J. Optim. Theory Appl. 164, 109–122 (2015)

    work page 2015