Convergence of the Graph Allen–Cahn SchemeReportar como inadecuado

Convergence of the Graph Allen–Cahn Scheme - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Journal of Statistical Physics

, Volume 167, Issue 3–4, pp 934–958

First Online: 30 March 2017Received: 07 November 2016Accepted: 28 February 2017DOI: 10.1007-s10955-017-1772-4

Cite this article as: Luo, X. & Bertozzi, A.L. J Stat Phys 2017 167: 934. doi:10.1007-s10955-017-1772-4


The graph Laplacian and the graph cut problem are closely related to Markov random fields, and have many applications in clustering and image segmentation. The diffuse interface model is widely used for modeling in material science, and can also be used as a proxy to total variation minimization. In Bertozzi and Flenner Multiscale Model Simul 103:1090–1118, 2012, an algorithm was developed to generalize the diffuse interface model to graphs to solve the graph cut problem. This work analyzes the conditions for the graph diffuse interface algorithm to converge. Using techniques from numerical PDE and convex optimization, monotonicity in function value and convergence under an a posteriori condition are shown for a class of schemes under a graph-independent stepsize condition. We also generalize our results to incorporate spectral truncation, a common technique used to save computation cost, and also to the case of multiclass classification. Various numerical experiments are done to compare theoretical results with practical performance.

KeywordsMachine learning Numerical analysis Diffuse interface methods This paper is dedicated to the memory of Leo P. Kadanoff who was an inspiration to generations of interdisciplinary scientists. Those of us who learned from him will carry the torch to the next generation.

Autor: Xiyang Luo - Andrea L. Bertozzi


Documentos relacionados