Re: Discrete Fourier Transform. Symmetry question

Ian ...

I posted my thanks before. More usefully, I wanted to add that in light of
your comments I have now experimented with doing the 2-d FFT in stages; FFT
each row, transpose, FFT each row, transpose back. It is very much clearer
what is happening and, since I understand the 1-D transform well enough, I
also understand what *each* of the entries is telling me.

Thanks again.

Mark
"Ian Parker" <ianparker2@xxxxxxxxx> wrote in message
news:ae6206f5-5f4c-48b1-9c43-61b1bca8048e@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On 12 Mar, 11:22, "Diamond, Mark" <d...@xxxxxxx> wrote:
I use this example to frame the question that follows, with the sublists
representing matrix rows ...
img={{4, 7, 1, 4}, {6, 0, 7, 5}, {7, 1, 2, 2}, {4, 0, 1, 7}}
fftImg={{14.5, 2.5-2.5I, 1.5, 2.5+2.5I}, {1+1.5I, -1, -3+2.5I, -2I},
{-0.5,
1.5+3.5I, -1.5, 1.5-3.5I}, {1-1.5I, 2I, -3-2.5I, -1}}

Could someone please tell me what the symmetry constraints are on a 2-D
Fourier transform given a real-valued input. Put another way, if I
*construct* the 2-D transform, what symmetry relationships must I enforce
to
guarantee that the inverse transform is real . It's clear enough to me in
the 1-D case (Conjugate[x_k] == x_{n-k}). From looking at the example,
that
symmetry condition seems to hold on each row of the DFT as well. It does
not, however, appear to be a sufficient condition to produce a real
inverse
of the fftImg (or have I messed something up)? Is there some sort of
similar
constraint on the *columns* that is not obvious to me? And lastly, while
its
clear what the value 14.5 represents, it isn't clear to me what the first
value in each row indicates?

While it would be nice if you're willing to answer the questions, a
pointer
to a suitable text might substitute!

Many thanks.

Mark Diamond

I think we should start with a one dimensional real. On transformation
f(n) = f(N+1-n)* (* = complex conjugate) f(0) and f(N/2) are both
real. Now to take a 2D transform we transform left/right and then up/
down. Hence transforming the 0 and N/2 we arrive at precisely the same
as before, after all we have simply taken two one dimensional
transforms.

For the symmetry of the other terms it should be noted that the FT of
an imaginary vector is f(n) = -f(N+1-n)* We can thus develop a
relationship as follows.

let A B be the n,m N+1-n,m
C D n,M+1-m N+1-n,M+1-m

A+B = (C+D)* and (A-B)=-(C-D)*


- Ian Parker


.