Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper addresses the computational inefficiency of estimating local mean curvature in high-dimensional datasets, which is crucial for geometry-aware machine learning algorithms. By deriving an exact algebraic identity that eliminates the need for an explicit matrix construction and utilizing a truncated SVD to handle the covariance matrix, the authors reduce the computational cost from $O(m^4)$ to $O(k^2 m + k m p^2)$. Experimental results demonstrate significant speedups of 50 to 300 times compared to traditional methods, with minimal loss in accuracy, making curvature estimation feasible for a wide range of machine learning applications.
Achieving 50 to 300 times faster mean curvature estimation could revolutionize geometry-aware machine learning by making it practical for high-dimensional data.
Estimating local mean curvature at each point of a high-dimensional dataset is a key ingredient of geometry-aware machine learning algorithms, such as the Mean Curvature Boundary Points (MCBP) method. The naive implementation of this computation, based on a local shape operator approximated from k-nearest neighbor patches, involves an explicit construction of a matrix $H$ whose trace form yields an $O(m^4)$ cost per point, rendering the approach intractable for datasets with more than a few dozen features. This paper introduces two complementary contributions that together reduce this cost by several orders of magnitude. The first contribution is an exact algebraic identity. This identity, derived from the orthogonality of the eigenvectors of the covariance matrix and the cyclicity of the trace operator, eliminates $H$ entirely and reduces the per-point cost to $O(m^2)$ after the eigendecomposition. The second contribution addresses the remaining $O(m^3)$ bottleneck of the full eigendecomposition. Since the local covariance matrix has rank at most $k-1 \ll m$, we replace it with a truncated SVD of the $k \times m$ centered data matrix, an $O(k^2 m)$ operation, and derive an analytical approximation for the contribution of the null-space eigenvectors based on the expected value of their outer product under the Haar measure. The resulting estimator has total cost $O(k^2 m + k m p^2)$, where $p = k-1$. Experiments on real-world datasets confirm speedups of 50 to 300 times relative to the original implementation, with negligible loss when the fast estimator is used to replace the original version. By providing a scalable and data-driven estimate of local curvature, the proposed method establishes curvature as a practical geometric feature for a broad range of machine learning tasks, from classical to modern deep learning pipelines.