CaltechAUTHORS
  A Caltech Library Service

The random component-wise power method

Teke, Oguzhan and Vaidyanathan, Palghat P. (2019) The random component-wise power method. In: Wavelets and Sparsity XVIII. Proceedings of SPIE. No.11138. Society of Photo-Optical Instrumentation Engineers (SPIE) , Bellingham, WA, Art. No. 111381L. ISBN 9781510629691. https://resolver.caltech.edu/CaltechAUTHORS:20190913-090526091

[img] PDF - Published Version
See Usage Policy.

968Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190913-090526091

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1117/12.2530511DOIArticle
ORCID:
AuthorORCID
Teke, Oguzhan0000-0002-1131-5206
Vaidyanathan, Palghat P.0000-0003-3003-7042
Additional Information:© 2019 Society of Photo-Optical Instrumentation Engineers (SPIE). The authors would like to thank Dr. Dimitri Van De Ville for the invitation to write this article.
Subject Keywords:Fixed point iteration, randomized iterations, low-rank approximation, distributed computation
Series Name:Proceedings of SPIE
Issue or Number:11138
Record Number:CaltechAUTHORS:20190913-090526091
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190913-090526091
Official Citation:Oguzhan Teke and Palghat P. Vaidyanathan "The random component-wise power method", Proc. SPIE 11138, Wavelets and Sparsity XVIII, 111381L (9 September 2019); https://doi.org/10.1117/12.2530511
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98633
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:13 Sep 2019 16:17
Last Modified:03 Oct 2019 21:43

Repository Staff Only: item control page