Seminar Details
2022-10-11 (14h) : Geometry of the symmetric eigenvalue problem
At Euler building (room a.002)
Organized by Mathematical Engineering
Speaker :
Foivos Alimisis (Université de Genève)
Abstract :
Eigenvalue problems are some of the most characteristic linear algebra applications of optimization techniques over Riemannian manifolds. These techniques are usually well benefited by the presence of a convexity structure. We study the geodesic convexity structure of the standard problem of computing some of the eigenvectors of a symmetric matrix (Rayleigh quotient) on the sphere and on the Grassmann manifold. We prove that, while the problem is only very locally convex, it satisfies in general weaker convexity properties (weak-quasi-convexity, quadratic growth) that are enough to provide convergence guarantees for many important algorithms. Namely, we prove that gradient descent for the Rayleigh quotient on the Grassmann manifold enjoys a linear convergence rate, while if its step-size is chosen via an exact line search, it empirically outperforms the more popular subspace iteration (power method). We also apply our results in the case of accelerated gradient descent (Nesterov's momentum), which turns out to be particularly beneficial when the gaps between the eigenvalues of the original matrix are small.