5 ms·
The early History of the Singular Value Decomposition (1993) [pdf]
- waynecochran 3mo agoThe SVD seems to come up everywhere in my work in computer vision. I find myself continuously using the various C++/Eigen SVD implementations. Actually I should speak in the past tense. Claude and Codex are now generating all my code for me now, and I see them spitting out SVD code frequently -- often for very special cases. SVD truly is an amazing tool.
- eigenspace 3mo agoIt comes up anywhere that youre working with data that has some sort of correlation structure. In image processing, the SVD makes it possible to talk about all the rich spatial correlations in the image, and pick out the strongest ones and discard noise. This is also why it's so ubiquitous in compression algorithms, and of central importance in stuff like quantum information.
- fooblaster 3mo agowhat work are you doing in computer vision that isn't entirely ML these days?
- waynecochran 3mo agoI'll give you one example, an often first step to solving the Perspective N Point (PNP) problem involves using the Direct Linear Transform (DLT) method which boils down to solving AX = 0 where A in a 12x2N matrix (N can be 6 to 500). The best way to solve this is with SVD. The first published PNP solver (for N = 3) dates to 1841 (did not use SVD) and we still are solving that problem now and I imagine we will still be solving it in 100 years (?).
- fooblaster 3mo agoclassic! Used the same thing to solve for the rigid transform of an April tag for a calibration problem years ago.
- aptitude_moo 3mo agoI'm not the person you are replying to but I work in image processing of SAR radar images and it's mostly ML-free (thankfully because I don't enjoy it). I dont know which other areas still work with these things
- fooblaster 3mo agoWhat sort of algorithms do you run on SAR images?
- aptitude_moo 3mo agoFor example, to create the image from the radar pulses, you can do time-domain backprojection, omega-k and others. Then when comparing images of different dates you can do SAR interferometry, then use numerical methods, iterative algorithms. Although I'm thinking this may be called signal processing instead of computer vision.
- TimorousBestie 3mo ago> Claude and Codex are now generating all my code for me now, and I see them spitting out SVD code frequently -- often for very special cases. I find this so annoying. I had to PR some Claude-generated gaussian elimination routine last month and making sure it got the pivoting logic correct was a waste of my time.
- waynecochran 3mo agoYou are doing it wrong. Have Claude generate the test code and log test data that it can feed back into itself. Claude can generate tests and verify the code better than humans now. I don't trust humans to get things right anymore -- I have a PhD and Claude knows all the math and libraries better than me.
- TimorousBestie 3mo ago> You are doing it wrong. I didn’t write any of it. I occasionally get assigned PRs written (or not, in this case) by other devs. > Claude can generate tests and verify the code better than humans now. It certainly didn’t do that in this case. > I don't trust humans to get things right anymore -- I have a PhD and Claude knows all the math and libraries better than me. If it knows all the libraries so well, why did it add a bespoke implementation?
- jmalicki 3mo agoIf you're getting code without tests to review in a PR, that should be an instant reject without even looking at the code.
- waynecochran 3mo agoGo ahead and have claude add and run units tests for you as part of the PR review process.
- jmalicki 3mo ago
- muragekibicho 3mo agoFor the curious, eigenvalues only exist for square matrices. Singular values are like generalized eigenvalues. Singular values are like the fundamental frequencies of your matrix. You know how you can define any color with RGB? In a (pretty handwavy) way, singular values are like RGB color codes for us math guys. Optimizers like Muon and Adam play around with weights' first, or second order singular values to train models.
- toolslive 3mo agoJust going to sound really pedantic here, but RGB does not capture the entire colour space. In fact, it only captures about 35% of the colours the human eye can perceive. https://www.oceanopticsbook.info/view/photometry-and-visibility/from-xyz-to-rgb https://www.oceanopticsbook.info/view/photometry-and-visibil...
- piker 3mo agoOkay, but that was a really useful metaphor if incomplete in a lot of ways. It made me say “oh”.
- wtallis 3mo agoYou seem to be conflating "RGB" with one particular RGB color space: sRGB. That's a common enough conflation to make, but not appropriate when you're trying to be pedantic.
- toolslive 3mo agoDoesn't matter: there's no RGB model that captures the colour space. That exactly the reason CIE exists.
- interroboink 3mo agoSince you seem to know, and I am curious, doesn't CIE[1] effectively use RGB to describe its space, too? Eg: the r̅(λ) g̅(λ) b̅(λ) color matching functions? Or is there something else in CIE you're referring to? [1] https://en.wikipedia.org/wiki/CIE_1931_color_space https://en.wikipedia.org/wiki/CIE_1931_color_space
- jmalicki 3mo agoSome fun stuff about SVDs: If you want to take a low rank approximation to a matrix D, let's call our approximation D'. The approximation that minimizes mean square error of the reconstructed matrix vs. the original (i.e. ||D - D'||_F, the Frobenius norm of their differences) happens to be the truncated SVD, by the Eckart–Young–Mirsky theorem [0]. I'm not claiming it's a practical way to do so, but this means that if you set up a neural network w/o nonlinearities that goes U -> S -> V^T, where S is a truncated scaling vector, and U and V^T are trained weights, make your loss function the MSE of reconstruction error, and minimize it with gradient descent, you will end up with the same U, S, and V that an SVD gives you. In fact, this is basically exactly what a Variational Autoencoder [1] is! Way too few people realize this connection, and I wish it was taught in more ML courses. VAEs just add nonlinearities between U -> nonlinearity -> S -> nonlinearity -> V^T, and a KL-divergence regularization term. (Well VAEs are trained as operators to reconstruct vectors, and the S is an embedding not a trained weight, so I'm being a little sloppy, but still the connection is strong). Once you realize this, you can have a lot of fun... anywhere you see an SVD being useful, you can construct arbitrary neural networks to replace them, and any time an SVD doesn't quite fit, e.g. you have binary data, realize that VAEs are just the same thing you can make all kinds of bespoke changes to... don't want MSE as your reconstruction error? Fine, use something else, but it's basically just an SVD! [0] https://en.wikipedia.org/wiki/Low-rank_approximation#Basic_low-rank_approximation_problem https://en.wikipedia.org/wiki/Low-rank_approximation#Basic_l... [1] https://en.wikipedia.org/wiki/Variational_autoencoder https://en.wikipedia.org/wiki/Variational_autoencoder
- selimthegrim 3mo agoAren't you skipping over the noise/stochasticity part from the sampling?
- jmalicki 3mo agoYes, that too, in addition to the other differences I pointed out. But it's just an SVD with a few more bells and whistles in my view.
- jmalicki 3mo ago
- allepo 3mo agoBâtarde (or littera bastarda) is a hybrid script that blends formal Gothic blackletter with cursive elements.
- snalty 3mo agoCan anyone suggest a starting point to be able to read mathematics papers like this and understand them?
- TimorousBestie 3mo agoAxler’s _Linear Algebra Done Right_ should get you at least part of the way there, content-wise, depending on what other math background you have. As for reading math papers in general, it’s mostly a process of stepping through it incrementally and trying to verify the steps you don’t understand based on the surrounding context. Most of the concepts in this paper are accessible on Wikipedia or elsewhere, you can make small (e.g. 2 x 2) examples as you go and see what happens. It’s not an easy skill to acquire from scratch, especially from outside the ivory tower.
- Diogenesian 3mo agoThis paper is actually not a bad one to get started with. Obviously you need the proper background and I am not sure how much linear algebra you've taken. Going through a senior undergrad numerical linear algebra text might be a good way to learn the prerequsites. In particular, you'll never be able to read a math paper without developing mathematical maturity via textbook exercises. Assuming you have the background, the boring answer is "patience and practice." For years I had to practically rewrite math papers word for word in order to get anything to stick. These days I am better at reading "mentally," but still sloppy and prone to misreading (just yesterday I misread GPT's proof because I was lazy and on my phone). More so than the empirical sciences, mathematics demands you understand every sentence before moving on to the next. Skimming does you no good. It really does just take patience and perseverance. The nice thing about this paper is that the math isn't especially advanced, and it's broken up with qualitative historical discussions. If you know a decent bit of linear algebra (enough to understand artificial neural networks), I think you can muddle through this.
- simonreiff 3mo agoI really recommend Professor Gilbert Strang's linear algebra course and also would check out any Michael Penn videos, both on YouTube, but for linear algebra, the Strang/MIT course is the best resource anywhere that I know. The Gilbert Strang video series on linear algebra includes the 18.06 course, as well as an 18.06B or something like that where he goes into detail about the SVD and ML algorithms like gradient descent. Generally if you're struggling with a math paper on the first or second page, no point in fighting it; gotta come back after you have the prerequisites. Nobody is born knowing this stuff, and also, all branches of math contain endless piles of really easy-to-describe but hopelessly difficult problems so never feel bad if you don't know how to solve a problem or even understand what you are reading. Just take your time, learn what you need, come back, a bit more hopefully makes sense, learn still more, and over time more things will become familiar.
- tzury 3mo agoChapter 7 of Linear Algebra Done Right by Sheldon Axler reads almost as poetry. https://linear.axler.net/ https://linear.axler.net/
- jacobolus 3mo agoReally? I find the part about the SVD in Axler's book extremely unhelpful, big blobs of opaque formulas and jargon with next to no explanation or context that basically require either knowing the topic fully beforehand or a huge amount of effort to parse. e.g. Axler's definition of singular values is the extremely dry and technical: > Suppose T is in L(V, W). The singular values of T are the nonnegative square roots of the eigenvalues of T†T, listed in decreasing order, each included as any times as the dimension of the corresponding eigenspace of T†T. (Using a dagger instead of an asterisk for the conjugate transpose since HN interprets and asterisk to mean italics.) If you already just proved a lot of stuff about eigenvalues, this could be a serviceable definition; at any rate it saves space. But it doesn't really explain the point. I'd recommend anyone interested in this or related topics read Trefethen & Bau (1997) Numerical Linear Algebra.
- tzury 3mo agoFrom the preface “You cannot read mathematics the way you read a novel. If you zip through a page in less than an hour, you are probably going too fast. When you encounter the phrase “as you should verify”, you should indeed do the verification, which will usually require some writing on your part. When steps are left out, you need to supply the missing pieces. You should ponder and internalize each definition. For each theorem, you should seek examples to show why each hypothesis is necessary.” It is a math studying book, not a let me chew it for you before you take it in type of a book. It requires effort, focus and missing steps are missing on purpose so you will discover them. This is the fun about studying mathematics. Sorry you fell that way, but the book in my opinion is a masterpiece in math composition.
- jacobolus 3mo agoThat's all well and good, but you also shouldn't excuse authors for not providing context, motivation, or explanation under the theory that the students should really be figuring out the whole subject from scratch for themselves. If you are really lucky the result of not explaining things might be an occasional exceptional student who works out a correct personal concept. But more commonly the result is just an unfilled gap in understanding and either a moderately motivated student who develops fluency with symbol twiddling but doesn't get the point of what they're doing or a less-motivated student who decides the topic sucks and gives up. I've read a lot of linear algebra books, and I personally find Axler's to have average quality exposition and a not tremendously insightful point of view. I know other people who swear by the book though, so YMMV. It's more appropriate for a well prepared pure math student who wants to go to grad school and has a goal of internalizing a lot of jargon so they can read/write pure math papers than for a scientist or computer programmer.
- FabHK 3mo agoBTW, if you wonder about the dedication ("For Gene Golub on his 15th birthday"): Gene Golub was a numerical analyst, and father of the practical singular value decomposition (his license plate read "Prof SVD"), together with William Kahan (the father of IEEE 754 floating point numbers). And his birthday was February 29. (In other words, the article was on the occasion of Gene's 60th birthday). https://en.wikipedia.org/wiki/Gene_H._Golub https://en.wikipedia.org/wiki/Gene_H._Golub RIP.
- FabHK 3mo agoJust to add: Credit is also due to Prof Christian Reinsch from Technical University of Munich (in addition to Golub and Kahan) for the invention of the practical algorithm for computing the SVD still in use today. https://blogs.mathworks.com/cleve/2022/10/23/christian-reinsch-roland-bulirsch-and-the-svd/ https://blogs.mathworks.com/cleve/2022/10/23/christian-reins... https://people.inf.ethz.ch/gander/talks/Vortrag2022.pdf https://people.inf.ethz.ch/gander/talks/Vortrag2022.pdf https://www.mathworks.com/company/technical-articles/professor-svd.html https://www.mathworks.com/company/technical-articles/profess... https://en.wikipedia.org/wiki/Christian_Reinsch https://en.wikipedia.org/wiki/Christian_Reinsch