Efficient Mean Curvature Computation on High-Dimensional Data Manifolds

Problem
Estimating local mean curvature in high-dimensional datasets is crucial for geometry-aware machine learning algorithms, such as the Mean Curvature Boundary Points (MCBP) method. The naive approach, which relies on constructing a local shape operator from k-nearest neighbor patches, incurs a computational cost of $O(m^4)$ per point due to the explicit formation of a matrix $H$. This renders the method impractical for datasets with more than a few dozen features. The authors address this gap by proposing a more efficient computation method, which is particularly relevant as the work is presented as a preprint and has not yet undergone peer review.

Method
The paper introduces two key contributions to reduce the computational burden of mean curvature estimation. The first is an exact algebraic identity that leverages the orthogonality of the eigenvectors of the covariance matrix and the cyclicity of the trace operator. This identity allows for the elimination of the matrix $H$, reducing the per-point cost to $O(m^2)$ after performing eigendecomposition. The second contribution tackles the remaining $O(m^3)$ complexity associated with full eigendecomposition. By recognizing that the local covariance matrix has a rank of at most $k-1 \ll m$, the authors propose using a truncated Singular Value Decomposition (SVD) of the $k \times m$ centered data matrix, which operates at $O(k^2 m)$. They also derive an analytical approximation for the contribution of null-space eigenvectors based on their expected outer product under the Haar measure. The overall computational cost of the proposed estimator is $O(k^2 m + k m p^2)$, where $p = k-1$.

Results
The authors validate their method through experiments on real-world datasets, demonstrating speedups of 50 to 300 times compared to the original naive implementation. Importantly, the fast estimator maintains a negligible loss in accuracy when substituting the original curvature estimation method. These results indicate a significant improvement in computational efficiency while preserving the integrity of the curvature estimates.

Limitations
The authors acknowledge that their method, while efficient, may still be sensitive to the choice of $k$, the number of nearest neighbors, which could affect the quality of the curvature estimates. Additionally, the reliance on SVD may introduce approximation errors, particularly in datasets with high noise levels or outliers. The paper does not address the potential impact of these factors on the generalizability of the method across diverse datasets.

Why it matters
This work establishes a scalable and data-driven approach to estimating local curvature, making it a practical geometric feature for various machine learning applications, from classical algorithms to modern deep learning frameworks. The implications of this research extend to enhancing the performance of geometry-aware models, thereby contributing to the broader field of geometric machine learning. For further details, see the full paper available on arXiv.