FSI Schemes: Fast Semi-Iterative Solvers for PDEs and Optimisation Methods

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9796
• 期：1
• 页码：91-102
• 全文大小：1,368 KB
• 参考文献：1.Acar, R., Vogel, C.R.: Analysis of bounded variation penalty methods for ill-posed problems. Inverse Prob. 10, 1217–1229 (1994)MathSciNet CrossRef MATH
  2.Bertero, M., Poggio, T.A., Torre, V.: Ill-posed problems in early vision. Proc. IEEE 76(8), 869–889 (1988)CrossRef
  3.Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20(1), 89–97 (2004)MathSciNet
  4.Gentzsch, W., Schlüter, A.: Über ein Einschrittverfahren mit zyklischer Schrittweitenänderung zur Lösung parabolischer Differentialgleichungen. Zeitschrift für Angewandte Mathematik und Mechanik 58, T415–T416 (1978). in GermanMATH
  5.Golub, G.H., Varga, R.S.: Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methods. Part I. Numerische Mathematik 3(1), 147–156 (1961)MathSciNet CrossRef MATH
  6.Hellwig, G.: Partial Differential Equations. Teubner, Stuttgart (1977)MATH
  7.van der Houwen, P.J., Sommeijer, B.P.: On the internal stability of explicit, m-stage Runge-Kutta methods for large m-values. Zeitschrift für Angewandte Mathematik und Mechanik 60(10), 479–485 (1980)MathSciNet CrossRef MATH
  8.Iijima, T.: Basic theory on normalization of pattern (in case of typical one-dimensional pattern). Bull. Electrotech. Lab. 26, 368–388 (1962). in Japanese
  9.Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course, Applied Optimization, vol. 87. Kluwer, Boston (2004)MATH
  10.Ochs, P., Brox, T., Pock, T.: iPiasco: inertial proximal algorithm for strongly convex optimization. J. Math. Imaging Vis. 53(2), 171–181 (2015)MathSciNet CrossRef MATH
  11.Perona, P., Malik, J.: Scale space and edge detection using anisotropic diffusion. IEEE Trans. Pattern Anal. Mach. Intell. 12(7), 629–639 (1990)CrossRef
  12.Polyak, B.T.: Some methods of speeding up the convergence of iteration methods. USSR Comput. Math. Math. Phys. 4(5), 1–17 (1964)CrossRef
  13.Richardson, L.F.: The approximate arithmetical solution by finite differences of physical problems involving differential equation, with an application to the stresses in a masonry dam. Philos. Trans. R. Soc. A 210, 307–357 (1911)CrossRef MATH
  14.Rudin, L.I., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259–268 (1992)MathSciNet CrossRef MATH
  15.Rumelhart, D.E., Hinton, G.E., Williams, R.J.: Learning internal representations by error propagation, chap. 8. In: Rumelhart, D.E., McClelland, J.L. (eds.) Parallel Distributed Processing: Explorations in the Microstructure of Cognition, vol. 1, pp. 318–362. MIT Press, Cambridge (1986)
  16.Saul’yev, V.K.: Integration of Equations of Parabolic Type by the Method of Nets. Elsevier, Pergamon, Oxford (1964)MATH
  17.Setzer, S., Steidl, G., Morgenthaler, J.: A cyclic projected gradient method. Comput. Optim. Appl. 54(2), 417–440 (2013)MathSciNet CrossRef MATH
  18.Sutskever, I., Martens, J., Dahl, G., Hinton, G.: On the importance of initialization and momentum in deep learning. In: Proceedings of 30th International Conference on Machine Learning, pp. 1139–1147. Atlanta, GA, June 2013
  19.Varga, R.S.: A comparison of the successive overrelaxation method and semi-iterative methods using Chebyshev polynomials. J. Soc. Ind. Appl. Math. 5(2), 39–46 (1957)MathSciNet CrossRef MATH
  20.Weickert, J.: Theoretical foundations of anisotropic diffusion in image processing. Comput. Suppl. 11, 221–236 (1996)CrossRef
  21.Weickert, J.: Anisotropic Diffusion in Image Processing. Teubner, Stuttgart (1998)MATH
  22.Weickert, J., Grewenig, S., Schroers, C., Bruhn, A.: Cyclic schemes for PDE-based image analysis. Int. J. Comput. Vis. 118(3), 275–299 (2016)MathSciNet CrossRef
  23.Wells, W.M.: Efficient synthesis of Gaussian filters by cascaded uniform filters. IEEE Trans. Pattern Anal. Mach. Intell. 8(2), 234–239 (1986)CrossRef
  24.Young, D.M.: On Richardson’s method for solving linear systems with positive definite matrices. J. Math. Phys. 32(1), 243–255 (1954)MATH
  25.Chzhao-Din, Y.: Some difference schemes for the solution of the first boundary value problem for linear differential equations with partial derivatives. Ph.D. thesis, Moscow State University (1958). in Russian
  
• 作者单位：David Hafner (15)
  Peter Ochs (15)
  Joachim Weickert (15)
  Martin Reißel (16)
  Sven Grewenig (15)
  
  15. Mathematical Image Analysis Group, Faculty of Mathematics and Computer Science, Campus E1.7, Saarland University, 66041, Saarbrücken, Germany
  16. Fachbereich Medizintechnik und Technomathematik, Fachhochschule Aachen, Heinrich-Mußmann-Straße 1, 52428, Jülich, Germany
  
• 丛书名：Pattern Recognition
• ISBN：978-3-319-45886-1
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9796

文摘

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.