Hypergraph $p$-Laplacian regularization on point clouds for data interpolation

As a generalization of graphs, hypergraphs are widely used to model higher-order relations in data. This paper explores the benefit of the hypergraph structure for the interpolation of point cloud data that contain no explicit structural information. We define the \varepsilon_n-ball hypergraph and the k_n-nearest neighbor hypergraph on a point cloud and study the p-Laplacian regularization on the hypergraphs. We prove the variational consistency between the hypergraph p-Laplacian regularization and the continuum p-Laplacian regularization in a semisupervised setting when the number of points n goes to infinity while the number of labeled points remains fixed. A key improvement compared to the graph case is that the results rely on weaker assumptions on the upper bound of \varepsilon_n and k_n. To solve the convex but non-differentiable large-scale optimization problem, we utilize the stochastic primal-dual hybrid gradient algorithm. Numerical experiments on data interpolation verify that the hypergraph p-Laplacian regularization outperforms the graph p-Laplacian regularization in preventing the development of spikes at the labeled points.