PDE-Inspired Algorithms for Semi-Supervised Learning on Point Clouds

Abstract

Given a data set and a subset of labels the problem of semi-supervised learning on point clouds is to extend the labels to the entire data set. In this paper we extend the labels by minimising the constrained discrete $p$-Dirichlet energy. Under suitable conditions the discrete problem can be connected, in the large data limit, with the minimiser of a weighted continuum $p$-Dirichlet energy with the same constraints. We take advantage of this connection by designing numerical schemes that first estimate the density of the data and then apply PDE methods, such as pseudo-spectral methods, to solve the corresponding Euler-Lagrange equation. We prove that our scheme is consistent in the large data limit for two methods of density estimation: kernel density estimation and spline kernel density estimation.

References in corpus (12)

• Adam: A Method for Stochastic Optimization
• On the Convergence of Adam and Beyond
• Consistency of spectral clustering
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Empirical graph Laplacian approximation of Laplace--Beltrami operators: Large sample results
• An improvement of the convergence proof of the ADAM-Optimizer
• Continuum limit of total variation on point clouds
• An Analysis of the Convergence of Graph Laplacians
• Spectral Convergence Rate of Graph Laplacian
• Local Asymptotics of P-splines
• Operator norm convergence of spectral clustering on level sets
• Nonlocal $p$-Laplacian Variational problems on graphs