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

31–40 of 84 posts

Re: The big six matrix factorizations

#31

Post by zodiac »

arinlen wrote: post #30
the_svd_doctor wrote: post #27

Earlier quoted context omitted.

It's always been very ambiguous in practice. To avoid ambiguity I usually use `flop/s` but not everyone likes that :)

> To avoid ambiguity I usually use `flop/s` but not everyone likes that :) Flop/s makes no sense and is outright wrong. The whole point of flops is to express how many floating point operations are required by an algorithm. How many operations are performed per second is a property of the hardware you're using to run an implementation of the algorithm. You want to express computational complexity in terms of floating…

Maybe the_svd_doctor uses flop/s to describe hardware, like you said

Re: The big six matrix factorizations

#32

Post by heinrichhartman »

joppy wrote: post #22
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…

This decomposition is not used much because it is not unique in any sense, it is not numerically stable, and it is fairly uninteresting: the matrix D can always be taken to consist of a diagonal of 1s of length rank(A) and the rest zeros. It is much more interesting once X and Y are constrained to something like unitary matrices (in which case we get SVD). This “rank decomposition” is a bit interesting algebraically…

It's not unique, but it can be implemented in a way that is stable. E.g. SVD does this (but is quite overkill for the requirements).

It's highly relevant from an algebraic perspective, hence it's curious that it's not covered (at all) in the numeric literature.

Re: The big six matrix factorizations

#33

Post by heinrichhartman »

whatshisface wrote: post #21
edflsafoiewq wrote: post #17

Earlier quoted context omitted.

It's basically the matrix form of dim(domain(f)) = dim(ker(f)) + dim(im(f)), or domain(f)/ker(f) ≅ im(f) with f (inducing) the isomorphism.

But the image and kernel are not the only two properties of a matrix.

Sure, but from an algebraic (categorical) perspective, taking kernels, co-kernels and images are the most fundamental operations you can think of.

The question is: How do you compute them in an effective (avoiding full SVD) and stable way?

Re: The big six matrix factorizations

#34

Post by jetbooster »

howlin wrote: post #28

Now apply them to the data used to identify the "Big Five" personality traits! This is an interesting application of factor analysis/matrix factorization: https://en.wikipedia.org/wiki/Big_Five_personality_traits

And then sell it to the Big Four!

https://en.m.wikipedia.org/wiki/Big_Four_accounting_firms

Re: The big six matrix factorizations

#35

Post by whatshisface »

heinrichhartman wrote: post #32
joppy wrote: post #22

Earlier quoted context omitted.

This decomposition is not used much because it is not unique in any sense, it is not numerically stable, and it is fairly uninteresting: the matrix D can always be taken to consist of a diagonal of 1s of length rank(A) and the rest zeros. It is much more interesting once X and Y are constrained to something like unitary matrices (in which case we get SVD). This “rank decomposition” is a bit interesting algebraically…

It's not unique, but it can be implemented in a way that is stable. E.g. SVD does this (but is quite overkill for the requirements). It's highly relevant from an algebraic perspective, hence it's curious that it's not covered (at all) in the numeric literature.

I could be misunderstanding, but I think you'd get all the algebraic content out of it by computing the dimensions of the image and kernel, then working with them from there on. Why would you want to have a matrix decomposition that separated them?

Granted, computing the dimensions of the kernel is not so easy, especially because a pair of vectors can be arbitrarily close without being linearly dependent. No wonder there is no stable way to do it, it technically exceeds the capability of finite-precision numbers. Multiplying a vector of unequal components by most numbers, especially those with non-terminating base-two decimal representations, will produce a vector that is linearly independent when rounded back to finite precision.

Clearly then, linear independence on computers has to be considered in the continuous sense in which singular values reveal it, where a very small singular value represents an "almost-kernel," which is the closest thing to a kernel you are likely to find outside of carefully constructed examples or integer matrices.

Re: The big six matrix factorizations

#37

Post by MatteoFrigo »

the_svd_doctor wrote: post #27
leephillips wrote: post #3

Thank you for this wonderfully concise summary: it’s convenient to have all this in one compact document. I suppose “flops” means “floating-point operations” here? Heretofore I’ve always encountered this as an abbreviation for “floating-point operations per second”.

It's always been very ambiguous in practice. To avoid ambiguity I usually use `flop/s` but not everyone likes that :)

Speaking of SVD doctors, I heard many years ago (from Alan Edelman) that Gene Golub's license plate used to be "DR SVD". Later he switched to "PROF SVD".

I couldn't confirm the DR SVD part, but the PROF SVD story appears to be real: https://www.mathworks.com/company/newsletters/articles/profe...

Re: The big six matrix factorizations

#38

Post by daniel-cussen »

oh_my_goodness wrote: post #10
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.

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. )

https://www.fgemm.com, coming soon.

Re: The big six matrix factorizations

#39

Post by jdeaton »

This is a fantastically clear outline of this topic. Thank you!

> The terms “factorization” and “decomposition” are synonymous and it is a matter of convention which is used. Our list comprises three factorization and three decompositions.

I can't tell if this is a joke: right after saying that these two words mean the same thing in this context, they are then used to categorize the methods.

Edit: This is the kind of content that proves the "dead internet theory" is wrong.

Post reply on HN