MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Re: Plot3d causes crash with radeon driver and
  • Next by Date: Re: Re: Combine images, Show[] and its effect on
  • Previous by thread: Efficiently compute Fourier coefficients for discrete function
  • Next by thread: Re: Efficiently compute Fourier coefficients for discrete function