Multiplication-Avoiding Variant of Power Iteration with Applications

10/22/2021
by   Hongyi Pan, et al.
0

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 ℓ_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 ℓ_1 norm. Precisely, 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset