Welcome to the homepage of the

Mathematical Optimization for Data Science Group

Department of Mathematics and Computer Science, Saarland University, Germany

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. [pdf]
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}
}


MOP Group
©2017-2024
The author is not
responsible for
the content of
external pages.