FFT of a real symmetric vector is not real and symmetric

Question

I am having a hard time understanding what should be a simple concept. I have constructed a vector in MATLAB that is real and symmetric. When I take the FFT in MATLAB, the result has a significant imaginary component, even though the symmetry rules of the Fourier transform say that the FT of a real symmetric function should also be real and symmetric. My example code:

N = 1 + 2^8;
k = linspace(-1,1,N);

V = exp(-abs(k));

Vf1 = fft(fftshift(V));
Vf2 = fft(ifftshift(V));
Vf3 = ifft(fftshift(V));
Vf4 = ifft(ifftshift(V));
Vf5 = fft(V);
Vf6 = ifft(V);

disp([isreal(Vf1) isreal(Vf2) isreal(Vf3) isreal(Vf4) isreal(Vf5) isreal(Vf6)])

Result:

0 0 0 0 0 0

No combinations of (i)fft or (i)fftshift result in a real symmetric vector. I've tried with both even and odd N (N = 2^8 vs. N = 1+2^8).

I did try looking at k+flip(k) and there are some residuals on the order of eps(1), but the residuals are also symmetric and the imaginary part of the FFT is not coming out as fuzz on the order of eps(1), but rather with magnitude comparable to the real part.

What blindingly obvious thing am I missing?

Blindingly obvious thing I was missing:

The FFT is not an integral over all space, so it assumes a periodic signal. Above, I am duplicating the last point in the period when I choose an even N, and so there is no way to shift it around to put the zero frequency at the beginning without fractional indexing, which does not exist.

A word about my choice of k. It is not arbitrary. The actual problem I am trying to solve is to generate a model FTIR interferogram which I will then FFT to get a spectrum. k is the distance that the interferometer travels which gets transformed to frequency in wavenumbers. In the real problem there will be various scaling factors so that the generating function V will yield physically meaningful numbers.

Hawsepiece

I ran your code and got the output 0 1 0 1 0 0. Still reading your question. – Frye

Answer 1

@Yvon is absolutely right with his comment about symmetry. Your input signal looks symmetrical, but it isn't because symmetry is related to origin 0. Using linspace in Matlab for constructing signals is mostly a bad choice. Trying to repair the results with fftshift is a bad idea too.

Use instead:

k = 2*(0:N-1)/N - 1;

and you will get the result you expect. However the imaginary part of the transformed values will not be perfectly zero. There is some numerical noise.

>> max(abs(imag(Vf5)))
ans =
2.5535e-15

Answer to Yvon's question:

Why? >> N = 1+2^4 N = 17 >> x=linspace(-1,1,N) x = -1.0000 -0.8750 -0.7500 -0.6250 -0.5000 -0.3750 -0.2500 -0.1250 0 0.1250 0.2500 0.3750 0.5000 0.6250 0.7500 0.8750 1.0000 >> y=2*(0:N-1)/N-1 y = -1.0000 -0.8824 -0.7647 -0.6471 -0.5294 -0.4118 -0.2941 -0.1765 -0.0588 0.0588 0.1765 0.2941 0.4118 0.5294 0.6471 0.7647 0.8824 – Yvon 1

Your example is not a symmetric (even) function, but an antisymmetric (odd) function. However, this makes no difference.

For a antisymmetric function of length N the following statement is true:

f[i] == -f[-i] == -f[N-i]

The index i runs from 0 to N-1.

Let us see was happens with i=2. Remember, count starts with 0 and ends with 16.

x[2] = -0.75
-x[N-2] == -x[17-2] == -x[15] = (-1) 0.875 = -0.875
x[2] != -x[N-2]

y[2] = -0.7647
-y[N-2] == -y[15] = (-1) 0.7647
y[2] == y[N-2]

The problem is, that the origin of Matlab vectors start at 1. Modulo (periodic) vectors start with origin 0. This difference leads to many misunderstandings.

Another way of explanation why linspace(-1,+1,N) is not correct:

Imagine you have a vector which holds a single period of a periodic function, for instance a Cosinus function. This single period is one of a infinite number of periods. The first value of your Cosinus vector must not be same as the last value of your vector. However,that is exactly what linspace(-1,+1,N) does. Doing so, results in a sequence where the last value of period 1 is the same value as the first sample of the following period 2. That is not what you want. To avoid this mistake use t = 2*(0:N-1)/N - 1. The distance t[i+1]-t[i] is 2/N and the last value has to be t[N-1] = 1 - 2/N and not 1.

Answer to Yvon's second comment

Whatever you put in an input vector of a DFT/FFT, by theory it is interpreted as a periodic function. But that is not the point.

DFT performs an integration.

fft(m) = Sum_(k=0)^(N-1) (x(k) exp(-i 2 pi m k/N )

The first value x(k=0) describes the amplitude of the first integration interval of length 1/N. The second value x(k=1) describes the amplitude of the second integration interval of length 1/N. And so on.

The very last integration interval of the symmetric function ends with same value as the first sample. This means, the starting point of the last integration interval is k=N-1 = 1-1/N. Your input vector holds the starting points of the integration intervals.

Therefore, the last point of symmetry k=N is a point of the function, but it is not a starting point of an integration interval and so it is not a member of the input vector.

Sera

No. 1) DFT is a sum, not integral. 2) The grid points k is a seed used to evaluate function values exp(-abs(k)). They are not used as time value by fft. 3) The periodicity does not matter at all because we can treat any piece of signal as at least one period. – Frye

