I'm currently trying to do some Fourier transformations, or at least trying to understand them. The only thing I'm worried about is the complex part of the function. All I have is some basic, self thought, understanding about complex numbers.

As far as I'm concerned, a complex number exists of a real part and a complex part. In the following DFT it seems it has no real part. Is that correct?

alt text

I think we can simplify it to the following, since the others are just modifiers.


But for some reason, im not getting the good value's. Perhaps i'm doing something wrong, but im not quite sure.


I just realised this may be a bit vague, but my questions are

  1. Does the function F(k,l) return a complex number, with no real part.
  2. Is there a special rule about $e^{-i}$


Okay, I'm sorry for asking these basic questions, this is all way beyond the math I've learned at school xD. But I understand most of the DFT now. Only there's one thing I don't understand and that:

  1. What does the $F(k,l)$ part of the function define.
  • $\begingroup$ You should edit that to read a real part and an imaginary part. Complex is the number as a whole. $\endgroup$ – Raskolnikov Dec 1 '10 at 18:17
  • $\begingroup$ If you give your DFT/FFT routine an array whose elements are $f(i,j)$, the routine will return an array where each $f(i,j)$ is replaced by $F(i,j)$ (i.e., your data's Fourier transform). $\endgroup$ – J. M. isn't a mathematician Dec 3 '10 at 8:51
  • $\begingroup$ Okay, since I don't see how that practically works. Lets say I have a matrix with 4 entries in it. So I have F(0,0), F(1,0), F(0,1) and F(1,1). For every pixel in the matrix, I'd have to calculate the DFT. Doesn't it give it a complexity of $O(N^4)$ instead of $O(N^2)$ $\endgroup$ – Timo Willemsen Dec 3 '10 at 8:54

Your sum has both real and imaginary parts. Because

$$e^{ix}= \cos(x) + i \sin(x) \; .$$

Is $f(a,b)$ in your formula a real number? Then the transform has real and imaginary components in general. (For certain choices of $f(a,b)$, you can have purely real numbers.)

If you mean $e^{-i}$, then use the formula I provided you and you should be able to compute it.

| cite | improve this answer | |
  • $\begingroup$ Thanks a lot, I wasn't aware that $e^{ix} = cos(x) + i sin(x)$ $\endgroup$ – Timo Willemsen Dec 1 '10 at 18:54
  • 1
    $\begingroup$ @Timo: You might be interested in this other question: math.stackexchange.com/questions/3510/…. $\endgroup$ – Hans Lundmark Dec 1 '10 at 19:22
  • 3
    $\begingroup$ @Timo: Additionally, if $f$ is real, $F$ will have a number of redundant components; you can in fact exploit the symmetry of FFT with real inputs so that only the non-redundant parts are computed (and the computation time is at least halved). $\endgroup$ – J. M. isn't a mathematician Dec 2 '10 at 11:04
  • 2
    $\begingroup$ @Timo: Nope. Try constructing a table of sines and cosines and you'll see for yourself that there's an awful lot of repeated data (only differing up to sign). That's because of the relationships satisfied by the sine and cosine. $\endgroup$ – J. M. isn't a mathematician Dec 3 '10 at 7:11
  • 1
    $\begingroup$ In fact, quite a number of well-tuned FFT programs internally cache a bunch of frequently-used trig function values in an array, since array accesses are usually cheaper than computing trig functions ab initio. $\endgroup$ – J. M. isn't a mathematician Dec 3 '10 at 8:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.