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!
|
| _version_ | 1866910502806880256 |
|---|---|
| author | Alimisis, Foivos Vary, Simon Vandereycken, Bart |
| author_facet | Alimisis, Foivos Vary, Simon Vandereycken, Bart |
| 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_18433 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Nesterov-style Accelerated Gradient Descent Algorithm for the Symmetric Eigenvalue Problem Alimisis, Foivos Vary, Simon Vandereycken, Bart Optimization and Control 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. |
| title | A Nesterov-style Accelerated Gradient Descent Algorithm for the Symmetric Eigenvalue Problem |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2406.18433 |