7 ms·
I dont think its surprising but its definitely a cool little exercise. Somewhat aside of the content of the post, I could see some use cases where specifically
by amcoastal 5y ago
I dont think its surprising but its definitely a cool little exercise. Somewhat aside of the content of the post, I could see some use cases where specifically implementing DFT layers in your architectures could lead to improved performance over using just the raw inputs or activations. Noisy datasets, or synthetic data based transfer learning come to mind as potential uses for the DFT as a step in your ML pipeline.
- threatripper 5y agoThere is the FFT in TensorFlow already: https://www.tensorflow.org/api_docs/python/tf/signal/fft https://www.tensorflow.org/api_docs/python/tf/signal/fft
- amelius 5y agoAnd FFT (Fast Fourier Transform) is more efficient than matrix multiplication (EDIT: by a matrix with Fourier elements).
- mochomocha 5y agoThis is analogous to saying "an umbrella is better than a toaster". They are two different things.
- ok123456 5y agoYou can implement a DFT with matrix multiplication using the vandermonde matrix with roots of the unitary polynomial as the basis.
- amelius 5y agoNot if you perform these operations in order to obtain a Fourier transform.
- cdavid 5y agoFourier transform, more exactly DFT, is a special case of matrix multiplication, when seen as a linear operator. The fact that you can do operations faster than the usual N*2 matrix / vector operation is due to the specific form of the underlying matrix (Van Der Mont matrix). So they are not that different: the specific structure of the Fourier basis allows for more efficient matrix * vector operation.
- deleted 5y ago[deleted]
- layoutIfNeeded 5y agoVandermonde. He was not Dutch, he was French. https://en.wikipedia.org/wiki/Alexandre-Théophile_Vandermonde https://en.wikipedia.org/wiki/Alexandre-Théophile_Vandermond...
- Joker_vD 5y agoWhy do people insist on comparing only things that are same? The same things are same, no point whatsoever comparing them: they're same! No, you should only compare things that are different, that way you learn more about their differences. And what's better, an umbrella or a toaster, depends on the one's goals: if one'd like to fry some bread, toaster is more useful; if one'd like to cover from rain, umbrella is far superior, although toaster could used be too; if one'd like to drive a nail into the wall, toaster again is better; etc.
- mochomocha 5y agoMy statement was as approximate as the one I was replying to. If the original statement had been "you can use FFT to implement some operations involving matrix multiplication faster" I wouldn't have taken issue with it. But saying "FFT is faster than matrix multiplication" has little meaning.
- vladTheInhaler 5y agoThe naive implementation of the DFT in terms of a matrix-vector multiplication has time complexity O(n^2) [1]. The point is that the FFT approach is much faster than that implementation. [1] https://en.wikipedia.org/wiki/DFT_matrix https://en.wikipedia.org/wiki/DFT_matrix
- hamiltonkibbe 5y agoThey are different things, but you can use both to protect you from the rain, and an umbrella does that more efficiently than a toaster. The drawback is that the umbrella doesn't generalize to the broader field of bagel toasting
- bigbillheck 5y agoYou know, I'll go out on the limb and say (unhelpfully) that a FFT is more efficient than any general dense matvec.
- touisteur 5y agoBah, when you've maxxed out your cuda cores, who's to prevent you from reaching for those sweet tensor core 100+ tflops mat-mul now?
- amcoastal 5y agoThat's really cool. I didn't know they had this, maybe they have a 2 dimensional version as well.