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

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.