A Practical Riemannian Algorithm for Computing Dominant Generalized Eigenspace
Abstract
Dominant generalized eigenspace computation, concerned with how to find one of the top-k generalized eigenspaces of a pair of real symmetric matrices, is one of the fundamental problems in scientific computing, data analysis, and statistics. In this work, we propose a practical Riemannian algorithm based on the first-order optimization on generalized Stiefel manifolds while efficiently leveraging second-order information. Particularly, we use inexact Riemannian gradients which result from running a fast least-squares solver to approximate matrix multiplications for avoiding costly matrix inversions involved therein. We also conduct a theoretical analysis that is different than existing ones, achieving a unified linear convergence rate regardless of the conventional generalized eigenvalue gap which is the key parameter to the currently dichotomized analysis: gap-dependent or gap-free. The resulting linear rate, albeit not optimal, remains valid in full generality. Despite the simplicity, empirically, our algorithm as a block generalized eigensolver remarkably outperforms existing solvers.
BibTeX
@InProceedings{pmlr-v124-xu20a,
title = {A Practical Riemannian Algorithm for Computing Dominant Generalized Eigenspace},
author = {Xu, Zhiqiang and Li, Ping},
booktitle = {Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI)},
pages = {819--828},
year = {2020},
editor = {Peters, Jonas and Sontag, David},
volume = {124},
series = {Proceedings of Machine Learning Research},
month = {03--06 Aug},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v124/xu20a/xu20a.pdf},
url = {https://proceedings.mlr.press/v124/xu20a.html},
abstract = {Dominant generalized eigenspace computation, concerned with how to find one of the top-k generalized eigenspaces of a pair of real symmetric matrices, is one of the fundamental problems in scientific computing, data analysis, and statistics. In this work, we propose a practical Riemannian algorithm based on the first-order optimization on generalized Stiefel manifolds while efficiently leveraging second-order information. Particularly, we use inexact Riemannian gradients which result from running a fast least-squares solver to approximate matrix multiplications for avoiding costly matrix inversions involved therein. We also conduct a theoretical analysis that is different than existing ones, achieving a unified linear convergence rate regardless of the conventional generalized eigenvalue gap which is the key parameter to the currently dichotomized analysis: gap-dependent or gap-free. The resulting linear rate, albeit not optimal, remains valid in full generality. Despite the simplicity, empirically, our algorithm as a block generalized eigensolver remarkably outperforms existing solvers.}
}