Accession Number:

AD1014925

Title:

Convergence Analysis of the Graph Allen-Cahn Scheme

Descriptive Note:

Technical Report

Corporate Author:

University of California Los Angeles Los Angeles United States

Personal Author(s):

Report Date:

2016-02-01

Pagination or Media Count:

23.0

Abstract:

Graph partitioning problems have a wide range of applications in machine learning. This work analyzes convergence conditions for a class of diffuse interface algorithm A.L. Bertozziand A. Flenner, Multiscale Modeling and Simulation, 1031090 1118, 2012 for binary and multi-class partitioning. Using techniques from numerical PDE and convex optimization, convergence and monotonicity are shown for a class of schemes under a graph-independent timestep restriction. We also analyze the effects of spectral truncation, a common technique used to save computational cost. Convergence of the scheme with spectral truncation is also proved under a timestep restriction inversely proportional to the size of the graph. Moreover, this restriction is shown to be sharp in a worst case. Various numerical experiments are done to compare theoretical results with practical performance.

Subject Categories:

  • Operations Research
  • Cybernetics
  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE