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, principal component analysis (PCA), among many others. Certain use cases may benefit from alternate, non-linear power methods with low complexity. In this paper, we introduce multiplication-avoiding power iteration (MAPI). MAPI replaces the standard ℓ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> inner products that appear at the regular power iteration (RPI) with multiplication-free vector products, which are Mercer-type kernels that induce the ℓ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf> norm. For an n × n matrix, MAPI requires n multiplications, while RPI needs n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> 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{icassp2022_multiplicationav,
title = {Multiplication-Avoiding Variant of Power Iteration with Applications},
author = {Hongyi Pan and Diaa Badawi and Runxuan Miao and Erdem Koyuncu and Ahmet Enis Çetin},
booktitle = {ICASSP 2022},
year = {2022}
}