Efficient Coordinate-Wise Leading Eigenvector Computation
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
Text
Wang et al. "Efficient Coordinate-Wise Leading Eigenvector Computation." Proceedings of Algorithmic Learning Theory, 2018.Markdown
[Wang et al. "Efficient Coordinate-Wise Leading Eigenvector Computation." Proceedings of Algorithmic Learning Theory, 2018.](https://mlanthology.org/alt/2018/wang2018alt-efficient/)BibTeX
@inproceedings{wang2018alt-efficient,
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},
year = {2018},
pages = {806-820},
volume = {83},
url = {https://mlanthology.org/alt/2018/wang2018alt-efficient/}
}