Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2406.18433 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- We develop an accelerated gradient descent algorithm on the Grassmann manifold to compute the subspace spanned by a number of leading eigenvectors of a symmetric positive semi-definite matrix. This has a constant cost per iteration and a provable iteration complexity of $\tilde{\mathcal{O}}(1/\sqrtδ)$, where $δ$ is the spectral gap and $\tilde{\mathcal{O}}$ hides logarithmic factors. This improves over the $\tilde{\mathcal{O}}(1/δ)$ complexity achieved by subspace iteration and standard gradient descent, in cases that the spectral gap is tiny. It also matches the iteration complexity of the Lanczos method that has however a growing cost per iteration. On the theoretical part, we rely on the formulation of Riemannian accelerated gradient descent by [26] and new characterizations of the geodesic convexity of the symmetric eigenvalue problem by [8]. On the empirical part, we test our algorithm in synthetic and real matrices and compare with other popular methods.