Mathematical Optimization for Data Science Group, Saarland University

Welcome to the homepage of the

Mathematical Optimization for Data Science Group

Department of Mathematics and Computer Science, Saarland University, Germany

Home
Teaching
Research
Publications
Job Offers

Saarland
University

Mathematics
and

Computer Science

FSI schemes: Fast semi-iterative solvers for PDEs and Optimisation Methods

D. Hafner, P. Ochs, J. Weickert, M. Reißel and S. Grewenig

Abstract:
Many tasks in image processing and computer vision are modelled by diffusion processes, variational formulations, or constrained optimisation problems. Basic iterative solvers such as explicit schemes, Richardson iterations, or projected gradient descent methods are simple to implement and well-suited for parallel computing. However, their efficiency suffers from severe step size restrictions. As a remedy we introduce a simple and highly efficient acceleration strategy, leading to so-called Fast Semi-Iterative (FSI) schemes that extrapolate the basic solver iteration with the previous iterate. To derive suitable extrapolation parameters, we establish a recursion relation that connects box filtering with an explicit scheme for 1D homogeneous diffusion. FSI schemes avoid the main drawbacks of recent Fast Explicit Diffusion (FED) and Fast Jacobi techniques, and they have an interesting connection to the heavy ball method in optimisation. Our experiments show their benefits for anisotropic diffusion inpainting, nonsmooth regularisation, and Nesterov's worst case problems for convex and strongly convex optimisation.



pdf	Bibtex	Publisher's link

Citation:
D. Hafner, P. Ochs, J. Weickert, M. Reißel, S. Grewenig:
FSI schemes: Fast semi-iterative solvers for PDEs and Optimisation Methods.

In B. Andres, B. Rosenhahn (Eds.): German Conference on Pattern Recognition (GCPR). Lecture Notes in Computer Science, Vol. 9796, 91-102, Springer, 2016. (Best Paper Award)

Bibtex:
@inproceedings{HOWRG16, title = {FSI schemes: Fast semi-iterative solvers for PDEs and Optimisation Methods}, author = {D. Hafner and P. Ochs and J. Weickert and M. Rei\ss{}el and S. Grewenig}, year = {2016}, editor = {B. Andres and B. Rosenhahn}, booktitle = {German Conference on Pattern Recognition (GCPR)}, series = {Lecture Notes in Computer Science}, publisher = {Springer}, volume = {9796}, pages = {91--102} }

Impressum
Datenschutz