search

elixir-nx / nx

Multi-dimensional arrays (tensors) and numerical definitions for Elixir
2.66k stars 194 forks source link

Guide fft #1559

Open ndrean opened 1 week ago

ndrean commented 1 week ago

First commit

ndrean commented 10 hours ago

I wonder why FFT and conv are in Nx and not in NxSignal ??

Now that this aperitif is almost done, I feel it is more interesting to play with the convolution, which most probably uses FFT, I will (try to) check. I read the doc, pretty terse. You have things like padding and sliding windows with strides but not sure how it wroks. I would build a little example for example applied on a simple and small image and use 3 or 4 kernels (say horizontal edge, vertical edge, gaussian blur). I don't think its huge, not even sure if the image will render correctly. Is this interesting for you? I may need examples to see and test what this function does exactly. MAybe if you point me directly where they are, could save me time.

polvalente commented 10 hours ago

I wonder why FFT and conv are in Nx and not in NxSignal ??

Now that this aperitif is almost done, I feel it is more interesting to play with the convolution, which most probably uses FFT, I will (try to) check. I read the doc, pretty terse. You have things like padding and sliding windows with strides but not sure how it wroks. I would build a little example for example applied on a simple and small image and use 3 or 4 kernels (say horizontal edge, vertical edge, gaussian blur). I don't think its huge, not even sure if the image will render correctly. Is this interesting for you? I may need examples to see and test what this function does exactly. MAybe if you point me directly where they are, could save me time.

Awesome. I will ping you regarding convolutional filters, as I've just given a talk on that! This is the repo if you want to take a look already: https://github.com/polvalente/code-beam-lite-nyc-2024

Regarding fft and conv being in Nx, ultimately the reason is that they are present in the XLA API, really.

And NxSignal is a library that currently only implements things through calling Nx itself. Think of Nx as being analogous to NumPy, while NxSignal is a subsection of SciPy.

Finally, conv is an operation in itself and can be implemented in the time domain. Nx doesn't build it on top of FFT.

ndrean commented 10 hours ago

Ah! I recall I had a little home work on cyclotomic polynomials and FFT for polynomial products (a convolution in fact) but was a long time ago.

So if you already did it, I can only will bring in a kinda noob POV! Thanks for the link, I will run it.

polvalente commented 10 hours ago

Ah! I recall I had a little home work on cyclotomic polynomials and FFT for polynomial products (a convolution in fact) but was a long time ago.

So if you already did it, I can only will bring in a kinda noob POV! Thanks for the link, I will run it.

The talk wasn't recorded, and putting it in a livebook format would be great!

To be clear, FFT can execute the convolution (with some restrictions) but it's important to keep in mind that each is its own primitive in Nx

ndrean commented 9 hours ago

In Scipy, I just had a look, there make some quick calculations to predict which method, direct or via FFT, is faster.

https://github.com/scipy/scipy/blob/92d2a8592782ee19a1161d0bf3fc2241ba78bb63/scipy/signal/_signaltools.py#L1165

and conv = IFFT( FFT x FFT(conjugate).

But for later!