A história inicial da decomposição de valores singulares (1993) [pdf](math.ucdavis.edu)
math.ucdavis.edu
The early History of the Singular Value Decomposition (1993) [pdf]
https://www.math.ucdavis.edu/~saito/courses/229A/stewart-svd.pdf
84 comments
Just 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-reins...
https://people.inf.ethz.ch/gander/talks/Vortrag2022.pdf
https://www.mathworks.com/company/technical-articles/profess...
https://en.wikipedia.org/wiki/Christian_Reinsch
https://blogs.mathworks.com/cleve/2022/10/23/christian-reins...
https://people.inf.ethz.ch/gander/talks/Vortrag2022.pdf
https://www.mathworks.com/company/technical-articles/profess...
https://en.wikipedia.org/wiki/Christian_Reinsch
For 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.
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.
My intuitive take:
Eigenvectors answer the question, if you have a linear mapping from a space to itself: which lines through (through the origin) remain unchanged after the mapping? And the associated eigenvalues tell you how much a specific point on that line moves along the line. For example: If you rotate things in 3D, the rotation axis remains unchanged. That's the eigenvector. If you reflect things through a mirror plane, any line in that mirror plane will remain unchanged (with eigenvalue 1). Other lines will be, well, mirrored, but there is one line that is reflected onto itself: the one perpendicular to the mirror plane. However, points on it will go from one side to the other, so have eigenvalue -1.
The SVD says something else: Any linear mapping from a space (to itself or a different one - higher or lower dimensional) can be expressed as 1) first a rotation in the old space, then 2) some coordinate scaling or dilation (expansion/contraction) along the coordinate axes, described by the diagonal matrix with singular values, 3) then another rotation in the new space.
Eigenvectors answer the question, if you have a linear mapping from a space to itself: which lines through (through the origin) remain unchanged after the mapping? And the associated eigenvalues tell you how much a specific point on that line moves along the line. For example: If you rotate things in 3D, the rotation axis remains unchanged. That's the eigenvector. If you reflect things through a mirror plane, any line in that mirror plane will remain unchanged (with eigenvalue 1). Other lines will be, well, mirrored, but there is one line that is reflected onto itself: the one perpendicular to the mirror plane. However, points on it will go from one side to the other, so have eigenvalue -1.
The SVD says something else: Any linear mapping from a space (to itself or a different one - higher or lower dimensional) can be expressed as 1) first a rotation in the old space, then 2) some coordinate scaling or dilation (expansion/contraction) along the coordinate axes, described by the diagonal matrix with singular values, 3) then another rotation in the new space.
Just 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-visibil...
https://www.oceanopticsbook.info/view/photometry-and-visibil...
You 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.
hold on. Just realised it's not even (part of ) a vector space.
It's not linear, non-euclidian and can't be mapped onto 3 dimensions.
It's not even constant or always reproducible:
Look at an object;
Observe colour X; then look at the wrong thing;
then look back and you might observe colour X' != X.Doesn't matter: there's no RGB model that captures the colour space. That exactly the reason CIE exists.
CIE (1931) is a RGB color space, based on monochromatic primary colors with wavelengths of 700 nm (red), 546.1 nm (green) and 435.8 nm (blue).
However the entire color space of CIE RGB (1931) includes points where some of the RGB components are negative.
Because positive components are sometimes desirable (e.g. because one can make light filters whose outputs are those components), the alternative XYZ representation is derived by computation from the original CIE RGB, which had been obtained from experiments with human subjects.
Any RGB model can capture the entire color space, even sRGB. The limitation is not at capturing, but only at reproducing colors when using RGB emitters, because the emitters cannot reproduce components with negative values.
There are no RGB models that can capture the entire color space without having points where some components are negative. This is caused mostly by defects of the human color vision, e.g. by the fact that the red receptors are also sensitive to violet light, not only to red light, and by the fact that the selectivity curves of the photoreceptors do not have ideal shapes.
However the entire color space of CIE RGB (1931) includes points where some of the RGB components are negative.
Because positive components are sometimes desirable (e.g. because one can make light filters whose outputs are those components), the alternative XYZ representation is derived by computation from the original CIE RGB, which had been obtained from experiments with human subjects.
Any RGB model can capture the entire color space, even sRGB. The limitation is not at capturing, but only at reproducing colors when using RGB emitters, because the emitters cannot reproduce components with negative values.
There are no RGB models that can capture the entire color space without having points where some components are negative. This is caused mostly by defects of the human color vision, e.g. by the fact that the red receptors are also sensitive to violet light, not only to red light, and by the fact that the selectivity curves of the photoreceptors do not have ideal shapes.
You can represent any arbitrary colors using RGB values for whatever "R", "G", and "B" primaries you like, they just might not fit in the range [0, 1].
(At least, under the strong assumptions we make in color modeling using the CIE system of colorimetry; the basic keyword is "Grassmann's laws".)
(At least, under the strong assumptions we make in color modeling using the CIE system of colorimetry; the basic keyword is "Grassmann's laws".)
Since 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
[1] https://en.wikipedia.org/wiki/CIE_1931_color_space
Not true, you can make the R G and B points far enough out to capture the entire human gamut
You can specify any colour if you can use values below 0 and above 100%.
This is solved through https://en.wikipedia.org/wiki/Primary_color#Imaginary_primar... that sit outside the visible spectrum.
Okay, but that was a really useful metaphor if incomplete in a lot of ways. It made me say “oh”.
Eigenvalue are more flexible than singular values -- If you have procedure for computing eigenvalues of C, squared singular values of X are eigenvalues of C=XX'. Left and write singular vectors of X and eigenvectors of XX' and X'X. For rotation rotation matrix, singular values are all 1. Meanwhile eigenvalues tell you angles of rotation https://math.stackexchange.com/questions/4874616/obtaining-a...
That's like saying spoons are more flexible than forks because you have soup (rotation matrices). Spoons and forks both work for rice (pos def matrices), and you'll want a fork for noodles (rectangular matrices).
You can use eigenvalue solver to find singular values of any matrix but not vica versa. Implementing eigenvalues needs complex numbers
And you can use a spoon to chop spaghetti into pieces. Say I have a 10,000 by 100 matrix (1M elements), squaring that to get a 10,000 x 10,000 (100M elements) matrix to get the singular vectors is probably a bad idea. That squares the condition number too.
The SVD staying in Reals when you have Real data is a nice feature.
The SVD staying in Reals when you have Real data is a nice feature.
> Implementing eigenvalues needs complex numbers
This is exactly why eigenvalues are less flexible than singular values. You can have a real valued matrix that does not have any eigenvalues in the field of real numbers, all eigenvalues are complex numbers. Examples: rotation matrixes in R^2 have no eigenvalues in R. Singular values, on the other hand, are always real (they are eigenvalues of the Hermitian matrix MM^*) and can be used the same way for the matrices over real (R) or complex (C) numbers, hence extra flexibility. Added bonus -- singular values are never negative.
Instead of "more flexible" a better statement would be -- eigenvalues convey more information than singular values.
This is exactly why eigenvalues are less flexible than singular values. You can have a real valued matrix that does not have any eigenvalues in the field of real numbers, all eigenvalues are complex numbers. Examples: rotation matrixes in R^2 have no eigenvalues in R. Singular values, on the other hand, are always real (they are eigenvalues of the Hermitian matrix MM^*) and can be used the same way for the matrices over real (R) or complex (C) numbers, hence extra flexibility. Added bonus -- singular values are never negative.
Instead of "more flexible" a better statement would be -- eigenvalues convey more information than singular values.
Last statement is a bit sus... Muon computes matrix sign function which can be defined as setting singular values to 1, though you can also define it without SVD. Muon itself doesn't use SVD because it uses a faster method to compute matrix sign. Adam doesn't do anything related to SVD or singular values. Also not sure what you meant by "second order singular values"
ADAM is related if your second derivative matrix happens to be diagonal.
Of course, it takes about 5 minutes to show that any DNN is going to have very very high magnitude off-diagonal terms by the way it's constructed, so pretending that a diagonal approximation is close enough is crazy.
Of course, it takes about 5 minutes to show that any DNN is going to have very very high magnitude off-diagonal terms by the way it's constructed, so pretending that a diagonal approximation is close enough is crazy.
Adam doesn't use the second derivatives matrix, it uses second moments of the gradient, which is the diagonal of the uncentered covariance matrix, but neither of them are directly related to SVD or singular values anyway.
There is a slight connection where Adam approximates full-matrix Adagrad which computes inverse square root of the convariance matrix, which you usually do using eigendecomposition, but on the covariance matrix SVD and eigendecomposition are equivalent (can easily be converted to each other), so you could use SVD to compute the inverse square root.
There is a slight connection where Adam approximates full-matrix Adagrad which computes inverse square root of the convariance matrix, which you usually do using eigendecomposition, but on the covariance matrix SVD and eigendecomposition are equivalent (can easily be converted to each other), so you could use SVD to compute the inverse square root.
The second moments of the gradient and the Hessian are absolutely related!
See the Fisher Information, and the Cramer-Rao Lower Bound (an inequality on how much the inverse covariance matrix and the Hessian can differ).
https://en.wikipedia.org/wiki/Fisher_information
See the Fisher Information, and the Cramer-Rao Lower Bound (an inequality on how much the inverse covariance matrix and the Hessian can differ).
https://en.wikipedia.org/wiki/Fisher_information
I didn't find a direct proof earlier, just assertions - I've only seen it proved in textbooks that aren't linkable.
Theorem 1, section 1.3, page 2 shows that the expected variance of the gradient of the loss function and the expected second derivative of the loss function are equal at the minimum. I hate that the ADAM paper did not talk about this, this is something that is hammered into anyone who has taken a mathematical statistics course. This has been an established fact in statistics for well over 100 years.
https://courses.grainger.illinois.edu/ece563/fa2025/Notes11-...
Away from the minimum they can diverge, but there is a close enough connection to make it an extremely useful approximation.
Theorem 1, section 1.3, page 2 shows that the expected variance of the gradient of the loss function and the expected second derivative of the loss function are equal at the minimum. I hate that the ADAM paper did not talk about this, this is something that is hammered into anyone who has taken a mathematical statistics course. This has been an established fact in statistics for well over 100 years.
https://courses.grainger.illinois.edu/ece563/fa2025/Notes11-...
Away from the minimum they can diverge, but there is a close enough connection to make it an extremely useful approximation.
Chapter 7 of Linear Algebra Done Right by Sheldon Axler reads almost as poetry.
https://linear.axler.net/
https://linear.axler.net/
Really? 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.
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.
From 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.
“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.
That'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.
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.
I agree completely. Sure, students could fill all the gaps themselves. But why not just fill the gaps and make good exercises?
They do.
You get some in the prose, and then more in the exercises.
Learn ____ the hard way.
Learn ____ the hard way.
Or the book could fill in more details with a rich exposition and supplement with high quality exercises.
I have mixed feelings about this. BTW my comment is not about Axler's linear algebra book but math pedagogy in general.
Spoon feeding doesn't really help with learning, internalising, building internalisation for. Effort and frustration is key.
For me the best way has been to be forced to discover the important properties and results myself. It is slow but effective and best for knowledge retention. I think the best way to enforce is exercises with grades of progressive hints.
One of my best teachers used to ask us to prove things that are not true. The effort and frustration to prove those were the best teaching moments. We soon caught on to his method though and we're on our alert whenever we were asked to prove something to be true.
Spoon feeding doesn't really help with learning, internalising, building internalisation for. Effort and frustration is key.
For me the best way has been to be forced to discover the important properties and results myself. It is slow but effective and best for knowledge retention. I think the best way to enforce is exercises with grades of progressive hints.
One of my best teachers used to ask us to prove things that are not true. The effort and frustration to prove those were the best teaching moments. We soon caught on to his method though and we're on our alert whenever we were asked to prove something to be true.
The big problem I have with Axler's presentation of the SVD is that it's backwards. It leads with a bunch of completely dry and technical minutiae written formally, loads students up with tedious and confusing technical exercises they aren't likely to appreciate, and defers the motivation, context, explanation, and pictures until a few dozen pages later (probably multiple weeks later for a course), and in my opinion doesn't do a great job with them even then. I think this does a big disservice to students, and I wouldn't recommend anyone learn about the SVD this way. (Admittedly, the SVD is treated more like a curious aside than a centrally important tool in Axler's book; he's not trying to train people to use numerical methods.)
The best place to learn about the SVD is probably in the context of some kind of concrete problem (the most illuminating would be a problem in statistics, image processing, geometry modeling, or whatever, but it could also be a more abstract pure math problem, something about quadratic forms or something) that demonstrates an actual need for it, and then introduce the idea with an intuitive explanation supported by pictures and spatial reasoning. The actual technical details are not really that complicated or hard to figure out once you understand the concept, but if you don't understand the concept then trying to prove a bunch of obscure technical statements just seems like pointless busywork.
The best place to learn about the SVD is probably in the context of some kind of concrete problem (the most illuminating would be a problem in statistics, image processing, geometry modeling, or whatever, but it could also be a more abstract pure math problem, something about quadratic forms or something) that demonstrates an actual need for it, and then introduce the idea with an intuitive explanation supported by pictures and spatial reasoning. The actual technical details are not really that complicated or hard to figure out once you understand the concept, but if you don't understand the concept then trying to prove a bunch of obscure technical statements just seems like pointless busywork.
I mostly agree.
I wouldn't have liked Axler as my first book of linear algebra but as a second book, it worked, it gave me a more algebraic appreciation which is a bit against my natural grain of vector space and geometric way of thinking.
I quite liked Linear Algebra Done Wrong. My first linear algebra book was Noble's.
I wouldn't have liked Axler as my first book of linear algebra but as a second book, it worked, it gave me a more algebraic appreciation which is a bit against my natural grain of vector space and geometric way of thinking.
I quite liked Linear Algebra Done Wrong. My first linear algebra book was Noble's.
Here you sit, an undergraduate with a calculus book open before you, or a pre-thesis graduate student with one of those books whose first ten pages, at least, you would like to master, or a research mathematician (established or would-be) with an article fresh off the press—what do you do now? How do you study, how do you penetrate the darkness, how do you learn something?
All I can tell you for sure is what I do, but I do suspect that the same sort of thing works for everyone. It's been said before and often, but it cannot be overemphasized: study actively. Don't just read it; fight it! Ask your own questions, look for your own examples, discover your own proofs. Is the hypothesis necessary? Is the converse true? What happens in the classical special case? What about the degenerate cases? Where does the proof use the hypothesis?
— Paul Halmos, “I Want to Be a Mathematician”, Study.
Some books simply built around this protocol, some are making it “easier” so they’re more popular and sell more.
All I can tell you for sure is what I do, but I do suspect that the same sort of thing works for everyone. It's been said before and often, but it cannot be overemphasized: study actively. Don't just read it; fight it! Ask your own questions, look for your own examples, discover your own proofs. Is the hypothesis necessary? Is the converse true? What happens in the classical special case? What about the degenerate cases? Where does the proof use the hypothesis?
— Paul Halmos, “I Want to Be a Mathematician”, Study.
Some books simply built around this protocol, some are making it “easier” so they’re more popular and sell more.
So you admit that chapter 7 does not read almost as poetry?
That is the poetry. When all parts clicks together.
The 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.
It 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.
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.
> 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.
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.
How big of an advantage was it, to have the code developed specifically for your project? These AI tools are pretty impressive, but why not have it generate a call to BLAS or PARDISO or something?
There are cases where you don't want the footprint of bringing in another framework / library or that is not even an option.
Yeah, I’m curious what put them in that case here, though. There are high quality open source linear algebra codes out there, so I’m surprised that they needed something generated. (But, just surprised and curious to hear more, not saying they are wrong or anything like that).
Here is an example. I wrote a MacOS app in Objective-C++/C++ that used Eigen's JacobiSVD solver at one point. A colleague of mine use Claude to port it into a web tool that used JavaScript. I scrolled thru the JS code and saw that is wrote is own Jacobi SVD solver. So I assume it did this match the exact behavior of the MacOS app -- using a 3rd party solver may not accomplish this. SVD solvers can behave differently in different use cases. What are the options for JS?
Not sure, I’m not familiar with the web ecosystem. Not familiar at all, so my next question will probably be stupid. Would it have been possible to compile your C++ library to WebAssembly?
I am sure it probably was - a bit heavier option. There other mobile / VR / XR apps that I had to port to a variety of platforms using languages like Swift and Kotlin -- each platform has its own vector library. These don't necessarily provide SVD routines. Apple has their Accelerate framework, but is very unnatural to use IMO -- and Swift and C++ don't play that well together regardless of what folks say (that is why I tend to still use Obj-C++ when I have a choice).
There was another app where I had a 3x3 shear transformation that I needed to decompose into a rotation * scale * rotation which is exactly what SVD does (see https://tinyurl.com/384mkdvh). No need to bring in a full linear algebra package just for that.
There was another app where I had a 3x3 shear transformation that I needed to decompose into a rotation * scale * rotation which is exactly what SVD does (see https://tinyurl.com/384mkdvh). No need to bring in a full linear algebra package just for that.
Solution of linear system is one of those problems that you should program yourself to learn the methods. But there are so many edge cases and details that you have to rely on libraries for production.
You 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.
> 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?
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?
If you're getting code without tests to review in a PR, that should be an instant reject without even looking at the code.
> If you're getting code without tests to review in a PR, that should be an instant reject without even looking at the code.
Management didn’t like that the last time I was assigned a AI-gen PR and I like my job otherwise.
Management didn’t like that the last time I was assigned a AI-gen PR and I like my job otherwise.
Go ahead and have claude add and run units tests for you as part of the PR review process.
Claude is absolutely terrible at writing unit tests, this advice continues to perplex me. Coding agents usually slam you with hundreds of lines that do little more than “test” what is obvious. Maybe it’s good for an API revision or such. But for linear algebra where errors might not manifest unless suitably chosen inputs are generated based on expert knowledge, that’ll be useless.
Have you used Claude lately? It definitely will outperform a human at this task now.
I use it literally every day. But please do not use it to generate tests on its own, it’s all sleight of hand. It does not (without substantial guidance and tweaking from an expert) have the capability to generate meaningful tests.
That's on the submitter of the PR to do. Don't put that burden on the reviewer.
No problem for claude. In fact I would have claude do the PR and go have lunch.
Claude can’t have lunch yet.
I don’t get paid to do my job and then also the submitter’s job.
what work are you doing in computer vision that isn't entirely ML these days?
I'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 (?).
classic! Used the same thing to solve for the rigid transform of an April tag for a calibration problem years ago.
I'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
What sort of algorithms do you run on SAR images?
For 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.
Some 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_l... [1] https://en.wikipedia.org/wiki/Variational_autoencoder
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_l... [1] https://en.wikipedia.org/wiki/Variational_autoencoder
I've recently passed my deep and generative learning exam and in fact before you said vae something was resonating with me, although in our course it wasn't made explicit we were approximating an svd.
Staying in the field of autoencoder, it blows my mind how you can pass from denoising autoencoder (computer science) to scores and eventually matching flows (physics) quite seamlessly
Staying in the field of autoencoder, it blows my mind how you can pass from denoising autoencoder (computer science) to scores and eventually matching flows (physics) quite seamlessly
To me, it's less that an autoencoder approximates an SVD, and more than an SVD is the OG autoencoder.
I made a demo of the SVD part.
https://jmalicki.github.io/svd-grad/
The devil was in the details, and that escalated quickly from a simple idea to actually getting it to work sucked me into a ton of random deep corners.
https://jmalicki.github.io/svd-grad/
The devil was in the details, and that escalated quickly from a simple idea to actually getting it to work sucked me into a ton of random deep corners.
Omg armijo, I don't want to see computational mathematics anymore lol
Aren't you skipping over the noise/stochasticity part from the sampling?
Yes, 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.
But it's just an SVD with a few more bells and whistles in my view.
I also forgot that you have to constrain U and V to be orthonormal - otherwise you end up with the same low rank approximation D', but exactly which numbers go in U, S, or V can shift as it's underdetermined without that constraint.
Can anyone suggest a starting point to be able to read mathematics papers like this and understand them?
This 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.
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.
I 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.
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.
Great book: An Introduction to Statistical Learning
PDF here:
https://www.statlearning.com/
PDF here:
https://www.statlearning.com/
Axler’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.
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.
I recommend asking an LLM to generate an interactive webpage to visualize, teach, and quiz you on the concepts. Or just chat with it directly.
Bâtarde (or littera bastarda) is a hybrid script that blends formal Gothic blackletter with cursive elements.
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
RIP.