Source-linked AI summary
Primal-dual methods and acceleration for Morozov and equality constrained regularization
Diana-Elena Mirciu, Martin Benning, Elena Resmerita
TL;DR
Ill-posed inverse problems require regularization to prevent noisy measurements from producing unstable reconstructions. This paper analyzes non-accelerated and accelerated primal-dual methods, extending error estimates across Hilbert and Banach spaces and verifying assumptions for equality-constrained and Morozov regularization. Numerical experiments support the theoretical results under additive noise.
Problem
Ill-posed inverse problems make direct inversion unstable under measurement noise, motivating regularization analyses for primal-dual methods.
Method
The paper analyzes Condat–Vũ and PDHG schemes with general convex data fidelities, extending non-accelerated analysis to Banach spaces and verifying conditions for equality-constrained and Morozov problems.
Results
The analysis derives Hilbert-space error estimates for both schemes, extends non-accelerated Condat–Vũ theory to Banach spaces, and numerical experiments confirm the theoretical results.
Takeaways & Limitations
The framework supports regularization analysis for noisy linear inverse problems across Euclidean and non-Euclidean settings, including equality-constrained and Morozov formulations.
Takeaways & Limitations
The analysis is restricted to additive noise, while non-additive noise models and accelerated schemes with other step-size choices remain open directions.
Abstract
from arXiv · showhide
This work develops a regularization analysis of non-accelerated and accelerated primal-dual methods for solving linear inverse problems in the presence of noisy data. We investigate a Condat-Vũ algorithm and an accelerated primal-dual hybrid gradient method in Hilbert spaces, with focus on quantifying the effect of data perturbations on the reconstruction error. For the non-accelerated scheme, we derive error estimates in terms of Bregman distances, whereas for the accelerated scheme we establish error estimates in norm. The study accommodates a general class of convex data fidelities satisfying suitable perturbation conditions, which are verified explicitly for equality constrained and Morozov regularization. For the non-accelerated method, the analysis is further extended to Banach spaces, taking into account non-Euclidean geometries and including a particular non-reflexive setting tailored to nonnegative solution reconstruction. The results recover known behavior in classical settings while extending the regularization analysis to these more general frameworks. Numerical experiments with representative regularizers, including sparsity and entropic models, support the theoretical findings and illustrate practical performance under noise.
1 Introduction
The paper addresses ill-posed linear inverse problems with noisy data by analyzing primal-dual methods as regularizing schemes. It develops non-accelerated and accelerated results across Hilbert and Banach spaces, including equality constrained and Morozov formulations.
- Motivation: Ill-posed inverse problems require regularization because direct inversion can amplify measurement noise and produce unstable reconstructions.A regularizer J incorporates prior structural knowledge such as smoothness or sparsity.
- Regularization settings: Tikhonov regularization balances noisy-data fidelity against a structural regularizer, whereas Morozov regularization imposes a residual bound determined by the noise level.Equality-constrained formulations instead fit noisy data exactly and therefore require early stopping to avoid inaccurate reconstructions.
- Primal-dual methods: The study analyzes non-accelerated and accelerated primal-dual hybrid gradient schemes in Hilbert spaces and Condat–Vũ procedures adapted to non-Euclidean Banach-space geometries.The Banach-space settings include simplex constraints via entropic mirror descent.
- Main contributions: For noisy observations and general stable data fidelities, the paper derives convergence rates under a classical source condition and extends the analysis from Hilbert spaces to reflexive and selected nonreflexive Banach spaces.The contributions complement prior analyses focused separately on non-accelerated equality constraints or accelerated schemes with vanishing dual regularization.
2 Preliminaries
The preliminaries establish the Hilbert-space inverse-problem framework, define Bregman tools and source conditions, formulate noisy-data regularization, and provide a generalized boundedness result supporting later error analysis.
- The analysis assumes Hilbert spaces X and Y with a bounded linear ill-posed operator K : X → Y.
- The regularization framework uses proper, convex, lower semicontinuous data fidelities and regularizer R, together with a differentiable function G inducing Bregman distances.The assumptions also require R + G to be continuous at some point in dom(Hf ◦ K) ∩ dom R ∩ dom G.
- A source condition, −K* v† ∈ ∂(R + G)(u†), is imposed on a solution u† when deriving convergence rates.
- Noisy data are handled through a discrepancy function S and the fidelity Hfδ = iCδ, with Cδ = {z : S(fδ, z) ≤ δ}, encompassing equality constraints and Morozov regularization.The norm discrepancy S(fδ, z) = ∥fδ − z∥ gives the inequality-constrained instance.
- Theorem 2.1 generalizes a boundedness lemma from quadratic inequalities to every order q > 1, supporting Condat-Vũ error estimates in Banach spaces.
3 The Condat-V˜u algorithm with noisy data in the Hilbert space setting
This section establishes ergodic convergence and noisy-data error estimates for the Condat-Vũ algorithm with general data fidelities in Hilbert spaces. Under alternative perturbation assumptions and a step-size condition, the estimates quantify primal and dual errors through Bregman distances and ensure convergence as noise vanishes.
- Contribution: The section develops ergodic convergence rates for the Condat-Vũ algorithm with general noisy-data fidelities in Hilbert spaces.The framework assumes (A4) with p = 2 and presents the Hilbert-space arguments before the Banach-space analysis.
- Algorithm: The Condat-Vũ iteration is formulated as a fixed-point procedure and implemented with initial values, positive step sizes, and noisy data.Algorithm 1 returns the primal and dual iterates after repeated proximal updates.
- Error estimates: The resulting bounds control ergodic primal and dual errors through one-sided Bregman distances, while convexity supports the estimates for the averaged sequence.The analysis distinguishes one-sided Bregman distances from symmetric counterparts, whose convexity is not guaranteed.
- Convergence: As the noise level δ tends to zero, the ergodic sequence converges to an optimal solution in the Bregman-distance sense.Using (A8) instead of (A7) yields analogous bounds, with the dual-variable estimate depending on the selected assumption.
4 The accelerated PDHG algorithm with noisy data in the Hilbert space setting
This section analyzes an accelerated PDHG method for noisy-data linear inverse problems in Hilbert spaces with general data fidelities. Under strong convexity and step-size conditions, it derives intermediate dual and primal error estimates, recovering the exact-data O(n^-2) rate while noting that Banach-space acceleration is outside scope.
- Method and setting: The section establishes convergence rates for accelerated PDHG in Hilbert spaces with noisy data and general data fidelity terms.The analysis adapts an accelerated method previously studied for exact data to the noisy setting.
- Method and setting: The method assumes γ-strong convexity of R and uses dynamic step sizes satisfying σ0τ0∥K∥2 < 1.The updates use θk = 1/√(1 + 2γτk), τk+1 = θkτk, and σk+1 = σk/θk.
- Error estimates: Auxiliary estimates bound the dual and primal errors through telescoping inequalities and step-size-dependent quantities.The dual analysis first yields a bound depending on earlier dual iterates, then an estimate independent of them; Theorem 4.5 provides the corresponding primal estimate.
- Rates and scope: For exact data, ∥u† − un∥2 ∼ 1/n2 · ∆1/(τ1γ2) for n ≥ N0, recovering the rate in.This follows by setting δ = 0 in the noisy-data estimate.
- Rates and scope: Acceleration of PDHG in reflexive Banach spaces is not analyzed because noisy-data extensions require more technical parameter choices.The cited Banach-space work concerns exact data, while the noisy-data extension lies beyond this paper’s scope.
5 Particular algorithms in Hilbert spaces
This section specializes the Hilbert-space analysis to equality constrained and Morozov regularization. It gives error estimates for non-accelerated Condat–Vũ and accelerated PDHG methods, with specialized algorithmic forms and perturbation verification.
- The Hilbert-space specialization covers non-accelerated Condat–Vũ and accelerated PDHG for Morozov regularization, plus accelerated PDHG for equality constrained problems.
- Equality constrained problems: For equality constrained problems, the Condat–Vũ method is stated as Algorithm 3 with primal proximal updates, dual variables, step sizes, and noisy data fδ.
- Equality constrained problems: The equality-constrained accelerated scheme is summarized through the dual update vk+1 = vk + σkK˜uk −σkfδ.
- Morozov regularization: Morozov regularization uses the fidelity Hfδ = iCδ with Cδ = {z : ∥fδ −z∥≤δ}, and the assumptions are verified for this setting.
- Morozov regularization: For Morozov regularization, the Condat–Vũ algorithm has a closed-form dual update, while the corresponding accelerated scheme is only described by reference.
6 The Condat-V˜u algorithm with noisy data in the Banach space setting
This section extends noisy-data Condat-Vũ analysis to reflexive Banach spaces, using non-Euclidean primal-dual geometries and deriving ergodic error estimates. It also treats nonnegative probability-simplex reconstruction in the non-reflexive L1 setting through directional derivatives and establishes corresponding convexity and error results.
- Reflexive Banach-space analysis: The generalized Condat-Vũ method is analyzed in reflexive Banach spaces X and Y for general noisy-data fidelities, with ergodic convergence rates for averaged iterates.The analysis highlights differences from the Hilbert-space setting and requires suitable Banach-space duality structures.
- Reflexive Banach-space analysis: The method uses auxiliary functions φ and ψ to define non-Euclidean geometries for primal and dual variables under essential smoothness, strict convexity, and coercivity assumptions.The primal geometry is strongly convex, and the dual geometry is specified analogously through assumptions (A10) and (A11).
- Reflexive Banach-space analysis: Algorithm 5 is well-defined under the stated assumptions, while τσ∥K∥^2 < 1 and a saddle point ensure bounded iterates and saddle-point cluster points for ergodic averages.The saddle-point existence condition is guaranteed by (A6).
- Non-reflexive probability-simplex setting: For nonnegative reconstruction on a probability simplex, the natural space is L1, whose positive cone has empty interior, so the analysis replaces unavailable derivatives with directional derivatives.The model uses the negative Boltzmann-Shannon entropy as the primal geometry.
- Non-reflexive probability-simplex setting: With simplex-indicator regularization, G = 0, and quadratic dual geometry, the specialized method has convex B under τσ∥K∥^2 < 1 and admits error estimates when source condition (A6) also holds.The corresponding proposition establishes both convexity and constants ν > 0 and C̄ > 0 for the estimates.
7 Numerical results
Numerical experiments assess the proposed primal-dual methods on sparse recovery and hyperspectral unmixing. They compare equality-constrained and Morozov formulations, validate theoretical error estimates, and illustrate accelerated convergence and noise amplification.
- Numerical experiments: Experiments apply the proposed algorithms to a sparsity problem and hyperspectral abundance-map recovery.The sparse setup uses a Gaussian Toeplitz-correlated forward matrix and a fifteen-sparse exact solution.
- Equality versus inequality constraint: Morozov regularization attains lower reconstruction errors than equality constraints across all tested noise levels.The comparison tracks the minimizing iteration nmin and corresponding Bregman-distance reconstruction error.
- Equality versus inequality constraint: At δ = 1.6, execution times are 0.56 seconds for equality constraints and 0.68 seconds for Morozov regularization.For small noise levels, the two frameworks have comparable execution times.
- Accelerated versus standard PDHG: The numerical plots confirm the theoretical upper bounds for standard PDHG and accelerated PDHG.The standard method is assessed with the Bregman-distance bound, while acceleration is assessed using squared-error estimates.
- Accelerated versus standard PDHG: Acceleration converges faster, with a sharp drop followed by oscillations in squared error and smooth decay under the Bregman distance.The two methods are theoretically analyzed using different performance quantities.
- Hyperspectral unmixing: In hyperspectral unmixing, abundance vectors satisfy nonnegativity and sum-to-one simplex constraints, with equality or Morozov data fidelity.The experiments use entropic and simplex-based Banach-space modeling and plot relative error, Bregman distance, and data residual diagnostics.
Conclusions
The work establishes regularization theory for primal–dual splitting algorithms applied to ill-posed inverse problems with additive noisy data. It derives Hilbert-space error estimates and extends the non-accelerated analysis to Banach and nonreflexive settings, while identifying open directions.
- Contributions: The study establishes regularization theory for selected primal–dual splitting algorithms in ill-posed inverse problems with noisy data.The framework addresses additive noise models.
- Contributions: In Hilbert spaces, it derives error estimates for both the Condat–Vũ and accelerated PDHG methods under a standard source condition.
- Contributions: The non-accelerated Condat–Vũ analysis is extended to Banach spaces, including an entropic PDHG instance in a natural nonreflexive setting.
- Open directions: Extending the framework to non-additive noise models and studying accelerated schemes with other step-size choices remain open problems.
A Appendix · A.1 Proof of Theorem 2.1
The proof fixes n ≥ 1 and uses the maximum b_n, monotonicity, and non-negativity to derive the required inequalities. The conclusion follows from the conjugacy identity q(q−1)p = 1.
- A.1 Proof of Theorem 2.1: The proof begins by fixing n ≥ 1 and applying the theorem’s assumptions for each k ∈ {1, . . . , n}.
- A.1 Proof of Theorem 2.1: It defines b_n as the maximum of a_k over 1 ≤ k ≤ n.
- A.1 Proof of Theorem 2.1: Because (S_n) is non-decreasing and (λ_n) lies in [0, +∞), the proof uses these properties to obtain an inequality involving b_n.
- A.1 Proof of Theorem 2.1: Non-negativity of (a_n), and hence of (b_n), together with non-negativity of (λ_n), supports the subsequent estimate.
- A.1 Proof of Theorem 2.1: The inequality is applied with k arbitrarily fixed in {1, . . . , n}, enabling the proof to pass to a bound involving b_n.
- A.1 Proof of Theorem 2.1: The definition of b_n supplies the first inequality in the final estimate.
- A.1 Proof of Theorem 2.1: The proof concludes using q (q−1)p = 1.
A.2 Additional figures - Comparison of the equality constrained formulation with the Morozov regularization
The section compares equality-constrained and Morozov reconstructions through abundance maps, error estimates across noise levels, and source-element validation. The figures include results for α = 0 and α = 1 and assess whether the estimated source element is correct.
- Abundance maps: Abundance maps compare ground truth with equality and Morozov solver reconstructions for Asphalt, Meadows, and Trees at α = 0 and α = 1.The maps show the best current iterates minimizing DR+Gα.
- Error estimates: The error estimate is compared for current iterates at different noise levels.
- Source-element validation: The comparison between −K∗v† and the sign of u† indicates that the estimated source element v† is correct.