Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry
From MaRDI portal
Publication:6284875
DOI10.1007/S10107-022-01809-4arXiv1703.09477MaRDI QIDQ6284875FDOQ6284875
Silvia Villa, Lorenzo Rosasco, Guillaume Garrigos
Publication date: 28 March 2017
Abstract: We provide a comprehensive study of the convergence of the forward-backward algorithm under suitable geometric conditions, such as conditioning or {L}ojasiewicz properties. These geometrical notions are usually local by nature, and may fail to describe the fine geometry of objective functions relevant in inverse problems and signal processing, that have a nice behaviour on manifolds, or sets open with respect to a weak topology. Motivated by this observation, we revisit those geometric notions over arbitrary sets. In turn, this allows us to present several new results as well as collect in a unified view a variety of results scattered in the literature. Our contributions include the analysis of infinite dimensional convex minimization problems, showing the first {L}ojasiewicz inequality for a quadratic function associated to a compact operator, and the derivation of new linear rates for problems arising from inverse problems with low-complexity priors. Our approach allows to establish unexpected connections between geometry and a priori conditions in inverse problems, such as source conditions, or restricted isometry properties.
Numerical optimization and variational techniques (65K10) Convex programming (90C25) Decomposition methods (49M27) Fixed-point iterations (47J26)
This page was built for publication: Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6284875)
