Singular Value Decomposition for Programmers

Think about the x-y plane, and imagine that we've drawn out the unit circle centered at the origin. Now imagine we have some matrix A that we apply to each point in the plane. Thus points will go here and there and you could visualize this effect, if you want, as producing a sort of vector field drawn above the plane where the start of each arrow is the original position of a point and the end of each arrow is where the matrix A moved it. A cute thing about matrices is that it can only do one of three things to the unit circle. It can either collapse the unit circle into a point (which happends only if A is the zero matrix), or it can transform it into a line, or it can transform it into an ellipse. Other functions could possibly transform the circle into some other shape, but matrices are constrained enough that they can only do one of these three things to it.

Now for the SVD. Here's the thing. Basically the SVD gives you information about the ellipse at the output of the matrix. You apply numpy.linalg.svd to your matrix and how can you understand what it gives you? Essentially it gives you information about the semi-axes of that ellipse.

The first column of the "U" matrix is a vector that start at the origin and extend out towards the first (biggest) semi-axis. The second column extend out to the second largest semi-axis, and so on. But they are all normalized so they don't actually touch the semi-axes, they only point towards them. The values in the diagonal of the middle matrix (often denoted Σ) in the SVD (called "singular values") contains the length of the semi-axes. If all of them are 1 then the matrix did not change the size of the circle one bit.

From this intuitive description follows a lot of the properties mentioned in the article. For instance, want to know if the matrix is invertible? Just check out the singular values. If one of them is zero (or near zero since the algorithm for computing the SVD often only gives you an approximate result) then that means the ellipse at the output is collapsed down one dimension, which means it is definitely not invertible since there are a bunch of points which are mapped to the zero vector, and there is no way to figure out where those points should map back to if you wanted to create an inverse function.

By the way, if you want to learn more, go check out Boyds course on linear dynamical systems[1]. That's essentially where I stole this explanation from.

[1] https://www.youtube.com/watch?v=ZNQ_pBCtYDg

https://jeremykun.com/2016/04/18/singular-value-decompositio...

https://jeremykun.com/2016/05/16/singular-value-decompositio...

The first one is particularly helpful for understanding SVD conceptually.

source code: http://github.com/uncomplicate/neanderthal

and the documentation: http://neanderthal.uncomplicate.org

So never try to do this for large square matrices. (Just like you should never compute the inverse of a large matrix).

Even for large non-square matrices, computing the SVD can be prohibitively expensive.