Multiplication-Avoiding Variant of Power Iteration with Applications

Hongyi Pan, Diaa Badawi, Runxuan Miao, Erdem Koyuncu, Ahmet Enis Çetin

Abstract

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.
BibTeX
@inproceedings{pan2022multiplication,
  author = {Hongyi Pan and Diaa Badawi and Runxuan Miao and Erdem Koyuncu and Ahmet Enis Çetin},
  title = {{Multiplication-Avoiding Variant of Power Iteration with Applications}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2022},
  url = {https://openreview.net/forum?id=65PQTVz9oy},
}

Loading related content...

Figure