How to do non-uniform (sampling) DFT?

Hi all,

Can anybody point me to some helps/tutorials/references/stories on how
to do non-uniform (sampling) DFT?

Thank you very much for your help,

-Walala

walala wrote:
> Hi all,
> 
> Can anybody point me to some helps/tutorials/references/stories on how
> to do non-uniform (sampling) DFT?
> 
> Thank you very much for your help,
> 
> -Walala

Here is a good source:

Technique for frequency analysis of unevenly sampled radar data
House, M.G.   Mountcastle, P.D.
XonTech Inc., Huntington Beach, CA, USA
This paper appears in: Radar Conference, 2002. Proceedings of the IEEE

Publication Date: 22-25 April 2002
On page(s): 63 - 67
ISSN: 1097-5659
Number of Pages: xix+508
Inspec Accession Number: 7366627
Abstract:
A new technique is described that generalizes the usefulness of the 
discrete Fourier transform for spectral analysis of radar data to 
applications where the discrete data points to be analyzed are not 
sampled at regular intervals and/or do not have equal statistical 
weight. This method finds a frequency-domain representation which best 
represents the given time-domain data in the least-square-residual 
sense. The theoretical implications of such an approach are discussed, 
and an example of the technique applied to a Doppler processing task is 
given. The merits of the approach relative to other spectral analysis 
techniques are discussed.

Good luck,
OUP

In article <6f348bd1.0408151717.3bd80eda@posting.google.com>,
walala <mizhael@yahoo.com> wrote:

>Can anybody point me to some helps/tutorials/references/stories on how
>to do non-uniform (sampling) DFT?

I assume you mean something like this: 

There is a function f(t), assumed to be periodic with period (for 
convenience) 2 pi, and at some more-or-less arbitrary N points t_1,...,t_N 
you know f(t_k) = y_k.
You want to (approximately) calculate the Fourier series coefficients
c_k such that f(t) = sum_k c_k exp(ikt).

Well, one thing you can do is assume only N coefficients count, e.g. 
f(t) = sum_{k=a}^b c_k exp(ikt) where a=-(N-1)/2,b=(N-1)/2 if N is odd,
or perhaps a=-N/2+1,b=N/2 if N is even, and solve the N x N system
of equations 

y_j = sum_{k=a}^b exp(ik t_j) c_k    

But this is really equivalent to a Lagrange interpolation problem:
y_j exp(-ia t_j) = sum_{k=0}^{N-1} exp(ik t_j) c_{k+a}
                 = P(exp(i t_j))

where P(z) = sum_{k=0}^{N-1} c_{k+a} z^k.  One way of solving 
the Lagrange problem is this: if 

w(z) = product_{j=1}^N (z - exp(i t_j))

then

P(z) = sum_{j=1}^n y_j exp(-ia t_j) product_{k <> j}
                (z - exp(i t_k))/(exp(i t_j) - exp(i t_k))

In particular the solution is unique as long as the t_j are
distinct mod 2 pi.

I make no claims about numerical stability.

Robert Israel                                israel@math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel 
University of British Columbia            
Vancouver, BC, Canada V6T 1Z2

You could try Googling for the Lomb-Scargle Periodogram method. It
works with unevenly sampled data. I believe it is used in the
astrophysics community.  I'm told that the Numerical Recipes in
(FORTRAN,C,...) books have an implementation.

I've never tried using it, but filed the reference away, just in case.
 Let me know how you get on.

Jon


mizhael@yahoo.com (walala) wrote in message news:<6f348bd1.0408151717.3bd80eda@posting.google.com>...
> Hi all,
> 
> Can anybody point me to some helps/tutorials/references/stories on how
> to do non-uniform (sampling) DFT?
> 
> Thank you very much for your help,
> 
> -Walala

>Subject: How to do non-uniform (sampling) DFT?
>From: mizhael@yahoo.com  (walala)
>Date: 8/15/2004 9:17 PM Eastern Daylight Time
>Message-id: <6f348bd1.0408151717.3bd80eda@posting.google.com>
>
>Hi all,
>
>Can anybody point me to some helps/tutorials/references/stories on how
>to do non-uniform (sampling) DFT?
>
>Thank you very much for your help,
>
>-Walala
>
>
>
>
>
>

Try the following paper:

Duijndam A. J. W. and Schonewille M. A., Nonuniform fast Fourier transform,
Geophysics, Vol 64, No 2 (March-April 1999), pages 539-551.

I have not actual reviewed the article in-depth, so it may not be of any help.

Scott

I'm told that the Numerical Recipes in
> (FORTRAN,C,...) books have an implementation.

Yes. NR has a section on spectral analysis on unevenly sampled data.
goto http://www.nr.com for a free copy of the book.

if the sample is not that non-uniform you can pad with zeros..you can
check more on how exactly this can be done in the book
http://www.dspguide.com

--Ramoj Paruchuri

I'm told that the Numerical Recipes in
> (FORTRAN,C,...) books have an implementation.

Yes. NR has a section on spectral analysis on unevenly sampled data.
goto http://www.nr.com for a free copy of the book.

if the sample is not that non-uniform you can pad with zeros..you can
check more on how exactly this can be done in the book
http://www.dspguide.com

--Ramoj Paruchuri

I'm told that the Numerical Recipes in
> (FORTRAN,C,...) books have an implementation.

Yes. NR has a section on spectral analysis on unevenly sampled data.
goto http://www.nr.com for a free copy of the book.

if the sample is not that non-uniform you can pad with zeros..you can
check more on how exactly this can be done in the book
http://www.dspguide.com

--Ramoj Paruchuri

I'm told that the Numerical Recipes in
> (FORTRAN,C,...) books have an implementation.

Yes. NR has a section on spectral analysis on unevenly sampled data.
goto http://www.nr.com for a free copy of the book.

if the sample is not that non-uniform you can pad with zeros..you can
check more on how exactly this can be done in the book
http://www.dspguide.com

--Ramoj Paruchuri

"walala" <mizhael@yahoo.com> wrote in message
news:6f348bd1.0408151717.3bd80eda@posting.google.com...
> Hi all,
>
> Can anybody point me to some helps/tutorials/references/stories on how
> to do non-uniform (sampling) DFT?
>
> Thank you very much for your help,
>
> -Walala

This might help.

function X=dft(t,x,f)
% function X=dft(t,x,f)
% Compute DFT (Discrete Fourier Transform) at frequencies given
%   in f, given samples x taken at times t:
%     X(f) = sum { x(k) * e**(2*pi*j*t(k)*f) }
%             k

shape = size(f);
t = t(:); % Format 't' into a column vector
x = x(:); % Format 'x' into a column vector
f = f(:); % Format 'f' into a column vector

% It's just this simple:
W = exp(-2*pi*j * f*t');
X = W * x;
X = reshape(X,shape);


-Aj