Advertisement
Advertisement
⚡ Community Insights
Discussion Sentiment
65% Positive
Analyzed from 2339 words in the discussion.
Trending Topics
#svd#singular#values#matrix#math#https#linear#more#algebra#read
Discussion Sentiment
Analyzed from 2339 words in the discussion.
Trending Topics
Discussion (74 Comments)Read Original on HackerNews
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.
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
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.
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.
https://www.oceanopticsbook.info/view/photometry-and-visibil...
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.
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.
https://linear.axler.net/
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.
“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.
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.
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.
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 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 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
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
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.
But it's just an SVD with a few more bells and whistles in my view.
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.
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.
PDF here:
https://www.statlearning.com/
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.