I know that when I perform a real to complex FFT half the frequency domain data is redundant due to symmetry. This is only the case in one axis of a 2D FFT though. I can think of a 2D FFT as two 1D FFT operations, the first operates on all the rows, and for a real valued image this will give you complex row values. In the second stage I apply a 1D FFT to every column, but since the row values are now complex this will be a complex to complex FFT with no redundancy in the output. Hence I only need width / 2 points in the horizontal axis, but you still need height points in the vertical axis. (thanks to Paul R)
My question is: I read that the symmetry is just "every term in the right part is the complex conjugated of the left part"
I have a code that I know for sure that is right that does this:
- take a real matrix as input -> FFT -> stores JUST half width (half coefficients, the nonredundant ones) but full height
- perform a pointwise-multiplication (alias circular convolution in time, I know, the matrices are padded) with another matrix
- Return with a IFFT on the half-width and full height matrix -> to real values. And that's the convolution result.
Why does it work? I mean: the conjugated complex numbers skipped (the negative frequencies) aren't of any use to the multiplication? Why is that?
To ask this as simple as I can: why do I discard half of the complex data from a real FFT to perform calculations? Aren't they important too? They're complex conjugated numbers afterall