3 ms·
There 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
by threatripper 5y ago
There 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.