Updating Singular Value Decomposition for Rank One Matrix Perturbation

2017/07/26 by Ratnik Gandhi, Gandhi, Ratnik, Amoli Rajgor +1
Engineering · Physics and Astronomy · #Electromagnetic Compatibility and Measurements #Electromagnetic Scattering and Analysis #Electromagnetic Simulation and Numerical Methods #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Numerical Analysis (math.NA)

paper · pdf · doi:10.48550/arxiv.1707.08369

openalex publication_date 2017/07/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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² log(\frac1ε)) time. The method uses Fast Multipole Method (FMM) for updating singular vectors in O(n log (\frac1ε)) time, where ε is the precision of computation.

Related

• A Fast Implementation of Singular Value Thresholding Algorithm using Recycling Rank Revealing Randomized Singular Value Decomposition
• The Singular Value Decomposition, Applications and Beyond
• Projection techniques to update the truncated SVD of evolving matrices
• Shifted Randomized Singular Value Decomposition
• Subspace Iteration Randomization and Singular Value Problems