Sub-sampling for Efficient Spectral Mesh Processing

This paper relates Nystrom method to Kernel Principal Component Analysis (KPCA), and derives a novel measure in the form of a matrix trace, based soly on sampled data, to quantify the quality of Nystrom approximation.

Abstract

In this paper, we apply Nyström method, a sub-sampling and reconstruction technique, to speed up spectral mesh processing. We first relate this method to Kernel Principal Component Analysis (KPCA). This enables us to derive a novel measure in the form of a matrix trace, based soly on sampled data, to quantify the quality of Nyström approximation. The measure is efficient to compute, well-grounded in the context of KPCA, and leads directly to a greedy sampling scheme via trace maximization. On the other hand, analyses show that it also motivates the use of the max-min farthest point sampling, which is a more efficient alternative. We demonstrate the effectiveness of Nyström method with farthest point sampling, compared with random sampling, using two applications: mesh segmentation and mesh correspondence.