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
Best Answer
Real input compared to complex input contains half that information(since the zero padded part contains no information). The output is in the complex form, that means a double size container for the real input. So from the complex output we can naturally eliminate the duplicate part without any loss. I tried to be as simple as possible.