# Rapid Grassmannian Averaging with Chebyshev Polynomials

arXiv: https://arxiv.org/abs/2410.08956 · HTML: https://mlsanity.com/paper/2410.08956/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 56 references that are in the map.
- First posted on arXiv 11 Oct 2024.

## Builds on (most cited first, 14 of 14)

- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challenges](https://mlsanity.com/paper/2211.08413/) (2022)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [Decentralized Federated Averaging](https://mlsanity.com/paper/2104.11375/) (2021)
- [Building Deep Networks on Grassmann Manifolds](https://mlsanity.com/paper/1611.05742/) (2016)
- [Decentralized Riemannian Gradient Descent on the Stiefel Manifold](https://mlsanity.com/paper/2102.07091/) (2021)
- [DeEPCA: Decentralized Exact PCA with Linear Convergence Rate](https://mlsanity.com/paper/2102.03990/) (2021)
- [Dictionary Learning and Sparse Coding on Grassmann Manifolds: An Extrinsic Solution](https://mlsanity.com/paper/1310.4891/) (2013)
- [Decentralized projected Riemannian gradient method for smooth optimization on compact submanifolds](https://mlsanity.com/paper/2304.08241/) (2023)
- [A Linearly Convergent Algorithm for Distributed Principal Component Analysis](https://mlsanity.com/paper/2101.01300/) (2021)
- [Decentralized Riemannian Conjugate Gradient Method on the Stiefel Manifold](https://mlsanity.com/paper/2308.10547/) (2023)
- [Scalable and Privacy-Preserving Federated Principal Component Analysis](https://mlsanity.com/paper/2304.00129/) (2023)
- [Distributed Principal Subspace Analysis for Partitioned Big Data: Algorithms, Analysis, and Implementation](https://mlsanity.com/paper/2103.06406/) (2021)
- [Huber means on Riemannian manifolds](https://mlsanity.com/paper/2407.15764/) (2024)

## Abstract (arXiv)

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.