Truncated SVD (2023)

akilat90

Some years ago, I was dabbling with PCA and was reading up a bit on the internet forums. As soon as I saw that animation in the blog post, I knew that was from the user “amoeba” in stats stack exchange. Quite random, but turned out my memory was accurate: https://stats.stackexchange.com/a/140579

bee_rider

If you want a truncated SVD, there’s a decent chance you will be happy with a randomized SVD. The paper “Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions” (Halko, Martinsson, and Tropp) is on arxiv. It is generally pretty accessible (although a little mathy), but also has great pseudocode for a number of common use-cases.

hingler36

Meaningful decompositions have got to be my favorite subject in linear algebra, and SVD is the king of these. Another location this pops up is "eigenfaces", an early form of compression (and correlation) of images of faces. Years ago I did a write up of how the SVD relates to singularities of a robotic manipulator: https://akintokinematics.com/notebooks/singular_value_decomp...

andrewla

Some classic HN discussion from the same era: https://news.ycombinator.com/item?id=38695478

nomel

It seems that decreases error curve always has the same shape. Is there a name for this shape? I assume you could sample just a few points and have a good estimate of what the error will be for any truncation. And, this makes me naively assume you could apply some reversible transformation to the image, before applying this, to reduce some of the "perceptual" error (even if at the expense of numeric error)?

E-Reverance

There are better ways to apply SVD to images than the way its usually taught https://www.youtube.com/watch?v=ZGwVlnuuzt4

thearn4

A bit of a blast from my PhD studies past, I used to think a lot about the SVD and application to discrete integral operators. FWIW, on the author's footnote: if anyone is interested truncated SVD and applications to low-rank approximations to convolutions, here's a very outdated paper of mine on exactly that! :) https://www.sciencedirect.com/science/article/abs/pii/S01689...

arjunchint

Nice write-up! The randomized SVD (Halko–Martinsson–Tropp) is a great practical fallback when you only need the top singular values/vectors.