用切比雪夫多项式加速流形平均,计算更快精度更高。
Rapid Grassmannian Averaging with Chebyshev Polynomials
- 利用谱结构和小矩阵运算实现快速平均
- 在最小时间内达到高精度,优于现有方法
- 适合需要高效流形计算的机器学习与视觉任务
我们提出两种新算法,用于在集中式和去中心化设置下高效平均流形上的点。流形点广泛用于机器学习、计算机视觉和信号处理中,通过子空间表示数据(通常为低维)。虽然平均这些点对许多任务至关重要(尤其在去中心化场景),但现有方法因流形的非欧几何特性而计算成本高昂。所提算法RGrAv和DRGrAv通过利用问题的谱结构,仅需少量矩阵乘法和QR分解即可快速计算平均值。我们提供了最优性理论保证,并通过数值实验表明,算法在极短时间内提供高精度解,显著优于当前最优方法。额外实验展示了算法在视频运动数据聚类等任务中的通用性,确立了RGrAv与DRGrAv作为通用流形平均的强大工具。
原文摘要 · Abstract (English)
We propose new algorithms to efficiently average a collection of points on a Grassmannian manifold in both the centralized and decentralized settings. Grassmannian points are used ubiquitously in machine learning, computer vision, and signal processing to represent data through (often low-dimensional) subspaces. While averaging these points is crucial to many tasks (especially in the decentralized setting), existing methods unfortunately remain computationally expensive due to the non-Euclidean geometry of the manifold. Our proposed algorithms, Rapid Grassmannian Averaging (RGrAv) and Decentralized Rapid Grassmannian Averaging (DRGrAv), overcome this challenge by leveraging the spectral structure of the problem to rapidly compute an average using only small matrix multiplications and QR factorizations. We provide a theoretical guarantee of optimality and present numerical experiments which demonstrate that our algorithms outperform state-of-the-art methods in providing high accuracy solutions in minimal time. Additional experiments showcase the versatility of our algorithms to tasks such as K-means clustering on video motion data, establishing RGrAv and DRGrAv as powerful tools for generic Grassmannian averaging.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。