Hacker News Reader

Comment by threatripper | Hacker News Reader

The Fourier transformation is a special case of a linear transformation. Linear neural networks can represent any linear transformation. Both can also be expressed as matrix multiplication.

It's not really all that surprising if you know some of the math behind neural networks, matrix algebra, linear transformations or the Fourier transformation.

View on HN

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.

There is the FFT in TensorFlow already: https://www.tensorflow.org/api_docs/python/tf/signal/fft

And FFT (Fast Fourier Transform) is more efficient than matrix multiplication (EDIT: by a matrix with Fourier elements).

This is analogous to saying "an umbrella is better than a toaster". They are two different things.

Not if you perform these operations in order to obtain a Fourier transform.

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

Vandermonde. He was not Dutch, he was French. https://en.wikipedia.org/wiki/Alexandre-Théophile_Vandermond...

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

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

The 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

You can implement a DFT with matrix multiplication using the vandermonde matrix with roots of the unitary polynomial as the basis.

They 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

You know, I'll go out on the limb and say (unhelpfully) that a FFT is more efficient than any general dense matvec.

Bah, 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?

That's really cool. I didn't know they had this, maybe they have a 2 dimensional version as well.

I've come to internalize the Fourier transform as a type of sparse matrix algorithm. I.e. something that implements a particular matrix-vector product without requiring explicit construction of said matrix.

And pushing the parantheses to factor out common subexpressions. Essentially exploiting the distributive law

Do you mean the FFT? I've been trying to wrap my head around the Fourier transform lately, and I can see the matrix connection to an FFT, but not the Fourier transform in general.

The Fourier transform performs a change of basis into the eigenbasis of convolution.

It's linear and so in the discrete case can be expressed as matrix multiplication (every discrete linear operation is expressible as matmul).

On the other hand, if you don't yet know a lot of NN math, like me, it is super surprising. Definitely a cool way to connect FFT and NNs.

Yes but this article shows that the matrix coefficients of the Fourier transform can be learned.

This is also not really surprising for a single layer neural network.

It might not be surprising when they implemented it by supervised learning, but when they also solved it by reconstructing the input it was like a rediscovery.

That's because "learning" in neural networks is a fancy way of saying "curve fitting."

Reply on news.ycombinator.com