Efficient coordinate-wise leading eigenvector computation

Jialei Wang, Weiran Wang, Dan Garber, Nathan Srebro
Proceedings of Algorithmic Learning Theory, PMLR 83:806-820, 2018.

Abstract

We develop and analyze efficient "coordinate-wise" methods for finding the leading eigenvector, where each step involves only a vector-vector product. We establish global convergence with overall runtime guarantees that are at least as good as Lanczos’s method and dominate it for slowly decaying spectrum. Our methods are based on combining a shift-and-invert approach with coordinate-wise algorithms for linear regression.

Cite this Paper

BibTeX
@InProceedings{pmlr-v83-wang18a, title = {Efficient coordinate-wise leading eigenvector computation}, author = {Wang, Jialei and Wang, Weiran and Garber, Dan and Srebro, Nathan}, booktitle = {Proceedings of Algorithmic Learning Theory}, pages = {806--820}, year = {2018}, editor = {Janoos, Firdaus and Mohri, Mehryar and Sridharan, Karthik}, volume = {83}, series = {Proceedings of Machine Learning Research}, month = {07--09 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v83/wang18a/wang18a.pdf}, url = {https://proceedings.mlr.press/v83/wang18a.html}, abstract = {We develop and analyze efficient "coordinate-wise" methods for finding the leading eigenvector, where each step involves only a vector-vector product. We establish global convergence with overall runtime guarantees that are at least as good as Lanczos’s method and dominate it for slowly decaying spectrum. Our methods are based on combining a shift-and-invert approach with coordinate-wise algorithms for linear regression.} }
Endnote
%0 Conference Paper %T Efficient coordinate-wise leading eigenvector computation %A Jialei Wang %A Weiran Wang %A Dan Garber %A Nathan Srebro %B Proceedings of Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Firdaus Janoos %E Mehryar Mohri %E Karthik Sridharan %F pmlr-v83-wang18a %I PMLR %P 806--820 %U https://proceedings.mlr.press/v83/wang18a.html %V 83 %X We develop and analyze efficient "coordinate-wise" methods for finding the leading eigenvector, where each step involves only a vector-vector product. We establish global convergence with overall runtime guarantees that are at least as good as Lanczos’s method and dominate it for slowly decaying spectrum. Our methods are based on combining a shift-and-invert approach with coordinate-wise algorithms for linear regression.
APA
Wang, J., Wang, W., Garber, D. & Srebro, N.. (2018). Efficient coordinate-wise leading eigenvector computation. Proceedings of Algorithmic Learning Theory, in Proceedings of Machine Learning Research 83:806-820 Available from https://proceedings.mlr.press/v83/wang18a.html.

Related Material