Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The big six matrix factorizations

nhigham.com

Post reply on HN
Print view View original

71–80 of 84 posts

Re: The big six matrix factorizations

#71

Post by FabHK »

isaacfrond wrote: post #2

The article presents a note on the 6 well known matrix compositions. He states that all of them have cubic complexity, but practical algorithms with better exponents exist for all of them.

Can you provide a source?

For example, the SVD (Golub-Kahan-Reinsch) method generally involves bidiagonalisation of the matrix and then implicit QR steps, which are often achieved with Householder reflections and Givens rotations. Sure, all of those are conceptually matrix multiplications, but they're not implemented as O(N^3) matrix multiplications; rather, their special structure is exploited so that they're faster. Yet, the entire algorithm is still cubic. So not sure Strassen would accelerate things.

Re: The big six matrix factorizations

#72

Post by FabHK »

gnufx wrote: post #52
oh_my_goodness wrote: post #10

Earlier quoted context omitted.

Could you link a practical algorithm with an exponent lower than 3? (I think of these things https://en.wikipedia.org/wiki/Computational_complexity_of_ma... as not being practical, but I'd love to be wrong. )

For something Strassen-ish you could look at https://jianyuhuang.com/papers/sc16.pdf and the GPU implementation https://apps.cs.utexas.edu/apps/sites/default/files/tech_rep...

That's matrix-matrix multiplication. Nobody disputes that Strassen etc. have sub-cubic complexity. What about one of the six decompositions mentioned, as GP claimed?

Re: The big six matrix factorizations

#73

Post by FabHK »

heinrichhartman wrote: post #14

From a theoretical perspective the most fundamental decomposition is the rank-decomposition: A = X D Y with X,Y invertible and D diagonal. It's called rank decomposition, because you can read off the rank from A by counting the non-zero entries in D. It's also useful to determining bases for the image and the kernel of A. Every math student learns a version of that in their first lecture series of Linear Algebra. Cur…

Isn't the Jordan decomposition the most fundamental one for theory?

Re: The big six matrix factorizations

#77

Post by [deleted] »

arbitrandomuser wrote: post #58
rhyn00 wrote: post #45

Spectral decomposition is pretty cool. Application 1 - spectral clustering - an alternative to k-means for nonlinear clusters. Get a Distance matrix of your data, spectral decomp, run k-means on your k top eigen vectors and that's your clusters. Application 2 - graph clustering - (run spectral clustering on adj matrix!) There's some tricks to getting it to work in practice like normalizing but it's a simple and power…

I've never given a second thought about what the etymology of "spectral" in spectral decomposition is. Somewhere in the back of my mind (and I guess many students of physics have the same notion) subconsciously i assumed it originates from eigenvalues of the Hamiltonian determining the atomic spectral lines . But I've never followed up on it and actually looked it up .

[deleted]

Re: The big six matrix factorizations

#78

Post by the_svd_doctor »

signaru wrote: post #76

QR factorization leads to many useful stuff : Eigenvalues/vectors, SVD (singular value decomposition), PCA (principal component analysis)

QR iteration (which uses QR decomposition) truly is a remarkable and beautiful algorithm.

It was even coined one of the top 10 algorithm of the 20th century https://archive.siam.org/pdf/news/637.pdf

Re: The big six matrix factorizations

#79

Post by blt »

the_svd_doctor wrote: post #64
arbitrandomuser wrote: post #58

Earlier quoted context omitted.

I've never given a second thought about what the etymology of "spectral" in spectral decomposition is. Somewhere in the back of my mind (and I guess many students of physics have the same notion) subconsciously i assumed it originates from eigenvalues of the Hamiltonian determining the atomic spectral lines . But I've never followed up on it and actually looked it up .

I might be wrong about the exact historical reason. But the way I see it "spectral decomposition of A" is a way to express A as a sum of orthogonal, rank-1, operators. A = \sum l_i u_i u_i^T. Those l_i are the eigenvalues; u_i are the eigenvectors. The eigenvectors look a whole lot like the "modes" in a Fourier decomposition. And if you plot (i, l_i), the eigenvalues are a bit like the "spectrum" (the amplitude of ea…

The spectrum of the matrix A is also closely related to the frequencies at which the ordinary differential equation xdot = Ax oscillates!

Re: The big six matrix factorizations

#80

Post by gnufx »

FabHK wrote: post #72
gnufx wrote: post #52

Earlier quoted context omitted.

For something Strassen-ish you could look at https://jianyuhuang.com/papers/sc16.pdf and the GPU implementation https://apps.cs.utexas.edu/apps/sites/default/files/tech_rep...

That's matrix-matrix multiplication. Nobody disputes that Strassen etc. have sub-cubic complexity. What about one of the six decompositions mentioned, as GP claimed?

I responded to a post about the practicality of MM multiplication methods, though GEMM is quite fundamental.
Post reply on HN