Sorry, you need to enable JavaScript to visit this website.

Multiplication-Avoiding Variant of Power Iteration with Applications

Citation Author(s):
Hongyi Pan, Diaa Badawi, Runxuan Miao, Erdem Koyuncu, Ahmet Enis Cetin
Submitted by:
Hongyi Pan
Last updated:
4 May 2022 - 8:17pm
Document Type:
Presentation Slides
Document Year:
Hongyi Pan
Paper Code:

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 ℓ 2 inner products that appear at the regular power iteration (RPI) with multiplication-free vector products, which are Mercer-type kernels that induce the ℓ 1 norm. For an n × 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.

0 users have voted: