We introduce a novel approach to measure the behavior of a geometric operator before and after coarsening.By comparing eigenvectors of the input operator and its coarsened counterpart, we can quantitatively and visually analyze how well the spectral properties of the operator are maintained. Using this measure, we show that standard mesh simplification and algebraic coarsening techniques fail to maintain spectral properties. In response, we introduce a novel approach for spectral coarsening. We show that it is possible to significantly reduce the sampling density of an operator derived from a 3D shape without affecting the low-frequency eigenvectors. By marrying techniques developed within the algebraic multigrid and the functional maps literatures, we successfully coarsen a variety of isotropic and anisotropic operators while maintaining sparsity and positive semi-definiteness. We demonstrate the utility of this approach for applications including operator-sensitive sampling, shape matching, and graph pooling for convolutional neural networks.
@article{Liu:SpectralCoarsen:2019,
title = {Spectral Coarsening of Geometric Operators},
author = {Hsueh-Ti Derek Liu and Alec Jacobson and Maks Ovsjanikov},
year = {2019},
journal = {ACM Transactions on Graphics},
}
This work is funded in part by by a Google Focused Research Award, KAUST OSR Award (OSR-CRG2017–3426), ERC Starting Grant No. 758800 (EXPROTEA), NSERC Discovery Grants (RGPIN2017–05235), NSERC DAS (RGPAS–2017–507938), the Canada Research Chairs Program, Fields Institute CQAM Labs, Mitacs Globalink, and gifts from Autodesk, Adobe, MESH, and NVIDIA Corporation. We thank members of Dynamic Graphics Project at the University of Toronto and STREAM group at the École Polytechnique for discussions and draft reviews; Eitan Grinspun, Etienne Corman, Jean-Michel Roufosse, Maxime Kirgo, and Silvia Sellán for proofreading; Ahmad Nasikun, Desai Chen, Dingzeyu Li, Gavin Barill, Jing Ren, and Ruqi Huang for sharing implementations and results; Zih-Yin Chen for early discussions.