arXiv:2606.06329cs.LGcs.CG2026-06

高效计算高维数据流形的局部平均曲率,速度提升百倍以上。

Efficient Mean Curvature Computation on High-Dimensional Data Manifolds

论文配图:Efficient Mean Curvature Computation on High-Dimensional Data Manifolds
图 1 · 摘自论文原文
  • 利用矩阵迹的代数恒等式,避免显式构造矩阵H,降为O(m²)复杂度。
  • 用截断SVD替代全谱分解,将瓶颈降至O(k²m),总复杂度为O(k²m + km p²)。
  • 在真实数据集上提速50-300倍,适合大规模几何感知机器学习任务。

在高维数据集中估计每个点的局部平均曲率,是几何感知机器学习算法(如均曲率边界点方法)的关键步骤。传统方法基于k近邻邻域的局部形状算子,需显式构建矩阵H,其迹计算复杂度达O(m⁴),在特征维度超过几十时难以应用。本文提出两项互补改进:第一,基于协方差矩阵特征向量正交性与迹的循环性质,导出精确代数恒等式,彻底消除矩阵H,使每点计算降至O(m²);第二,针对全谱分解的O(m³)瓶颈,由于局部协方差矩阵秩至多为k−1≪m,改用中心化数据矩阵的截断SVD(复杂度O(k²m)),并基于哈尔测度下零空间特征向量外积的期望值,推导其贡献的解析近似。最终估计算法总复杂度为O(k²m + km p²),其中p = k−1。在真实数据集上的实验表明,相较原始实现提速50至300倍,替换后误差可忽略。该方法为大规模机器学习提供了可扩展且数据驱动的局部曲率估计,使曲率成为从经典到现代深度学习流程中实用的几何特征。

原文摘要 · Abstract (English)

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.

曲率计算高维数据机器学习算法优化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。