Timezone: »
Poster
Projection techniques to update the truncated SVD of evolving matrices with applications
Vasileios Kalantzis · Georgios Kollias · Shashanka Ubaru · Athanasios N. Nikolakopoulos · Lior Horesh · Kenneth Clarkson
This submission 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 computational kernel in applications
such as Latent Semantic Indexing and Recommender Systems. Nonetheless,
the proposed framework is purely algebraic and
targets general updating problems. The algorithm presented in this paper
undertakes a projection viewpoint and focuses on building a pair of
subspaces which approximate the linear span of the sought singular vectors
of the updated matrix. We discuss and analyze two different choices to
form the projection subspaces. Results on matrices from real applications
suggest that the proposed algorithm can lead to higher accuracy,
especially for the singular triplets associated with the largest modulus
singular values. Several practical details and key differences with other
approaches are also discussed.
Author Information
Vasileios Kalantzis (IBM Research)
https://www-users.cs.umn.edu/~kalan019/
Georgios Kollias (IBM)
Shashanka Ubaru (IBM Research)
Athanasios N. Nikolakopoulos (Amazon)
Lior Horesh (IBM Research)
Kenneth Clarkson (IBM Research)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Spotlight: Projection techniques to update the truncated SVD of evolving matrices with applications »
Fri. Jul 23rd 01:40 -- 01:45 AM Room
More from the Same Authors
-
2022 Poster: Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra »
Nadiia Chepurko · Kenneth Clarkson · Lior Horesh · Honghao Lin · David Woodruff -
2022 Spotlight: Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra »
Nadiia Chepurko · Kenneth Clarkson · Lior Horesh · Honghao Lin · David Woodruff -
2021 Poster: Analysis of stochastic Lanczos quadrature for spectrum approximation »
Tyler Chen · Thomas Trogdon · Shashanka Ubaru -
2021 Oral: Analysis of stochastic Lanczos quadrature for spectrum approximation »
Tyler Chen · Thomas Trogdon · Shashanka Ubaru -
2019 Poster: Dimensionality Reduction for Tukey Regression »
Kenneth Clarkson · Ruosong Wang · David Woodruff -
2019 Oral: Dimensionality Reduction for Tukey Regression »
Kenneth Clarkson · Ruosong Wang · David Woodruff