3
$\begingroup$

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

1 Answers 1

2

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.