Lattice discrete Fourier transforms

[Niles]

Homework Statement

Hi

Say I have a 5x5 lattice, where each entry (or we can call it site) contains the number 1. Now, on the lattice we have a function g(R), which is equal to the number on the site. In this case g(R)=1 for all sites (here R is a vector from the point (3,3), which denotes the site we are talking about).

Now I wish to Fourier transform the function g, and I use the lattice discrete FT

<br /> f(\mathbf{k}) = \sum_{\mathbf{R} } e^{i \mathbf{k} \cdot \mathbf{R} } g(\mathbf{R})<br />

where k is a vector. Now, since each site contains the number 1, the system is homogeneous, and from the inverse Fourier transform,

<br /> g(\mathbf R) = \sum_{\mathbf k} e^{-i\mathbf k\mathbf R} f(\mathbf k),<br />

we see that only the k=0-term can survive, since g(R) is constant. But by performing the sum

<br /> f(\mathbf{k}) = \sum_{\mathbf{R} } e^{i \mathbf{k} \cdot \mathbf{R} } g(\mathbf{R}),<br />

it is quite obvious that all terms are there, i.e. it is not only the k=0 term that survives. That is a paradox I cannot explain. Can you guys shed some light on this?Niles.

 

[jbunniii]

Your exponents are missing some factors. Instead of

e^{-ik\cdot R}

it should be

e^{-2\pi i k \cdot R / N}

where in your case N = 5.

Then for k \neq 0 you will be summing evenly spaced samples around the unit circle, so the result will be zero.

 

[jbunniii]

P.S. Since your function is constant, the 2d DFT is equivalent to two iterated 1d DFT's. If I write k = (k_1, k_2) and R = (R_1, R_2), then

f(k) = \sum_R e^{2\pi i (k_1 R_1 + k_2 R_2) / N} = \sum_{R_1} e^{2\pi i k_1 R_1 / N} \sum_{R_2} e^{2\pi i k_2 R_2 / N}

 

[Niles]

Thanks for helping. I just tried doing it again (with the correct factor in the exponential) for a 3x3 system, but still other terms show up (I tried writing it up manually).

 

[Niles]

I'm sorry to bump the thread, but it is extremely important that this issue gets solved (I potentially have to redo 6 months of course work), and I am all out of good ideas.

 

[jbunniii]

I'm not sure what is going wrong for you. Maybe I am misinterpreting what you want to do. I wrote the following segment of Matlab code (actually Octave, but it should work for Matlab as well) to calculate your sum:

fid = fopen('out.txt','w');

for a = -2:2
    for b = -2:2
        k = [a b];
        f_k = 0;
        for m = -2:2
            for n = -2:2
                r = [m n];
                f_k = f_k + exp(i*2*pi * (k * r') / 5);
            end
        end
        fprintf(fid, 'f([%d %d]) = %f + i*%f\n', a, b, real(f_k), imag(f_k));
    end
end

fclose(fid);

Here is the result I got:

f([-2 -2]) = 0.000000 + i*0.000000
f([-2 -1]) = -0.000000 + i*0.000000
f([-2 0]) = -0.000000 + i*0.000000
f([-2 1]) = -0.000000 + i*-0.000000
f([-2 2]) = 0.000000 + i*0.000000
f([-1 -2]) = -0.000000 + i*0.000000
f([-1 -1]) = -0.000000 + i*0.000000
f([-1 0]) = 0.000000 + i*-0.000000
f([-1 1]) = -0.000000 + i*-0.000000
f([-1 2]) = 0.000000 + i*0.000000
f([0 -2]) = -0.000000 + i*0.000000
f([0 -1]) = 0.000000 + i*0.000000
f([0 0]) = 25.000000 + i*0.000000
f([0 1]) = 0.000000 + i*0.000000
f([0 2]) = -0.000000 + i*0.000000
f([1 -2]) = 0.000000 + i*0.000000
f([1 -1]) = -0.000000 + i*0.000000
f([1 0]) = 0.000000 + i*0.000000
f([1 1]) = -0.000000 + i*-0.000000
f([1 2]) = -0.000000 + i*0.000000
f([2 -2]) = 0.000000 + i*0.000000
f([2 -1]) = -0.000000 + i*0.000000
f([2 0]) = -0.000000 + i*0.000000
f([2 1]) = -0.000000 + i*0.000000
f([2 2]) = 0.000000 + i*0.000000

 

[Niles]

I'm not sure what is going wrong for you. Maybe I am misinterpreting what you want to do.

No no, you got it. What I want to do is to find f(k). But you change the value of the k-vector? Why is it that you do that, instead of leaving it just as (k_x,k_y)?

 

[Niles]

Wait, ignore my post #7. I will try out your example, and return when I get a result.

 

[Niles]

Ok, now I get the same table as you. But the problem comes when we choose e.g. k=(0, 1.5)^T - there f(k) blows up (I get f(k)=6.18 in that case).

 

[jbunniii]

Ok, now I get the same table as you. But the problem comes when we choose e.g. k=(0, 1.5)^T - there f(k) blows up (I get f(k)=6.18 in that case).

Yes, if you look at points that do not have integer coordinates, you will not get zero. In fact, if you evaluate f at all points (instead of just integers), you will obtain a 2-dimensional "sinc" function.

The reason for this is that you only use finitely many terms in the sum. You are in effect calculating the Fourier transform of a 2-dimensional "rectangle" function.

If you use more terms, you will more closely approximate an "impulse."

See here for a visualization:

http://cnyack.homestead.com/files/artran/ft2dxy1.htm