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

Multiplying Matrices Without Multiplying

arxiv.org

Post reply on HN
Print view View original

31–40 of 124 posts

Re: Multiplying Matrices Without Multiplying

#31

Post by cs702 »

Every element of a matrix multiplication is a dot-product of two vectors. The dot-product of two vectors quantifies their similarity -- in fact, we call it "dot-product similarity" in a nearest-neighbors context: If the dot product > 0, the vectors point in similar directions; if It's not too hard to imagine that it might be possible to learn representative K-means clusters of training vectors and then, at run-time, find similar vectors using an efficient hashing scheme and do the equivalent of a table lookup to get the approximate dot-product similarity scores -- without having to perform any multiplications.

This isn't quite correct (I'm oversimplifying and ignoring many important details), but I think it's a helpful mental image.

Very clever stuff.

Re: Multiplying Matrices Without Multiplying

#32

Post by PythonNut »

joe_the_user wrote: post #29

Shouldn't the solution to fast matrix multiplication be logarithms, similarly to fast scalar multiplication? https://en.wikipedia.org/wiki/Logarithm_of_a_matrix

Perhaps surprisingly, the matrix logarithm does not satisfy log(A) + log(B) = log(AB) in general (only when AB = BA) which is why you cannot use it to "multiply by adding".

Re: Multiplying Matrices Without Multiplying

#33

Post by antonzabirko »

honie wrote: post #20
antonzabirko wrote: post #8

Had this same exact thought as an undergrad like 3 years ago! I kinda gave up due to the massive barrier and difficult financial burdens faced by phd students. This feels nice to know i wasn't crazy.

I don't disagree with you on the potential financial burdens faced by PhD students but, in this case, and if I haven't missed anything, the infrastructural barrier is not high: > All experi-ments use a single thread on a Macbook Pro with a 2.6GHz Intel Core i7-4960HQ processor. Unless stated otherwise, all timing results use five trials, with each trial reporting the fastest among 20 executions. It may also be worth…

I meant learning barrier. If i had the money i likely would go for it though!

Re: Multiplying Matrices Without Multiplying

#34

Post by adgjlsfhk1 »

PythonNut wrote: post #32
joe_the_user wrote: post #29

Shouldn't the solution to fast matrix multiplication be logarithms, similarly to fast scalar multiplication? https://en.wikipedia.org/wiki/Logarithm_of_a_matrix

Perhaps surprisingly, the matrix logarithm does not satisfy log(A) + log(B) = log(AB) in general (only when AB = BA) which is why you cannot use it to "multiply by adding".

More importantly, matrix logarithms only exist for square matrices.

Re: Multiplying Matrices Without Multiplying

#35

Post by antonzabirko »

ssivark wrote: post #15
antonzabirko wrote: post #8

Had this same exact thought as an undergrad like 3 years ago! I kinda gave up due to the massive barrier and difficult financial burdens faced by phd students. This feels nice to know i wasn't crazy.

Do you mean the exact idea behind MADDNESS or just "ML for multiplying matrices"? The latter doesn't mean much without the former :-)

Not sure how they did it, but basically i thought about reducing things that gained complexity through layers with neural nets. Computer architecture and the layers of complexity between groups of system instructions and function code for example. There have got to be inefficiencies that can be collapsed with the help of ml.

Re: Multiplying Matrices Without Multiplying

#36

Post by infogulch »

I wonder how much alternative number representations have been studied for use in matrices. Like, storing the log of values instead so that multiplication can be done by just adding. Or something like Zech's logarithm. Or even, take the log of whole matrices (which is a thing apparently [0]), then adding them to compute their multiplication. I wonder if the logarithm of a matrix can be computed using ML.

[0]: https://en.wikipedia.org/wiki/Logarithm_of_a_matrix

Re: Multiplying Matrices Without Multiplying

#37

Post by xyzzyz »

cs702 wrote: post #31

Every element of a matrix multiplication is a dot-product of two vectors. The dot-product of two vectors quantifies their similarity -- in fact, we call it "dot-product similarity" in a nearest-neighbors context: If the dot product > 0, the vectors point in similar directions; if It's not too hard to imagine that it might be possible to learn representative K-means clusters of training vectors and then, at run-time,…

The dot-product of two vectors quantifies their similarity -- in fact, we call it "dot-product similarity" in a nearest-neighbors context: If the dot product > 0, the vectors point in similar directions; if

To make it more explicit, dot product of two vectors is just cosine of the angle between them, multiplied by their lengths.

Re: Multiplying Matrices Without Multiplying

#38

Post by xyzzyz »

adgjlsfhk1 wrote: post #34
PythonNut wrote: post #32

Earlier quoted context omitted.

Perhaps surprisingly, the matrix logarithm does not satisfy log(A) + log(B) = log(AB) in general (only when AB = BA) which is why you cannot use it to "multiply by adding".

More importantly, matrix logarithms only exist for square matrices.

That’s not that big of a problem, as you can easily reduce the problem of multiplication of rectangular matrices to multiplication of square ones.

Re: Multiplying Matrices Without Multiplying

#39

Post by mhh__ »

Ar-Curunir wrote: post #26
mhh__ wrote: post #21

Earlier quoted context omitted.

The biggest blocker for me is usually working out how I can implement a given idea without either writing a bunch of code (I'll get bored) or trying to verify if the paper even works for my use case without doing the aforementioned. One field I pay attention to with this problem seems to be abstract interpretation, with my background at least, the methods are very theoretically clean and impressive but actually imple…

Computer Science doesn't mean empirical stuff only, nor does it mean evaluations with code. Theory has its place, and so does systems work. No need to denigrate one or the other.

I was trying to be clear that I was referring to papers which are talking about code they wrote. If you wrote (say) a program to predict the throughput of machine code, then I want to be able to reproduce the results you claim - thats a real example, no hint of any source yet and I've been looking.

If we can't reproduce it isn't really science. I know academics often write bad code and don't like to publish their dirty work, but the buck has to stop somewhere.

Post reply on HN