Given $f(x)$ and its FFT $F(u)$, I need to prove that $df/dx = F(u) * 2iu\pi /n.$

$df/dx = f'(x)$ and $n$ is the number of pixels of the one dimensional image $f$.

I tried to use the convolution theorem using conv($f[1 -1]$) which is the same as $df/dx$ and in the frequency domain it's $F(u) * FFT([1 -1])$ however there sizes don't match.

  • $\begingroup$ @JasonR please help with the full solution. we i tried it as well.and had some problem with it. $\endgroup$ – Gilad Feb 6 '13 at 10:11

This should have been a comment on the question but is too long to fit within the 500-character limit.

The $f$ that is the subject of this question is a sequence or vector of $n$ numbers $$[f_0, f_1, \ldots, f_{n-1}] ~~ \text{or} ~~ \left[f[0], f[1], \ldots, f[n-1]\right] ~~ \text{or} ~~ \left[f(0), f(1), \ldots, f(n-1)\right]$$ depending on choice of notation, and its Discrete Fourier Transform (DFT) $F$ (called the FFT by the OP) is another sequence or vector of $n$ numbers. Thus, it is not clear what the derivative $\frac{\mathrm d}{\mathrm dx}f(x) = f^\prime(x)$ means since the argument of $f(\cdot)$ is an integer and not a continuous variable. One could attempt to make sense of what is intended by looking at the OP's approach to the problem via (cyclic or periodic) convolution with the sequence $[1, -1]$ (actually should have been $[1,-1,0,0,\ldots, 0]$ which results in replacing $f_i$ by $f_{i+1}-f_i$. Now, we are getting closer to the notion of differentiation since the derivative of a continuous function is obtained by looking at the limit of $\frac{f(x+h)-f(x)}{h}$ as $h \to 0$. Here we have the closest we can get since we are using $\frac{f(i+1)-f(i)}{1} = f_{i+1}-f_i$, and of course $1$ cannot "approach" $0$. Unfortunately, this does not give the desired result. The $k$-th term of the DFT of $[1,-1,0,0,\ldots, 0]$ is readily computed from the definition (no FFTs needed) as $1 - e^{-j2\pi k/n}$, and so the DFT of the "derivative" sequence $f_{i+1}-f_i$ has $k$-th term $F_k(1 - e^{-j2\pi k/n})$ which is not what the OP wants to prove.

So, what does the OP want to prove? It is $\frac{\mathrm df}{\mathrm dx} \mathbf{=} F(u)*j(2\pi u/n)$. This needs clarification on two grounds. First, the left side of this equality is a function of $x$, the right side a function of $u$. So what does it mean to say the two are equal? Second, what the right side means needs clarification. Does the $*$ mean multiplication of the two complex numbers $F(u)$ and $j(2\pi u/n)$, or is the $*$ denoting complex conjugation of $F(u)$ before the multiplication, or does $*$ denote convolution so that $F(u)*j(2\pi u/n)$ means the $u$-th term of the (cyclic or periodic) convolution of the sequences $[F_0,F_1,\ldots,F_{n-1}]$ and $[1, j(2\pi/n),j(2\pi 2/n), \ldots, j(2\pi (n-1)/n)]$? The closest match occurs if we assume that $=$ is a typographical error and that what is meant is not the equality that the OP claims is needed. Instead, suppose that what was really asked for but mistranslated by the OP is that the $k$-th term of the DFT of $\frac{\mathrm df}{\mathrm dx}$ by which is meant the sequence with $i$-th term $f_{i+1}-f_i$ is $F_ke^{j2\pi k/n}$ (another typo, the missing exponential!). As noted above, this is not quite right: it should be $F_k(1 - e^{-j2\pi k/n})$. Note, incidentally, that the inverse DFT of the sequence with $k$-th term $F_ke^{j2\pi k/n}$ is a cyclic shift of the sequence $f$; see, for example, this Wikipedia entry

But maybe as a non-expert in image processing I am missing something completely and so I await clarification from the OP, or perhaps a more detailed explanation from @JasonR of the method outlined in his comment on the OP's question.

  • $\begingroup$ I should have thought more when I read the OP. I was thinking of the continuous-time Fourier transform instead, which has the well-known property that differentiation in the time-domain yields scaling in the frequency domain by a factor proportional to $\omega$. I'm going to remove my misleading comment. $\endgroup$ – Jason R Feb 6 '13 at 16:11
  • $\begingroup$ I suspect what he means is that if P is some sort of "derivative like" operator in the discrete domain, then $FFT\{Pf\} = G[u] = F[u] 2 i \pi u/n$ where $F[u] = FFT\{f\}$ and $n$ is the number of samples? $\endgroup$ – thang Feb 7 '13 at 0:02
  • $\begingroup$ @thang Yes, he might mean that, but he says something completely different. Perhaps the OP will return some time and clarify his meaning. $\endgroup$ – Dilip Sarwate Feb 7 '13 at 0:17
  • $\begingroup$ Yeah you're right... the post itself makes no sense to me as is. That's the only way in which I can make sense of it. $\endgroup$ – thang Feb 7 '13 at 0:18

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.