Multiplication-Avoiding Variant of Power Iteration with Applications
This addresses energy efficiency and speed in data analysis algorithms like ranking and PCA, though it is incremental as it modifies an existing method.
The paper tackles the computational cost of power iteration by introducing multiplication-avoiding power iteration (MAPI), which reduces multiplications from n^2 to n per iteration for an n×n matrix, leading to faster convergence and superior performance in applications like PCA-based image reconstruction and graph-based ranking.
Power iteration is a fundamental algorithm in data analysis. It extracts the eigenvector corresponding to the largest eigenvalue of a given matrix. Applications include ranking algorithms, recommendation systems, principal component analysis (PCA), among many others. In this paper, we introduce multiplication-avoiding power iteration (MAPI), which replaces the standard $\ell_2$-inner products that appear at the regular power iteration (RPI) with multiplication-free vector products which are Mercer-type kernel operations related with the $\ell_1$ norm. Precisely, for an $n\times n$ matrix, MAPI requires $n$ multiplications, while RPI needs $n^2$ multiplications per iteration. Therefore, MAPI provides a significant reduction of the number of multiplication operations, which are known to be costly in terms of energy consumption. We provide applications of MAPI to PCA-based image reconstruction as well as to graph-based ranking algorithms. When compared to RPI, MAPI not only typically converges much faster, but also provides superior performance.