Updating Singular Value Decomposition for Rank One Matrix Perturbation
This work addresses computational bottlenecks for researchers and practitioners in big data and streaming applications, offering an incremental improvement over existing SVD update methods.
The paper tackles the problem of efficiently updating Singular Value Decomposition (SVD) for rank-one matrix perturbations, which is crucial in distributed and streaming big data contexts, by presenting a method that achieves an overall time complexity of O(n^2 log(1/ε)) and uses the Fast Multipole Method to update singular vectors in O(n log(1/ε)) time.
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 \ \text{log}(\frac{1}ε))$ time. The method uses Fast Multipole Method (FMM) for updating singular vectors in $O(n \ \text{log} (\frac{1}ε))$ time, where $ε$ is the precision of computation.