Finally! I got your idea! It did not raise any problem in OP question, since in either way we have a periodic signal. But YES you are right, provided that we only want ONE instead of two exp(1) points at each peak. Very much thanks!!! Again, DFT is a sum; it does not have any concept of "integration interval". – Frye

@Frye DFT is the development von Fourier Transformation in the continuous space to a time discrete space. So, the infinite integral is substituted by a finite sum. However, remember the trapezodiod integration from numerical mathematics lectures and you will discover the relationship to DFT sums. – Sera

@Yvon's point a few comments up is key to my problem, in that k is not a time but the index for the function, so it does matter that it goes from -1 to 1 (in the real problem there will be scaling). The Fourier transform of which should be a Lorentzian function and should be real. You are absolutely correct, though, that I am, in essence, duplicating the first and last points in a periodic function and that is what is screwing me up. – Hawsepiece

Answer 2

It's

Vf = fftshift(fft(ifftshift(V)));

That is, you need ifftshift in time-domain so that samples are interpreted as those of a symmetric function, and then fftshift in frequency-domain to again make symmetry apparent.

This only works for N odd. For N even, the concept of a symmetric function does not make sense: there is no way to shift the signal so that it is symmetric with respect to the origin (the origin would need to be "between two samples", which is impossible).

For your example V, the above code gives Vf real and symmetric. The following figure has been generated with semilogy(Vf), so that small as well as large values can be seen. (Of course, you could modify the horizontal axis so that the graph is centered at 0 frequency as it should; but anyway the graph is seen to be symmetric.)

Lackadaisical

I must have neglected to clear the variable space when I re-ran with N odd, and I do get the result you have here. However, when I run with N even, I still get imaginary results. I assume that is because I no longer technically have a zero frequency component. Any advice on how to account for that? Do I have to construct my k-vector to always include the 0 frequency case? – Hawsepiece

Think about it: a signal with an even number of samples cannot be symmetric about the origin. The origin would have to be "between two samples", but that just doesn't make sense You need an odd number of samples for the signal to be symmetric, i.e. an even function in the mathematical sense – Lackadaisical

Answer 3

You have a problem when implementing the concept "symmetry". A purely real, even (or "symmetric") function has a Fourier transform function that is also real and even. "Even" is the symmetry with respect to the y-axis, or the t=0 line.

When implementing a signal in Matlab, however, you always start from t=0. That is, there is no way to "define" the signal starting from before the origin of time.

Searching the Internet for a while lead me to this - Correct use of fftshift and ifftshift at input to fft and ifft.

As Luis has pointed out, you need to perform ifftshift before feeding the signal into fft. The reason has never been documented in Matlab, but only in that thread. For historical reasons, outputs AND inputs of fft and ifft are swapped. That is, instead of ordered from -N/2 to N/2-1 (the natural order), the signal in time or frequency domain is ordered from 0 to N/2-1 and then -N/2 to -1. That means, the correct way to code is fft( ifftshift(V) ), but most people ignore this at most times. Why it's got silently ignored rather than raising huge problems is that most concerns have been put on the amplitude of signal, not phase. Since circular shifting does not affect amplitude spectrum, this is not a problem (even for the Matlab guys who have written the documentations).

To check the amplitude equality -

Vf2 = fft(ifftshift(V));
Vf5 = fft(V);
Va2 = abs(fftshift(Vf2));
Va5 = abs(fftshift(Vf5));

>> min(abs(Va2-Va5)<1e-10)

ans =

     1

To see how badly wrong in phase -

Vp2 = angle(fftshift(Vf2));
Vp5 = angle(fftshift(Vf5));

Anyway, as I wrote in the comment, after copy&pasting your code into a fresh and clean Matlab, it gives 0 1 0 1 0 0.

To your question about N=even and N=odd, my opinion is when N=even, the signal is not symmetric, since there are unequal number of points on either side of the time origin.

Frye

The FFT without any shift is quite natural: you have time samples at 0,..., N-1 (in that order), and get N frequencies from 0 to the maximum frequency. The shifts are only necessary if we want to shift the origin to the middle. The order -N/2 to N/2-1 is not any more natural than 0, ..., N-1, as I see it – Lackadaisical

Answer 4

Just add the following line after "k = linspace(-1,1,N);"

k(end)=[];

it will remove the last element of the array. This is defined to be symmetric array.

also consider that isreal(complex(1,0)) is false!!! The isreal function just checks for the memory storage format. so 1+0i is not real in the above example.

You have define your function in order to check for real numbers (like this)

myisreal=@(x) all((abs(imag(x))<1e-6*abs(real(x)))|(abs(x)<1e-8));

Finally your source code should become something like this:

N = 1 + 2^8;
k = linspace(-1,1,N);

k(end)=[];

V = exp(-abs(k));


Vf1 = fft(fftshift(V));

Vf2 = fft(ifftshift(V));
Vf3 = ifft(fftshift(V));
Vf4 = ifft(ifftshift(V));
Vf5 = fft(V);
Vf6 = ifft(V);

myisreal=@(x) all((abs(imag(x))<1e-6*abs(real(x)))|(abs(x)<1e-8));

disp([myisreal(Vf1) myisreal(Vf2) myisreal(Vf3) myisreal(Vf4) myisreal(Vf5) myisreal(Vf6)]);

Atrophied