4 ms·
Truncated SVD (2023)
- akilat90 24d agoSome 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 https://stats.stackexchange.com/a/140579
- bee_rider 24d agoIf 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 24d agoMeaningful 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_decomposition.html https://akintokinematics.com/notebooks/singular_value_decomp...
- andrewla 24d agoSome classic HN discussion from the same era: https://news.ycombinator.com/item?id=38695478 https://news.ycombinator.com/item?id=38695478
- nomel 24d agoIt 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 24d agoThere are better ways to apply SVD to images than the way its usually taught https://www.youtube.com/watch?v=ZGwVlnuuzt4 https://www.youtube.com/watch?v=ZGwVlnuuzt4
- thearn4 24d agoA 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/S0168927413000822 https://www.sciencedirect.com/science/article/abs/pii/S01689...
- arjunchint 24d agoNice write-up! The randomized SVD (Halko–Martinsson–Tropp) is a great practical fallback when you only need the top singular values/vectors.
- mr_big_bowls 24d ago[dead]