Coordinate-wise Power Method
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 coordinatewise mechanism could be applied to other iterative methods that are used in machine learning.
A coordinate descent method of the power method is proposed with convergence analysis. An even faster algorithm based on greedy coordinate descent is proposed. Empirical results suggest that the proposed method is fast in practice compared to the baseline or vanilla power method. The authors show that the algorithms proposed have a local linear convergence.
Overall I enjoyed reading the paper, it is well written and flows well with the intuition for the algorithms clearly written in the main paper which is helpful. However I am not sure how the comparison is fair: the convergence analysis only applies to the problem of computing eigenvectors. If this is the case, it is important to compare with recent algorithms that compute the same, comparing just with the vanilla power method does not say much about usefulness of the proposed algorithms, many state-of-the-art algorithms are often randomized/parallelized see for example [1], [2], [3] (I am not familiar with recent papers in SIAM, Matrix analysis, Numerical Linear Algebra but these seem like good baselines to compare with). A discussion of how the proposed algorithms can or cannot be parallelized WITH convergence would greatly enhance the utility.   The authors claim that their method is useful when the entire matrix cannot fit in the memory but is not made concrete: usually in this scenario, communication costs become significant see [4].  Finally, local convergence is already known, see [5] although showing that the function is strongly convex is still a valid contribution.  1. A Parallel Eigensolver for Dense Symmetric Matrices based on Multiple Relatively Robust Representations (2005) by P. Bientinesi, I. S. Dhillon, and R. A. van de Geijn;   2. Finding Structure With Randomness: Probabilistic Algorithms For Constructing Approximate Matrix Decompositions (2010) by N. Halko, P. G. Martinsson AND J. A. Tropp.    3. An Algorithm for the Principal Component Analysis of large Data Sets (2011) by N. Halko, P.G. Martinsson, Y. Shkolnisky, M. Tygert.  4. Communication-Avoiding Krylov Subspace Methods in Theory and Practice (2015) PhD Thesis by  Erin Carson, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-179.html}  5. Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection (ICML 2015) by Julie Nutini, Mark Schmidt, Issam Laradji, Michael Friedlander, Hoyt Koepke