Results 1 to 8 of 8

Math Help - 2D discrete Fourier transform

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    49

    2D discrete Fourier transform

    Hi guys

    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

    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,

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

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

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

    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?

    Best,
    Niles.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Niles_M View Post
    Hi guys

    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

    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,

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

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

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

    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?

    Best,
    Niles.
    Let me preface this post by saying that I have absolutely no experience with Fourier transforms, but I saw your other post describing your urgency, etc., so I decided to post this in the event that it turns out to be useful.

    This link on Wikipedia is for the section entitled Expressing the inverse DFT in terms of the DFT as part of the article Discrete Fourier transform. Without experience, I cannot determine whether or not this applies to your situation, but it seemed there was a chance.

    Good luck.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2008
    Posts
    49
    Thanks, I'll take a look at it to see if it helps. I feel bad asking this, but do you know of the best way of directing attention to this post?

    By the way, I am doing this numerically. Is it because I need to look at large systems in order to see only the k=0 contribution?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Niles_M View Post
    Thanks, I'll take a look at it to see if it helps. I feel bad asking this, but do you know of the best way of directing attention to this post?
    Sorry, I don't know. Maybe a moderator will be able to give some useful info in that regard. From what I gather, you are very considerate when it comes to rules and such, and are merely in an unusual situation and don't know what to do, so I would expect a friendly response from moderators.

    Quote Originally Posted by Niles_M View Post
    By the way, I am doing this numerically. Is it because I need to look at large systems in order to see only the k=0 contribution?
    I hope this wasn't directed towards me, because again I cite my lack of knowledge/experience. I'm writing this additional note just so you know I didn't ignore it.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2008
    Posts
    49
    Thanks, it is very kind of you. I contacted a moderator.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    One last note, which may or may not be useful; I noticed the Wikipedia article is written in terms of complex numbers, and in case there was an issue with this, complex numbers can be treated in the same way ordered pairs are treated, in many ways. a + bi could be a way of expressing the ordered pair (a, b), similar to how in nonnegative integers 2^a3^b can encode (a, b) as a nonnegative integer. Of course there are things like complex conjugates which may or may not change things. Just an idea.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Niles_M View Post
    Hi guys

    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

    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,

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

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

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

    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?
    It is not really a paradox, because all the entries in the original matrix g(R) are the same (they are all equal to 1). So the single piece of information given by the k=0 term is sufficient to re-create the matrix.

    If g(R) had contained two or more distinct entries then the FT would have contained more than one nonzero term.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Oct 2008
    Posts
    49
    "So the single piece of information given by the k=0 term is sufficient to re-create the matrix."

    I agree with that, but when I carry out the sum

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

    then all k-terms are there, so f(k) also has k!=0 terms (which is should not, since it is homogeneous). That is what I call the paradox.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Discrete Fourier Transform implementation
    Posted in the Advanced Math Topics Forum
    Replies: 3
    Last Post: March 8th 2011, 05:05 PM
  2. Discrete Fourier Transform (DFT).
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: November 27th 2010, 10:45 PM
  3. [SOLVED] Discrete fourier transform
    Posted in the Differential Geometry Forum
    Replies: 12
    Last Post: November 9th 2010, 10:19 AM
  4. Discrete Fourier Transform
    Posted in the Calculus Forum
    Replies: 0
    Last Post: September 10th 2010, 06:36 AM
  5. Eigenvectors for the discrete fourier transform
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: December 2nd 2009, 03:16 AM

Search Tags


/mathhelpforum @mathhelpforum