6 ms·
An extension of spectral decomposition on a square matrix is called the singular value decomposition where any matrix can be decomposed. The trick is to diagona
by solinent 6y ago
An extension of spectral decomposition on a square matrix is called the singular value decomposition where any matrix can be decomposed. The trick is to diagonalize the matrix A A^T and A^T A, in this manner we can find the left and right singular values and have an equation which is very similar to the spectral decomposition. It has a very wide range of applicibility--most of which is also highly valuable.
There's also the Moore-Penrose pseudoinverse which also has plenty of applicaitons and works on non-square matrices.
- ivan_ah 6y agoYeah. I don't know why LA courses focus so much on eigenvalues, and don't talk much about SVD. It seems like an obvious next step once you know how to compute eigenvalues, but SVDs are always covered in passing and superficially (at least in courses I've taken). I find it fascinating that A = U∑V^T works on ANY matrix A, with U and V being made of orthogonal vectors (the left and right singular vectors of A)... it's like saying that all matrices are scalings and projections when viewed with appropriate bases for the input and output spaces (U and V). > we can find the left and right singular values Interestingly the (nonzero subset) of the left and right singular values happen to be the same... I don't have a useful intuition about how to explain this. Does anyone know why A A^T and A^T A have the same eigenvalues?
- nextos 6y agoSVDs are the entry point to topic models, e.g. NNMF. Super interesting and useful for modeling large datasets efficiently.
- OscarCunningham 6y ago> Yeah. I don't know why LA courses focus so much on eigenvalues, and don't talk much about SVD. It makes sense to talk about the eigenvalues of an operator on any vector space. But in order for singular values to make sense the vector space needs to have an inner product. So eigenvalues are more general because they make sense even when you haven't chosen an inner product on your vector space. From an HN perspective this kind of consideration is relevant when working on a data set in which there are some arbitrary units. You don't want your model predicting house prices to work differently depending on whether you choose to measure floor size in m^2 or ft^2.
- ssivark 6y agoCould you elaborate on why SVD requires an inner product structure (choice of scale) while eigenvalues do not? Do you just mean that the input and output vector spaces might generically have different units, and so one would need to use some sensible "normalized" units?
- mgraczyk 6y agoSingular values of a transform are defined using the "operator norm" of the transform. The norm is defined in terms of the inner product. On the other hand, eigenvalues are defined with using only the transform and scalar multiplication, which does not require an inner product.
- tsbinz 6y agoI'm not sure you need to do that (define singular values via the operator norm), but one thing I don't see a solution for is getting rid of the requirement of the inner product for the definition of the adjoint.
- kkylin 6y agoThere's probably more than one perspective on this. Here's one: a standard way to approach SVD is to start with a matrix A and consider A^TA and AA^T. Since the latter is symmetric (or hermitian if on a complex vector space, where transpose is replaced by adjoint), by the spectral theorem it has real eigenvalues and orthonormal eigenvectors, from which the SVD can be deduced. But the definition of A^T or A^* depends on a particular choice of basis, and is not a coordinate-invariant concept. If one had an inner product <,>, the adjoint can be defined in a coordinate-independent way using that inner product: A^* is the operator defined by <Au,v> = <u,A^v> for all vectors u and v. (One can check that A^ is uniquely defined.) For a different choice of inner product, one gets a different A^. Note that the operator A^TA comes up naturally when one considers what the action of A does to the length of vectors: |u|^2 = <u,u> |Au|^2 = <Au,Au> = <u,A^Au> Geometrically, the SVD tells us how a linear transformation dilates or contracts space in different directions, e.g., think about what a linear transformation does to a sphere. But all these concepts -- length of vectors, spheres, ellipsoids (images of spheres under linear transformations) -- depend on a choice of inner product.
- SmartestUnknown 6y agoAny two matrices AB and BA have same eigen values. Say v is an eigen vector of AB with eigen value lambda : you have ABv = lambda v. Now BA(Bv) = B(ABv) = B(lambda v) = lambda*(Bv). So, Bv is an eigen vector of BA with eigen value lambda.
- deleted 6y ago[deleted]
- jedbrown 6y agoTrefethen and Bau's Numerical Linear Algebra (http://people.maths.ox.ac.uk/trefethen/text.html http://people.maths.ox.ac.uk/trefethen/text.html) introduces SVD up-front, before discussing how to compute anything.
- bulldoa 6y agocurious, what are some cool application of SVD?
- ivan_ah 6y agoNot the OP, but I've got some links for you: 1. https://en.wikipedia.org/wiki/Singular_value_decomposition#Applications_of_the_SVD https://en.wikipedia.org/wiki/Singular_value_decomposition#A... of which the "Low-rank matrix approximation" is the most important one (it's like looking inside the matrix, seeing its significant components, and zeroing out the remaining ones to save space). See also PCA in statistics. 2. 1976 video about SVD https://www.youtube.com/watch?v=R9UoFyqJca8 https://www.youtube.com/watch?v=R9UoFyqJca8 that shows a visualization for an algorithm for how to compute it. 3. Good two-part blog post series https://jeremykun.com/2016/04/18/singular-value-decomposition-part-1-perspectives-on-linear-algebra/ https://jeremykun.com/2016/04/18/singular-value-decompositio... https://jeremykun.com/2016/05/16/singular-value-decomposition-part-2-theorem-proof-algorithm/ https://jeremykun.com/2016/05/16/singular-value-decompositio...
- hprotagonist 6y agoI’ve used to on neural spike data before. If your responses are not too “messy”, you can estimate the part of the response that was due to a stimulus instead of just noise, pretty well.
- jbay808 6y agoVery useful for working with MIMO (multi input multi output) control systems.
- yt-sdb 6y agoNot an application, but this my favorite explanation of SVD: http://gregorygundersen.com/blog/2018/12/10/svd/ http://gregorygundersen.com/blog/2018/12/10/svd/ It's such an important operation that I'd say understanding it changes how you understand a lot of linear algebra. That Kun post is also good.
- magicalhippo 6y agoLatent semantic indexing[1] uses SVD to identify relationships between words in unstructured text. You can use it to search for words and find related texts even though those texts do not contain the actual words you searched for. Or you can use it to find similar texts, even though important words may differ. Not sure how relevant LSI is these days, not my field at all, but mapping words to vector spaces and using SVD like this kinda blew my mind a bit when I stumbled upon it many years ago. [1]: https://en.wikipedia.org/wiki/Latent_semantic_analysis#Mathematics_of_LSI https://en.wikipedia.org/wiki/Latent_semantic_analysis#Mathe...
- jesuslop 6y agoA digression is that what multiplying A and A^T really means, in the sense that A represents a map of spaces, but A^T represents a map in the opposite direction of the dual spaces. In finite dimension or in topological vector spaces, a space is isomorphic with its dual, but not naturalliy so. It is naturally isomorphic to the double dual! as in Mac Lane's CWM. So the multiplication is doable with an apparent excess good luck. On the other hand, in [1], linear adjoint operators bewteen two topological vector spaces are shown equivalent, up to an scalar, to adjoint functor pairs showing a Galois connection between the posetal categories being the lattice of subspaces of the original two spaces. This story should continue. [1] https://doi.org/10.1090/S0002-9939-1974-0346548-4 https://doi.org/10.1090/S0002-9939-1974-0346548-4
- blt 6y agoI would not call the SVD an "extension" of the eigen decomposition. The SVD is also defined for square matrices and is not equal to the eigen decomposition except for the case of symmetric matrices. This leads to the question: for a non-symmetric square diagonalizable matrix, what is the difference between the eigenvalues and the singular values? A good heuristic for applications is that the eigenvalues capture the asymptotic behavior of repeating the map, i.e. the behavior of A^k as k goes to infinity, while the singular values capture the transient behavior of applying the map once. For example, consider the matrix 0.9 x 0 0.9. As x goes to infinity, its largest singular value becomes infinity, while its eigenvalues remain smaller than one. This means that there exists a vector (0 1) whose image under A is huge, but whose image under A^k still approaches the zero vector for large k. A good book on these topics is "Spectra and Pseudospectra" by Trefethen and Embree.
- solinent 6y agoGood point, while I don't need this clarification others might. I shouldn't have implied that they are the same for square matrices implicitly, hence my failed attempt at using "similar". However, they're still an extension in the sense that singular values do correspond to (square of the) eigenvalues of the square matrix A A^T and A^T A.
- blt 6y agoYeah I guess "extension" is not a precisely defined word. I wanted to make sure other readers didn't interpret like "generalization", meaning that the original narrow concept is precisely a special case of the extension.
- solinent 6y agoYeah, I wouldn't have used extension for a math audience, probably just "related concept", or "application of". In the software context it usually means the opposite--something specific that makes use of some existing functionality.
- cameronperot 6y agoGilbert Strang covers a this well in his "18.065 - Matrix Methods in Data Analysis, Signal Processing, and Machine Learning" course [1]. I can highly recommend the lecture series to anyone interested in such topics. [1] https://www.youtube.com/watch?v=rYz83XPxiZo&list=PLUl4u3cNGP63oMNUHXqIUcrkS2PivhN3k&index=8 https://www.youtube.com/watch?v=rYz83XPxiZo&list=PLUl4u3cNGP...