Updating Singular Value Decomposition for Rank One Matrix Perturbation
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}{\epsilon}))$ time. The method uses Fast Multipole Method (FMM) for updating singular vectors in $O(n \ \text{log} (\frac{1}{\epsilon}))$ time, where $\epsilon$ is the precision of computation.
Code (1)
Similar Papers 제목 키워드 기반
Projection techniques to update the truncated SVD of evolving matrices
This paper considers the problem of updating the rank-k truncated Singular Value Decomposition (SVD) of matrices subject to the addition of new rows and/or columns over time. Such matrix problems represent an important c…
Recommendation SystemsEfficient Robust Principal Component Analysis via Block Krylov Iteration and CUR Decomposition
Robust principal component analysis (RPCA) is widely studied in computer vision. Recently an adaptive rank estimate based RPCA has achieved top performance in low-level vision tasks without the prior rank, but both t…
The Singular Value Decomposition, Applications and Beyond
The singular value decomposition (SVD) is not only a classical theory in matrix computation and analysis, but also is a powerful tool in machine learning and modern data analysis. In this tutorial we first study the basi…
BIG-bench Machine LearningMatrix CompletionEvaluating Singular Value Thresholds for DNN Weight Matrices based on Random Matrix Theory
This study evaluates thresholds for removing singular values from singular value decomposition-based low-rank approximations of deep neural network weight matrices. Each weight matrix is modeled as the sum of signal and …
Ranky : An Approach to Solve Distributed SVD on Large Sparse Matrices
Singular Value Decomposition (SVD) is a well studied research topic in many fields and applications from data mining to image processing. Data arising from these applications can be represented as a matrix where it is la…