# Singular Value Decomposition

The ML workhorse

August 5, 2014 — May 23, 2023

feature construction

functional analysis

high d

linear algebra

networks

probability

signal processing

sparser than thou

statistics

### Assumed audience:

People with undergrad linear algebra

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.”