Analysis of the MBO scheme: from materials science to data clustering

Abstract

The Merriman, Bence, and Osher (MBO) scheme -- also known as thresholding scheme -- is a numerical method originally introduced to approximate the evolution by mean curvature flow (MCF). The algorithm produces a time approximation of MCF by iterating the following two steps: (i) convolution with a smooth kernel and (ii) thresholding. <br /> One of the reasons for finding numerical schemes to approximate MCF is that in its multiphase variant, MCF can be used in materials science to model the slow relaxation of grain boundaries in polycrystals. The MBO scheme has been modified in various directions to better approximate the model of grain growth. One of these modifications, due to Esedoglu and Salvador, allows for more freedom in the choice of some parameters used in the model. In the thesis, we give the first rigorous conditional convergence proof of this variant of the algorithm: we show that the approximations produced by the scheme converge to a De Giorgi's solution to multiphase mean curvature flow. <br /> The MBO scheme has been also used as a graph-based learning algorithm by Bertozzi et al. to perform data clustering, which is the task of splitting a given data set into subsets of points similar to each other. In this case, the MBO scheme is used to successively update a clustering to obtain a better split in the data. The algorithm is conceptually the same, with the only modification in the first step, where the convolution with the kernel is replaced by the action of the graph heat operator. In the thesis, we study the large data limit behavior of the algorithm: we show that under the manifold assumption for the data, when the number of sampled points goes to infinity, (i) the final outcome of the scheme approximates a local minimizer of an optimal partition problem on the data manifold; and (ii) in the two-class setting, the dynamics of the MBO scheme converges to a viscosity solution to MCF on the manifold.