Classification and image processing with a semi‐discrete scheme for fidelity forced Allen–Cahn on graphs. Issue 1 (17th March 2021)

• Record Type: Journal Article
• Authors: Budd, Jeremy; van Gennip, Yves; Latz, Jonas
• Other Names: Benner Peter guestEditor.; Klawonn Axel guestEditor.; Stoll Martin guestEditor.
• Is Part Of: Mitteilungen der Gesellschaft für Angewandte Mathematik und Mechanik. Volume 44:Issue 1(2021)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2021-03-17
• Subjects: Allen‐Cahn equation -- fidelity constraint -- graph dynamics -- Nyström extension -- Strang formula -- threshold dynamics; Mathematics -- Periodicals; Mechanics, Applied -- Periodicals; 510.5
• DOI: 10.1002/gamm.202100004
• Languages: English
• ISSNs: 0936-7195

Abstract

Abstract: This paper introduces a semi‐discrete implicit Euler (SDIE) scheme for the Allen‐Cahn equation (ACE) with fidelity forcing on graphs. The continuous‐in‐time version of this differential equation was pioneered by Bertozzi and Flenner in 2012 as a method for graph classification problems, such as semi‐supervised learning and image segmentation. In 2013, Merkurjev et. al. used a Merriman‐Bence‐Osher (MBO) scheme with fidelity forcing instead, as heuristically it was expected to give similar results to the ACE. The current paper rigorously establishes the graph MBO scheme with fidelity forcing as a special case of an SDIE scheme for the graph ACE with fidelity forcing. This connection requires the use of the double‐obstacle potential in the ACE, as was already demonstrated by Budd and Van Gennip in 2020 in the context of ACE without a fidelity forcing term. We also prove that solutions of the SDIE scheme converge to solutions of the graph ACE with fidelity forcing as the discrete time step converges to zero. In the second part of the paper we develop the SDIE scheme as a classification algorithm. We also introduce some innovations into the algorithms for the SDIE and MBO schemes. For large graphs, we use a QR decomposition method to compute an eigendecomposition from a Nyström extension, which outperforms the method used by, for example, Bertozzi and Flenner in 2012, in accuracy, stability, and speed. Moreover, we replace the Euler discretization for the scheme's diffusion step by a computation based on the Strang formula for matrix exponentials. We apply this algorithm to a number of image segmentation problems, and compare the performance with that of the graph MBO scheme with fidelity forcing. We find that while the general SDIE scheme does not perform better than the MBO special case at this task, our other innovations lead to a significantly better segmentation than that from previous literature. We also empirically quantify the uncertainty that this segmentation inherits from the randomness in the Nyström extension.