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

D. Hafner, Peter Ochs, J. Weickert, M. Reißel, S. Grewenig
German Conference on Pattern Recognition (GCPR), Springer, LNCS, Vol.9796: 91--102, 2016
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.
Publisher's link

Other associated files : hafner-gcpr16.pdf [1MB]  

Images and movies


BibTex reference

  author       = "D. Hafner and P. Ochs and J. Weickert and M. Reißel and S. Grewenig",
  title        = "FSI schemes: Fast semi-iterative solvers for PDEs and Optimisation Methods",
  booktitle    = "German Conference on Pattern Recognition (GCPR)",
  series       = "Lecture Notes in Computer Science",
  volume       = "9796",
  pages        = "91--102",
  month        = " ",
  year         = "2016",
  editor       = "B. Andres, B. Rosenhahn",
  publisher    = "Springer",
  note         = "Awarded the GCPR 2016 Best Paper Award",
  url          = "http://lmb.informatik.uni-freiburg.de/Publications/2016/Och16"

Other publications in the database