search

scijs / ndarray-fft

FFT for ndarrays
MIT License
48 stars 3 forks source link

FFT with real-valued input #5

Open rreusser opened 8 years ago

rreusser commented 8 years ago

Do you have a sense for the complexity of forking this and specializing it for real-valued input? Is it a matter of substituting zeros and carefully cutting out half of the calculations? It accounts for the vast majority of my FFT usage and is simpler to deal with, so would love to pull this off, if possible.

milcktoast commented 5 years ago

I've been looking around for a fast JS implementation of this as well, and came upon j-funk/corbanbrook-fft which seems correct and quite performant from my initial testing. Maybe it would be useful to create a scijs fork for maintenance and discovery?

Realized this partially exists at scijs/fourier-transform. It doesn't operate on ndarray, but is optimized for 1D real-valued input.

dy commented 5 years ago

@jpweeks yes, that also lacks inverse version, also that returns magnitudes, there is a room for enhancement for sure.

rreusser commented 5 years ago

I did manage to get a strictly real-valued invertible fft working here: https://github.com/rreusser/glsl-rfft, though it combines two signals and then uses symmetry to separate the positive frequency part of the fft at the end, so I don't think it works if you have less than two signals. (But if you do, it's super useful and The FFT on a GPU describes how.) (Related is that if you have two real-valued signals, you can often combine them into realSignal1 + i * realSignal2 and still just complex-fft, filter and invert with the same amount of work as two real-valued ffts, e.g. gaussian blur or a frequency filter without a phase shift)

Otherwise yeah, it'd be awesome to find an existing implementation and work with it.

Just to recap, correct me if I'm wrong but in general if you compute the complex fft of real-valued data, the negative frequencies are just the complex conjugate of the positive frequencies, meaning they're redundant and you can drop them without losing data or invertibility. Which means, as stated above, I'm half suspicious this might be possible just by cutting the loops in half and fixing the indices since any missing data is already available elsewhere. Seems too complicated and tedious to try that naively though, so if there's a forkable implementation, 🍴!