The big six matrix factorizations
nhigham.com
The big six matrix factorizations
1–10 of 84 posts
Re: The big six matrix factorizations
#2The 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.
Re: The big six matrix factorizations
#3Thank 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”.
Re: The big six matrix factorizations
#4Any suggestions on what to learn in Linear Algebra after Gilbert Strang’s 18.06SC?
https://ocw.mit.edu/courses/18-06sc-linear-algebra-fall-2011...
My goal is to learn the math behind machine learning.
Re: The big six matrix factorizations
#5Any suggestions on what to learn in Linear Algebra after Gilbert Strang’s 18.06SC? https://ocw.mit.edu/courses/18-06sc-linear-algebra-fall-2011... My goal is to learn the math behind machine learning.
Here are some links from my favourite reference website:
Book: Mathematics for Machine Learning (mml-book.github.io) https://news.ycombinator.com/item?id=16750789
Mathematics for Machine Learning [pdf] (mml-book.com) https://news.ycombinator.com/item?id=21293132
Mathematics of Machine Learning (2016) (ibm.com) https://news.ycombinator.com/item?id=15146746
Re: The big six matrix factorizations
#6Any suggestions on what to learn in Linear Algebra after Gilbert Strang’s 18.06SC? https://ocw.mit.edu/courses/18-06sc-linear-algebra-fall-2011... My goal is to learn the math behind machine learning.
[deleted]
Re: The big six matrix factorizations
#7Any suggestions on what to learn in Linear Algebra after Gilbert Strang’s 18.06SC? https://ocw.mit.edu/courses/18-06sc-linear-algebra-fall-2011... My goal is to learn the math behind machine learning.
These lectures are fantastic after you've mastered the basics of linear algebra https://www.youtube.com/watch?v=McLq1hEq3UY (convex optimization, by a very experienced and often funny lecturer)
Re: The big six matrix factorizations
#8The 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.
They're all basically O(M(n)) where M(n) is your matrix multiplication time. Even though M(n)<=n^2.3...., it's reasonable to say that it's n^3, because in practice, no one uses the sub-cubic algorithms. Strassen is possibly workable, but it isn't widely used, and all of the sub-cubic algorithms have accuracy tradeoffs.
Re: The big six matrix factorizations
#9The 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.
> but practical algorithms with better exponents exist for all of them.
I'm aware of randomized algorithms with better complexity, which come at the cost of only giving approximate results (though the approximation may be perfectly good for practical purposes). See e.g. [1]. Are there other approaches?
Re: The big six matrix factorizations
#10The 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. )