A Nesterov-style Accelerated Gradient Descent Algorithm for the Symmetric Eigenvalue Problem

2024/06/26 by Alimisis, Foivos, Vary, Simon, Vandereycken, Bart
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2406.18433

Abstract

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 O(1/√δ), where δ is the spectral gap and O hides logarithmic factors. This improves over the 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.

Related

• Gradient-type subspace iteration methods for the symmetric eigenvalue problem
• Geodesic Convexity of the Symmetric Eigenvalue Problem and Convergence of Riemannian Steepest Descent
• Riemannian Acceleration with Preconditioning for symmetric eigenvalue problems
• Low-complexity subspace-descent over symmetric positive definite manifold
• Fast eigenpairs computation with operator adapted wavelets and hierarchical subspace correction