Accelerated iterative regularization via dual diagonal descent

DOI10.1137/19M1308888zbMATH Open1461.90093arXiv1912.12153OpenAlexW2997044101MaRDI QIDQ5853571FDOQ5853571

Authors: Luca Calatroni, Guillaume Garrigos, Lorenzo Rosasco, Silvia Villa 

Publication date: 10 March 2021

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: We propose and analyze an accelerated iterative dual diagonal descent algorithm for the solution of linear inverse problems with general regularization and data-fit functions. In particular, we develop an inertial approach of which we analyze both convergence and stability. Using tools from inexact proximal calculus, we prove early stopping results with optimal convergence rates for additive data-fit terms as well as more general cases, such as the Kullback-Leibler divergence, for which different type of proximal point approximations hold.

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

Recommendations

• Iterative regularization via dual diagonal descent
• Irregularization accelerates iterative regularization
• Accelerated Landweber iteration with convex penalty for linear inverse problems in Banach spaces
• Accelerated projected steepest descent method for nonlinear inverse problems with sparsity constraints
• A fast convergent method of iterated regularization

zbMATH Keywords

dualityaccelerationforward-backward splittingiterative regularizationstability and convergence analysisdiagonal methods

Mathematics Subject Classification ID

Convex programming (90C25) Linear programming (90C05) Computing methodologies for image processing (68U10) Inverse problems in optimal control (49N45) Duality theory (optimization) (49N15)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Probing the Pareto frontier for basis pursuit solutions
• Nonlinear total variation based noise removal algorithms
• Estimation of the mean of a multivariate normal distribution
• Regularization and Variable Selection Via the Elastic Net
• Model Selection and Estimation in Regression with Grouped Variables
• Introductory lectures on convex optimization. A basic course.
• Support Vector Machines
• Mirror descent and nonlinear projected subgradient methods for convex optimization.
• Signal Recovery by Proximal Forward-Backward Splitting
• Image recovery via total variation minimization and related problems
• Accelerated and inexact forward-backward algorithms
• Title not available (Why is that?)
• First-order methods of smooth convex optimization with inexact oracle
• Title not available (Why is that?)
• Stein Unbiased GrAdient estimator of the Risk (SUGAR) for Multiple Parameter Selection
• Total generalized variation
• Iterative regularization methods for nonlinear ill-posed problems
• On the Minimizing Property of a Second Order Dissipative System in Hilbert Spaces
• Title not available (Why is that?)
• Convergence rates for an iteratively regularized Newton-Landweber iteration in Banach space
• Viscosity Solutions of Minimization Problems
• A dynamical approach to an inertial forward-backward algorithm for convex minimization
• Coupling Forward-Backward with Penalty Schemes and Parallel Splitting for Constrained Variational Inequalities
• A guide to the TV zoo
• Convex analysis and monotone operator theory in Hilbert spaces
• Iterative methods for nonlinear ill-posed problems in Banach spaces: convergence and applications to parameter identification problems
• Iterative total variation schemes for nonlinear inverse problems
• Inexact and accelerated proximal point algorithms
• A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
• On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
• Asymptotic behavior of coupled dynamical systems with multiscale aspects
• Error estimation for Bregman iterations and inverse scale space methods in image restoration
• Level-set methods for convex optimization
• A dynamical approach to convex minimization coupling approximation with the steepest descent method
• Convergence of diagonally stationary sequences in convex optimization
• Inertial forward-backward algorithms with perturbations: application to Tikhonov regularization
• Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity
• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than \(1/k^2\)
• Asymptotic behavior of nonautonomous monotone and subgradient evolution equations
• Asymptotic behavior of gradient-like dynamical systems involving inertia and multiscale aspects
• Preconditioned iterative regularization in Banach spaces
• A fast dual proximal gradient algorithm for convex minimization and applications
• Combining fast inertial dynamics for convex optimization with Tikhonov regularization
• Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3
• Asymptotics for some vibro-impact problems with a linear dissipation term
• On Nesterov acceleration for Landweber iteration of linear ill-posed problems
• Iterative regularization via dual diagonal descent
• Subspace correction methods for a class of nonsmooth and nonadditive convex variational problems with mixed \(L^1/L^2\) data-fidelity in image processing
• Infimal convolution of data discrepancies for mixed noise removal
• Iterative regularization with a general penalty term-theory and application to \(L^{1}\) and \(TV\) regularization
• Splitting forward-backward penalty scheme for constrained variational problems
• Stability of over-relaxations for the forward-backward algorithm, application to FISTA
• The Differential Inclusion Modeling FISTA Algorithm and Optimality of Convergence Rate in the Case b $\leq3$
• Convergence rate of inertial forward-backward algorithm beyond Nesterov's rule
• Modern regularization methods for inverse problems
• Error estimates for general fidelities

Cited In (9)

• Fast iterative regularization by reusing data
• Implicit regularization with strongly convex bias: Stability and acceleration
• Irregularization accelerates iterative regularization
• A new accelerated algorithm for ill-conditioned ridge regression problems
• Accelerated gradient methods combining Tikhonov regularization with geometric damping driven by the Hessian
• Parameter-free FISTA by adaptive restart and backtracking
• Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry
• Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
• Iterative regularization via dual diagonal descent

Uses Software

• SPGL1

This page was built for publication: Accelerated iterative regularization via dual diagonal descent

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