# Multiplication-Avoiding Variant of Power Iteration with Applications

arXiv: https://arxiv.org/abs/2110.12065 · HTML: https://mlsanity.com/paper/2110.12065/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 31 references that are in the map.
- First posted on arXiv 22 Oct 2021.

## Builds on (most cited first, 7 of 7)

- [Accelerated Stochastic Power Iteration](https://mlsanity.com/paper/1707.02670/) (2017)
- [Optimal Algorithms for L1-subspace Signal Processing](https://mlsanity.com/paper/1405.6785/) (2014)
- [MF-Net: Compute-In-Memory SRAM for Multibit Precision Inference using Memory-immersed Data Conversion and Multiplication-free Operators](https://mlsanity.com/paper/2102.00035/) (2021)
- [Efficient L1-Norm Principal-Component Analysis via Bit Flipping](https://mlsanity.com/paper/1610.01959/) (2016)
- [A Generalization of Principal Component Analysis](https://mlsanity.com/paper/1910.13511/) (2019)
- [A Simple and Fast Algorithm for L1-norm Kernel PCA](https://mlsanity.com/paper/1709.10152/) (2017)
- [Robust Principal Component Analysis Using a Novel Kernel Related with the L1-Norm](https://mlsanity.com/paper/2105.11634/) (2021)

## Built on by (most cited first, 1 of 1)

- [Federated Momentum Contrastive Clustering](https://mlsanity.com/paper/2206.05093/) (2022)

## Abstract (arXiv)

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 n2 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.