Singular Value Decomposition

The ML workhorse

Assumed audience:

People with undergrad linear algebra

An important matrix factorisation. TBC

Randomized methods

Halko, Martinsson, and Tropp (2010),Bach et al. (2019)

as Frobenius minimiser




Bach, C, D. Ceglia, L. Song, and F. Duddeck. 2019. β€œRandomized Low-Rank Approximation Methods for Projection-Based Model Order Reduction of Large Nonlinear Dynamical Problems.” International Journal for Numerical Methods in Engineering 118 (4): 209–41.
Brand, Matthew. 2002. β€œIncremental Singular Value Decomposition of Uncertain Data with Missing Values.” In Computer Vision β€” ECCV 2002, edited by Anders Heyden, Gunnar Sparr, Mads Nielsen, and Peter Johansen, 2350:707–20. Berlin, Heidelberg: Springer Berlin Heidelberg.
β€”β€”β€”. 2006. β€œFast Low-Rank Modifications of the Thin Singular Value Decomposition.” Linear Algebra and Its Applications, Special Issue on Large Scale Linear and Nonlinear Eigenvalue Problems, 415 (1): 20–30.
Bunch, James R., and Christopher P. Nielsen. 1978. β€œUpdating the Singular Value Decomposition.” Numerische Mathematik 31 (2): 111–29.
Gu, Ming, and Stanley C. Eisenstat. 1993. β€œA Stable and Fast Algorithm for Updating the Singular Value Decomposition.” Citeseer.
β€”β€”β€”. 1995. β€œDowndating the Singular Value Decomposition.” SIAM Journal on Matrix Analysis and Applications 16 (3): 793–810.
Halko, Nathan, Per-Gunnar Martinsson, and Joel A. Tropp. 2010. β€œFinding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions.” arXiv.
Hastie, Trevor, Rahul Mazumder, Jason D. Lee, and Reza Zadeh. 2015. β€œMatrix Completion and Low-Rank SVD via Fast Alternating Least Squares.” In Journal of Machine Learning Research, 16:3367–3402.
Rabani, Eran, and Sivan Toledo. 2001. β€œOut-of-Core SVD and QR Decompositions.” In PPSC.
Sarwar, Badrul, George Karypis, Joseph Konstan, and John Riedl. 2002. β€œIncremental Singular Value Decomposition Algorithms for Highly Scalable Recommender Systems.”
Tropp, Joel A., Alp Yurtsever, Madeleine Udell, and Volkan Cevher. 2016. β€œRandomized Single-View Algorithms for Low-Rank Matrix Approximation.” arXiv:1609.00048 [Cs, Math, Stat], August.
Zhang, Yangwen. 2022. β€œAn Answer to an Open Question in the Incremental SVD.” arXiv.

No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.