Share Email Print
cover

Proceedings Paper • new

The random component-wise power method
Author(s): Oguzhan Teke; Palghat P. Vaidyanathan
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

This paper considers a random component-wise variant of the unnormalized power method, which is similar to the regular power iteration except that only a random subset of indices is updated in each iteration. For the case of normal matrices, it was previously shown that random component-wise updates converge in the mean-squared sense to an eigenvector of eigenvalue 1 of the underlying matrix even in the case of the matrix having spectral radius larger than unity. In addition to the enlarged convergence regions, this study shows that the eigenvalue gap does not directly affect the convergence rate of the randomized updates unlike the regular power method. In particular, it is shown that the rate of convergence is affected by the phase of the eigenvalues in the case of random component-wise updates, and the randomized updates favor negative eigenvalues over positive ones. As an application, this study considers a reformulation of the component-wise updates revealing a randomized algorithm that is proven to converge to the dominant left and right singular vectors of a normalized data matrix. The algorithm is also extended to handle large-scale distributed data when computing an arbitrary rank approximation of an arbitrary data matrix. Numerical simulations verify the convergence of the proposed algorithms under different parameter settings.

Paper Details

Date Published: 9 September 2019
PDF: 16 pages
Proc. SPIE 11138, Wavelets and Sparsity XVIII, 111381L (9 September 2019); doi: 10.1117/12.2530511
Show Author Affiliations
Oguzhan Teke, Caltech (United States)
Palghat P. Vaidyanathan, Caltech (United States)


Published in SPIE Proceedings Vol. 11138:
Wavelets and Sparsity XVIII
Dimitri Van De Ville; Manos Papadakis; Yue M. Lu, Editor(s)

© SPIE. Terms of Use
Back to Top