Efficient Mean Curvature Computation on High-Dimensional Data Manifolds

Over the past two decades, the integration of differential geometry into machine learning—termed Geometric Machine Learning—has gained prominence. Foundational works such as Bronstein et al. [2017, 2021] demonstrated that many data structures, from graphs to manifolds, can be better understood through geometric principles like symmetry groups and curvature. The manifold hypothesis [Fefferman et al., 2016] posits that high-dimensional data often lie near low-dimensional, smooth Riemannian manifolds, which has driven the development of manifold learning algorithms like ISOMAP [Tenenbaum et al., 2000], Locally Linear Embedding [Roweis and Saul, 2000], t-SNE [van der Maaten and Hinton, 2008], and UMAP [McInnes et al., 2018]. These methods focus on recovering the intrinsic geometry, but often overlook the estimation of differential geometric quantities such as curvature, which encode richer local shape information.

Estimating local mean curvature is crucial for understanding the geometric irregularities, boundary detection, and shape analysis of data manifolds. Existing approaches typically rely on constructing local shape operators from neighborhood patches, involving high-order tensor computations and full eigenvalue decompositions. These procedures become computationally prohibitive as the ambient dimension increases, limiting their application in modern high-dimensional datasets like image features, genomics, and sensor arrays. Therefore, there is a pressing need for scalable, accurate, and theoretically grounded methods to estimate curvature in high-dimensional settings.

The core challenge addressed in this paper is the high computational complexity associated with local mean curvature estimation on high-dimensional data manifolds. Traditional methods involve constructing a shape operator matrix H, which requires tensor contractions over all pairs of eigenvectors, leading to an O(m^4) cost per point. When combined with eigendecomposition, the total complexity reaches O(m^3), making it infeasible for datasets with hundreds or thousands of features. This computational barrier prevents the widespread adoption of curvature-based features in large-scale machine learning pipelines. Moreover, the high cost limits the ability to perform real-time analysis, impeding applications in dynamic environments such as video processing or streaming sensor data. Addressing this bottleneck is essential for integrating geometric insights into modern data-driven models.

The paper introduces two key innovations. First, an exact algebraic identity is derived that exploits the orthogonality of the covariance matrix eigenvectors and the cyclic property of the trace operator. This identity reformulates the mean curvature estimator, removing the explicit construction of the shape operator matrix H and reducing the complexity from O(m^4) to O(m^3). Second, recognizing that the local covariance matrix in high-dimensional data has low rank (at most p = k - 1), the authors replace full eigenvalue decomposition with a truncated SVD of the centered neighborhood data matrix, which costs only O(k^2 m). To handle the null space eigenvectors, they analytically approximate their contribution using the expected outer product under Haar measure, based on random orthogonal bases. Combining these techniques results in a scalable estimator with total complexity O(k^2 m + k m p^2), enabling efficient curvature estimation in high-dimensional spaces.

• �� Derive an algebraic identity that expresses the mean curvature estimator solely in terms of the covariance matrix C = W⊤W, where W contains the eigenvectors of the local covariance matrix, eliminating the explicit shape operator H.
• �� Exploit the orthogonality of eigenvectors to simplify tensor contractions involving element-wise squares and products, transforming quartic tensor operations into matrix multiplications.
• �� Recognize that the local covariance matrix has rank at most p = k - 1, allowing the replacement of full eigendecomposition with a truncated SVD of the centered neighborhood data matrix Xc, at a computational cost of O(k^2 m).
• �� Derive an analytical approximation for the contribution of the null eigenvectors by calculating the expected outer product of a random orthonormal basis under Haar measure, which models the distribution of eigenvectors in high-dimensional spaces.
• �� Combine the algebraic identity and the null-space approximation to formulate a total estimator with complexity O(k^2 m + k m p^2), suitable for large m and small k.
• �� Validate the approach through systematic experiments on real datasets, comparing computational times, estimation errors, and downstream task performance against baseline methods.

• �� Datasets: The authors evaluate their method on multiple real-world datasets, including high-dimensional image features, gene expression profiles, and sensor data, with ambient dimensions ranging from 50 to 200.
• �� Baselines: Comparisons are made against the original shape operator-based method, which involves constructing H and performing full eigenvalue decompositions, as well as simplified variants.
• �� Metrics: Evaluation includes computational time, accuracy of mean curvature estimates (correlation with ground truth or high-precision estimates), boundary detection precision, and anomaly detection performance.
• �� Hyperparameters: Neighborhood size k varies from 10 to 50, ensuring the low-rank assumption holds. The number of experiments covers different ambient dimensions and neighborhood sizes.
• �� Ablation studies: The impact of the algebraic identity and null-space approximation is isolated to demonstrate their individual contributions to complexity reduction and accuracy preservation.
• �� Results: The proposed method achieves 50-300× speedup, with less than 5% deviation in curvature estimates compared to the exact method. Boundary and anomaly detection tasks show improved precision and recall, confirming the practical benefits of the approach.

• �� The new estimator reduces the computational time from hours to minutes for m=200, k=20, with a speedup factor of approximately 100. The curvature estimates maintain a high correlation (>0.95) with the exact method, indicating negligible loss of fidelity.
• �� In boundary detection experiments, incorporating the estimated curvature improves classification accuracy by up to 8%, demonstrating its utility in identifying geometric transitions.
• �� The ablation analysis confirms that the algebraic identity alone cuts complexity from O(m^4) to O(m^3), while the low-rank SVD approximation further reduces it to near O(k^2 m). The combined approach offers a practical solution for high-dimensional data.
• �� Across different datasets and parameter settings, the method exhibits robust performance, scalability, and consistency, validating its potential for broad adoption in geometric data analysis pipelines.

• �� Boundary detection: Identifying sharp transitions and edges in data manifolds, aiding in clustering, segmentation, and visualization tasks.
• �� Anomaly detection: High-curvature regions often correspond to outliers or unusual data points, useful in fraud detection, network security, and fault diagnosis.
• �� Semi-supervised learning: Selecting boundary points with high curvature for labeling improves classifier robustness, especially in low-label regimes.
• �� Bioinformatics: Analyzing single-cell genomics data to reveal differentiation trajectories, transitional states, and cell-type boundaries.
• �� Graph neural networks: Using local curvature estimates as node or edge features to enhance message passing and community detection.
• �� These applications benefit from the method’s scalability, enabling real-time analysis in large-scale high-dimensional datasets.

• �� The low-rank assumption relies on small neighborhood sizes; larger neighborhoods or noisy data may violate this, reducing estimation accuracy.
• �� The analytical approximation assumes uniform distribution of eigenvectors under Haar measure, which may not hold in structured or non-uniform data, leading to bias.
• �� Handling extremely high-dimensional data (m > 1000) or very large neighborhoods (k > 50) still incurs computational costs, requiring further optimization.
• �� The method primarily targets smooth, low-curvature regions; highly irregular or topologically complex areas may pose challenges for accurate estimation.
• �� Future work should explore adaptive neighborhood selection, robustness to noise, and integration with deep learning frameworks for end-to-end geometric feature learning.