Updating Singular Value Decomposition for Rank One Matrix Perturbation

Code

• github.com/AmoliR/rank1-svd-update
  none★ 0

Abstract

An efficient Singular Value Decomposition (SVD) algorithm is an important tool for distributed and streaming computation in big data problems. It is observed that update of singular vectors of a rank-1 perturbed matrix is similar to a Cauchy matrix-vector product. With this observation, in this paper, we present an efficient method for updating Singular Value Decomposition of rank-1 perturbed matrix in O(n^2 \ log(1)) time. The method uses Fast Multipole Method (FMM) for updating singular vectors in O(n \ log (1)) time, where is the precision of computation.

Reproductions