On the linear convergence rates of exchange and continuous methods for total variation minimization

DOI10.1007/S10107-020-01530-0zbMATH Open1475.49032arXiv1906.09919OpenAlexW3035792190MaRDI QIDQ2235147FDOQ2235147

Authors: Axel Flinth, Frédéric De Gournay, Pierre Weiss 

Publication date: 20 October 2021

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: We analyze an exchange algorithm for the numerical solution total-variation regularized inverse problems over the space M($Omega$) of Radon measures on a subset $Omega$ of R d. Our main result states that under some regularity conditions, the method eventually converges linearly. Additionally, we prove that continuously optimizing the amplitudes of positions of the target measure will succeed at a linear rate with a good initialization. Finally, we propose to combine the two approaches into an alternating method and discuss the comparative advantages of this approach.

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

Recommendations

• Linearized primal-dual methods for linear inverse problems with total variation regularization and finite element discretization
• Linear convergence analysis of the use of gradient projection methods on total variation problems
• A note on convergence of solutions of total variation regularized linear inverse problems
• A New Alternating Minimization Algorithm for Total Variation Image Reconstruction
• An algorithm for total variation regularization in high-dimensional linear problems

zbMATH Keywords

inverse problemssemi-infinite programmingsuperresolutiontotal variation minimization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Discrete approximations in optimal control (49M25) Numerical methods involving duality (49M29) Semi-infinite programming (90C34)

Cites Work

• Title not available (Why is that?)
• Gradient methods for minimizing composite functions
• Title not available (Why is that?)
• Partially finite convex programming. I: Quasi relative interiors and duality theory
• Title not available (Why is that?)
• Semi-Infinite Programming: Theory, Methods, and Applications
• Title not available (Why is that?)
• Title not available (Why is that?)
• Atomic decomposition by basis pursuit
• Title not available (Why is that?)
• Towards a Mathematical Theory of Super‐resolution
• Exact reconstruction using Beurling minimal extrapolation
• Compressed Sensing Off the Grid
• Exact support recovery for sparse spikes deconvolution
• Modifications of the First Remez Algorithm
• Exact Solutions to Super Resolution on Semi-Algebraic Domains in Higher Dimensions
• Inverse problems in spaces of measures
• On Representer Theorems and Convex Regularization
• The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems
• The basins of attraction of the global minimizers of the non-convex sparse spike estimation problem
• The sliding Frank–Wolfe algorithm and its application to super-resolution microscopy
• Exact solutions of infinite dimensional total-variation regularized problems
• Spline solutions to L\(^1\) extremal problems in one and several variables
• Title not available (Why is that?)
• Splines Are Universal Solutions of Linear Inverse Problems with Generalized TV Regularization
• Linear convergence of accelerated conditional gradient algorithms in spaces of measures
• Sampling the Fourier Transform Along Radial Lines
• Sparse Inverse Problems over Measures: Equivalence of the Conditional Gradient and Exchange Methods

Cited In (15)

• Sparsest piecewise-linear regression of one-dimensional data
• A generalized conditional gradient method for dynamic inverse problems with optimal transport regularization
• TV-based spline reconstruction with Fourier measurements: uniqueness and convergence of grid-based methods
• Proximal methods for point source localisation
• Nonconvex regularization for sparse neural networks
• On the uniqueness of solutions for the basis pursuit in the continuum
• Explicit representations for Banach subspaces of Lizorkin distributions
• Super-resolution of positive sources on an arbitrarily fine grid
• Localization of point scatterers via sparse optimization on measures
• Linear convergence analysis of the use of gradient projection methods on total variation problems
• TV-based reconstruction of periodic functions
• Title not available (Why is that?)
• Sparse optimization on measures with over-parameterized gradient descent
• Dynamical programming for off-the-grid dynamic inverse problems
• Asymptotic linear convergence of fully-corrective generalized conditional gradient methods

This page was built for publication: On the linear convergence rates of exchange and continuous methods for total variation minimization

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