Faster Eigenvector Computation via Shift-and-Invert Preconditioning
Dan Garber Toyota Technological Institute at Chicago Elad Hazan Princeton University Chi Jin UC Berkeley Sham M. Kakade University of Washington Cameron Musco MIT Praneeth Netrapalli Microsoft Research, New England Aaron Sidford Microsoft Research, New England
Abstract
We give faster algorithms and improved sample complexities for estimating the top eigenvector of a matrix $\mathbf{\Sigma}$ – i.e. computing a unit vector $x$ such that $x^{\top}\mathbf{\Sigma}x\geq(1-\epsilon)\lambda_{1}(\mathbf{\Sigma})$ :
中文速览
计算矩阵最大特征向量是主成分分析、谱聚类等众多算法的核心步骤，但当矩阵规模很大、特征值间隔（gap）很小时，经典的幂迭代法和 Lanczos 方法速度很慢，因为它们的运行时间是数据规模与 gap 倒数的乘积。本文提出了一种基于"平移求逆预条件"（shift-and-invert preconditioning）与随机方差缩减梯度（SVRG）的统一算法框架：先把特征向量计算转化为求解一系列条件数可控的线性方程组，再用高效的随机优化方法求解这些方程组，从而在理论上首次将数据规模项与 gap 相关项"解耦"，离线场景下的运行时间优于此前所有方法，在线/流式场景下也获得了更低的样本复杂度，对某些常用模型甚至达到渐近最优。这项工作不仅推进了特征值计算的理论上界，还表明成熟的线性求解库可以直接被复用来加速特征向量计算，具有重要的实践指导价值。
原文 arXiv:1605.08754;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1605.08754v1