Re: Efficiently compute Fourier coefficients for discrete function
- To: mathgroup at smc.vnet.net
- Subject: [mg105455] Re: [mg105425] Efficiently compute Fourier coefficients for discrete function
- From: Sseziwa Mukasa <mukasa at jeol.com>
- Date: Thu, 3 Dec 2009 06:15:19 -0500 (EST)
- References: <200912021125.GAA26671@smc.vnet.net>
On Dec 2, 2009, at 6:25 AM, Kelly Jones wrote:
> Mathematica-wise, how to efficiently compute the Fourier coefficients
> for a function defined at finite "random" points. Example:
>
> This defines Sin[3*x] for 100 random values of x:
>
> l = Table[Random[],{i,1,100}]
> l2 = Table[{l[[i]],Sin[3*l[[i]]]},{i,1,Length[l]}]
>
> This calculates the nth Fourier coefficient:
>
> pfourier[s_,n_] := Sum[s[[i]][[2]]*Exp[-I*n*s[[i]][[1]]], {i,
> 1,Length[s]}]
>
> (I realize I'm off by a factor of pi; I'm only interested in relative
> size for now).
>
> As expected, the imaginary/sine part of the 3rd coefficient has the
> greatest magnitude:
>
> Table[Im[pfourier[l2,n]],{n,1,10}]
>
> I could compute pfourier[l2,n] for all n, but that seems inefficient.
>
> Is there a simpler function (similar to Fourier and FourierTransform)
> that does this?
Simplicity is in the eye of the beholder. As long as all the sample
points can be mapped to rational numbers, which is true in your case,
sampling at random points is equivalent to sampling over an
equispaced mesh that contains all the random points, and setting the
sample values at points that don't correspond to the random set to
0. From this it is obvious that the spectrum of a randomly sampled
signal is the convolution of the a train of impulses at the random
sample points and the spectrum of the signal of interest. So the
easiest algorithm is to identify the mesh (in your case the gcd of
the values in l) and fill in l2 with zeroes at mesh points not in l.
The drawback is your spectrum will have more points in it than your
signal since sampling at random points means there is no longer a 1
to 1 map between points in the spectrum (Fourier coefficients) and
the signal. If you want to compute the spectrum at a specific subset
of frequencies you can use an NFFT (Non-equispaced Fourier Transform)
style algorithm, there's a Mathematica implementation of an NFFT
algorithm at http://library.wolfram.com/infocenter/MathSource/5598/,
there's more information on NFFT at http://www-user.tu-chemnitz.de/
~potts/nfft/guide3/html/index.html.
Regards,
Ssezi
- References:
- Efficiently compute Fourier coefficients for discrete function
- From: Kelly Jones <kelly.terry.jones@gmail.com>
- Efficiently compute Fourier coefficients for discrete function