Coordinate-wise Power Method | Center for Big Data Analytics

Abstract: In this paper, we propose a coordinate-wise version of the power method from an optimization viewpoint. The vanilla power method simultaneously updates all the coordinates of the iterate, which is essential for its convergence analysis. However, different coordinates converge to the optimal value at different speeds. Our proposed algorithm, which we call coordinate-wise power method, is able to select and update the most important k coordinates in O(kn) time at each iteration, where n is the dimension of the matrix and k ≤ n is the size of the active set. Inspired by the “greedy” nature of our method, we further propose a greedy coordinate descent algorithm applied on a non-convex objective function specialized for symmetric matrices. We provide convergence analyses for both methods. Experimental results on both synthetic and real data show that our methods achieve up to 23 times speedup over the basic power method. Meanwhile, due to their coordinate-wise nature, our methods are very suitable for the important case when data cannot fit into memory. Finally, we introduce how the coordinate- wise mechanism could be applied to other iterative methods that are used in machine learning.

Download: pdf, code

Citation

Coordinate-wise Power Method (pdf, software, code)
Q. Lei, K. Zhong, I. Dhillon.
To appear in Neural Information Processing Systems (NIPS), December 2016.

Bibtex:
@inproceedings{lei2016coordinate, author = "Qi Lei AND Kai Zhong AND Inderjit S. Dhillon", title = "Coordinate-wise Power Method", booktitle = "Neural Information Processing Systems (NIPS)", year = "2016", month = "dec", abstract = "In this paper, we propose a coordinate-wise version of the power method from an optimization viewpoint. The vanilla power method simultaneously updates all the coordinates of the iterate, which is essential for its convergence analysis. However, different coordinates converge to the optimal value at different speeds. Our proposed algorithm, which we call coordinate-wise power method, is able to select and update the most important k coordinates in O(kn) time at each iteration, where n is the dimension of the matrix and k ≤ n is the size of the active set. Inspired by the “greedy” nature of our method, we further propose a greedy coordinate descent algorithm applied on a non-convex objective function specialized for symmetric matrices. We provide convergence analyses for both methods. Experimental results on both synthetic and real data show that our methods achieve up to 23 times speedup over the basic power method. Meanwhile, due to their coordinate-wise nature, our methods are very suitable for the important case when data cannot fit into memory. Finally, we introduce how the coordinate- wise mechanism could be applied to other iterative methods that are used in machine learning." }