Singular Value Decomposition
The ML workhorse
August 5, 2014 — May 22, 2023
An important matrix factorisation. TBC
1 Randomized methods
2 Incremental updates / downdates
(Brand 2006, 2002; Bunch and Nielsen 1978; Gu and Eisenstat 1995, 1993; Sarwar et al. 2002; Zhang 2022).
3 as Frobenius minimiser
TODO.
4 For PCA
5 Incoming
Carlo Tomasi, elegantly pedagogic.
Avrim Blum on SVD
6 References
Bach, Ceglia, Song, et al. 2019. “Randomized Low-Rank Approximation Methods for Projection-Based Model Order Reduction of Large Nonlinear Dynamical Problems.” International Journal for Numerical Methods in Engineering.
Brand. 2002. “Incremental Singular Value Decomposition of Uncertain Data with Missing Values.” In Computer Vision — ECCV 2002.
———. 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,.
Bunch, and Nielsen. 1978. “Updating the Singular Value Decomposition.” Numerische Mathematik.
Gu, and Eisenstat. 1993. “A Stable and Fast Algorithm for Updating the Singular Value Decomposition.”
———. 1995. “Downdating the Singular Value Decomposition.” SIAM Journal on Matrix Analysis and Applications.
Halko, Martinsson, and Tropp. 2010. “Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions.”
Hastie, Mazumder, Lee, et al. 2015. “Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares.” In Journal of Machine Learning Research.
Rabani, and Toledo. 2001. “Out-of-Core SVD and QR Decompositions.” In PPSC.
Sarwar, Karypis, Konstan, et al. 2002. “Incremental Singular Value Decomposition Algorithms for Highly Scalable Recommender Systems.”
Tropp, Yurtsever, Udell, et al. 2016. “Randomized Single-View Algorithms for Low-Rank Matrix Approximation.” arXiv:1609.00048 [Cs, Math, Stat].
Zhang. 2022. “An Answer to an Open Question in the Incremental SVD.”