Take the 2-minute tour ×

I have an array y[x], x=0,1,2,...,10^6 describing a periodic signal with y(10^6)=y(0), and I want to compute its derivative dy/dx with a fast method.

I tried the spectral difference method, namely

dy/dx = inverse_fourier_transform ( i*k fourier_transform(y)[k] ) .................(1)

and the result is different from (y[x+1]-y[x-1])/2 i.e. suggested by finite difference method.

Which of the two is more accurate, and which is faster? Are there other comparable methods?

Below is an effort to understand the difference of the results:

If one expand both the sum for the fourier_transform and that for the inverse_fourier_transform in (1), one can express dy/dx as a linear combination of y[x] with coefficients a[x]. I computed these coefficients and they seem to go as 1/n (when the length of the array goes to infinity) with n being the distance to where the derivative is examined. Compared to the finite differencing method which uses only the two neighboring points, the spectral difference is highly non-local... Am I correct with this result, and if yes, how to understand this?

share|improve this question
You should post your question here: math.stackexchange.com –  SteAp Apr 18 '12 at 21:50
this could also have gone to scicomp.stackexchange.com, but is probably a best fit at dsp.stackexchange.com –  Aron Ahmadia May 10 '12 at 19:04
add comment

1 Answer

up vote 2 down vote accepted

if you are sampling the signal above the nyquist frequency then the fourier method gives you an exact answer because your data completely describe the signal (assuming no noise).

the finite difference method is a first order approximation and so is not exact. but still, if you plot the two, they should show the same basic trends. if they look completely different then you probably have an error somewhere.

however, a fast ft is O(nlog(n)) while finite differences are O(n) so the latter is faster (but not so much faster that it should be automatically preferred).

the fourier approach is non-local in the sense that it constructs the whole signal, exactly (and so uses all wavelengths).

share|improve this answer
Thanks! My signal is a continuous one and does not have a cut-off frequency, so there is always more structure not sampled on small scales. –  user1342516 Apr 19 '12 at 6:48
Is it appropriate to understand like this: finite difference calculates the derivative on the smallest sampling scale, while as the spectral/fourier approach tries to reconstruct the whole signal with all sampled frequencies and computes the derivative of the reconstructed signal on an infinitesimal scale? –  user1342516 Apr 19 '12 at 6:57
yes, but in your case you will also have artifacts because reconstruction is not correct (as you have frequencies in the "real" signal that are not present in the data). –  andrew cooke Apr 19 '12 at 10:48
add comment

Your Answer


