FFT of a non uniformly sampled signal

Hello,
I have a signal, f(t), that has been sampled non uniformly
(irregular).
I need to find the DTF of this signal, F(omega).
Since the FFT is very fast and I already have an implementation of it
that I am familiar with; I want to regularize the data;
that is approximate the signal at $t=i*\Delta t$, where i=0, 1, 2, ...
and $\Delta t$ is the sampling.

So far I have binned the sampled values.
Example:
I have the following irregular samples of f(t):
f(1) = 2, f(2) = 3, f(6) = 1, f(7) = 3 and f(13) = 4.
Choosing $\Delta t$ = 10 the result of the binning is:
f(0)   =  f(1)  +  f(2) = 5
f(10) =  f(6)  +  f(7) + f(13) = 8

Does the binning introduce aliasing?

Is there a relatively simple way I can assign the non uniformly
sampled values to the nodes in an uniform grid that gives a better
("smoother" ?)  representation of f(t)?

Thanks in advance for any answers!

No Latex support :-( ?

the line

>>that is approximate the signal at $t=i*\Delta t$, where i=0, 1, 2, ...
>>and $\Delta t$ is the sampling.

should read:
that is approximate the signal at t = i*Dt, where i=0, 1, 2, ... and
Dt is the sampling.

"Andy365" <andreas_w_paulsen@yahoo.com> wrote in message 
news:dc7d3ede-d09e-4c98-b549-ac9a30f49668@m10g2000yqd.googlegroups.com...
> Hello,
> I have a signal, f(t), that has been sampled non uniformly
> (irregular).
> I need to find the DTF of this signal, F(omega).
> Since the FFT is very fast and I already have an implementation of it
> that I am familiar with; I want to regularize the data;
> that is approximate the signal at $t=i*\Delta t$, where i=0, 1, 2, ...
> and $\Delta t$ is the sampling.
>
> So far I have binned the sampled values.
> Example:
> I have the following irregular samples of f(t):
> f(1) = 2, f(2) = 3, f(6) = 1, f(7) = 3 and f(13) = 4.
> Choosing $\Delta t$ = 10 the result of the binning is:
> f(0)   =  f(1)  +  f(2) = 5
> f(10) =  f(6)  +  f(7) + f(13) = 8

That doesn't work.

Say the signal was a constant level V e.g.
 f(1) = V, f(2) = V, f(6) = V, f(7) = V and f(13) = V.

f(0)   =  f(1)  +  f(2) = 2*V
f(10) =  f(6)  +  f(7) + f(13) = 3*V

Both f(0) and f(10) should equal V.

You could use linear interpolation e.g.

f(0) = f(1) - (f(2)-f(1))
f(10) = (f(7)+f(13))/2

On 05/09/2011 10:51 AM, Andy365 wrote:
> Hello,
> I have a signal, f(t), that has been sampled non uniformly
> (irregular).
> I need to find the DTF of this signal, F(omega).
> Since the FFT is very fast and I already have an implementation of it
> that I am familiar with; I want to regularize the data;
> that is approximate the signal at $t=i*\Delta t$, where i=0, 1, 2, ...
> and $\Delta t$ is the sampling.
>
> So far I have binned the sampled values.
> Example:
> I have the following irregular samples of f(t):
> f(1) = 2, f(2) = 3, f(6) = 1, f(7) = 3 and f(13) = 4.
> Choosing $\Delta t$ = 10 the result of the binning is:
> f(0)   =  f(1)  +  f(2) = 5
> f(10) =  f(6)  +  f(7) + f(13) = 8
>
> Does the binning introduce aliasing?
>
> Is there a relatively simple way I can assign the non uniformly
> sampled values to the nodes in an uniform grid that gives a better
> ("smoother" ?)  representation of f(t)?

I don't know if this is the _best_ way, but here's _a_ way:

I would consider using splines to make things fit.  For each result 
sample, choose the three nearest neighboring source samples, and do the 
spline thing.

The calculations for splines is only complex if you need to calculate 
for arbitrary sampling intervals -- if the intervals are known before 
hand, then the computation becomes one of multiplying the three samples 
by three known coefficients and taking the result.  So if your actual 
sampling instants are really at integer increments of some faster clock, 
and if those integer increments are bounded tightly enough (i.e., if 
there's never an increment longer than 5, for instance), then you can 
pre-calculate some or all of the possible combinations of intervals and 
significantly speed up your on-line calculation.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Do you need to implement control loops in software?
"Applied Control Theory for Embedded Systems" was written for you.
See details at http://www.wescottdesign.com/actfes/actfes.html

On May 9, 1:57=A0pm, Andy365 <andreas_w_paul...@yahoo.com> wrote:
> No Latex support :-( ?
>
> the line
>
> >>that is approximate the signal at $t=3Di*\Delta t$, where i=3D0, 1, 2, =
...
> >>and $\Delta t$ is the sampling.
>
> should read:
> that is approximate the signal at t =3D i*Dt, where i=3D0, 1, 2, ... and
> Dt is the sampling.

how do the dt samples relate to the nyquist rate?  10x, 5x, 2x?

there will always be aliasing with resampling, to some degree

linear or spline interpolation may be all that is needed, depends on
the nature of your data

and the problem your trying to solve

Hello Andrew,
yes you are right I must normalize the data:
f(0)   = [  f(1)  +  f(2) ] / 2
f(10) =  [ f(6)  +  f(7) + f(13) ] / 3

Would not linear interpolation be more vulnerable to noise?
In my example I only had 2 and 3 samples in each bin cell.
In reality I may have about 10 samples in each bin cell.
If I sum together 10 samples the signal/noise ratio would improve by a
factor of 10?

On May 9, 8:40=A0pm, steve <bungalow_st...@yahoo.com> wrote:
> On May 9, 1:57=A0pm, Andy365 <andreas_w_paul...@yahoo.com> wrote:
>
> > No Latex support :-( ?
>
> > the line
>
> > >>that is approximate the signal at $t=3Di*\Delta t$, where i=3D0, 1, 2=
, ...
> > >>and $\Delta t$ is the sampling.
>
> > should read:
> > that is approximate the signal at t =3D i*Dt, where i=3D0, 1, 2, ... an=
d
> > Dt is the sampling.
>
> how do the dt samples relate to the nyquist rate? =A010x, 5x, 2x?
>
> there will always be aliasing with resampling, to some degree
>
> linear or spline interpolation may be all that is needed, depends on
> the nature of your data
>
> and the problem your trying to solve

Hello Steve,
to me the binning I am doing seems to me a bit similar to the problem
of rasterizing a line in computer graphics.
Therefore I was wondering if there might be some techniques borrow
from that field / image analysis that I could use?

On May 9, 7:51=A0pm, Andy365 <andreas_w_paul...@yahoo.com> wrote:
> Hello,
> I have a signal, f(t), that has been sampled non uniformly
> (irregular).
> I need to find the DTF of this signal, F(omega).

Wrong. You need to find the spectrum F(w) of this,
sequence, not the DFT. The DFT is useful only with
regularly sampled data, whereas the signal you are
describing might be seen as a sequence of irregularly
spaced Dirac deltas.

Use the straight-forward inner product with the
basis functions.

> Since the FFT is very fast and I already have an implementation of it
> that I am familiar with;

That doesn't matter. The FFT is the wrong tool to use.
A hammer is no good if the task is to cut a plank in half.

> I want to regularize the data;
> that is approximate the signal at $t=3Di*\Delta t$, where i=3D0, 1, 2, ..=
.
> and $\Delta t$ is the sampling.

When? Before applying the FFT? Or is the interpolation
the purpose of the FFT?

Rune

On May 10, 5:39=A0am, Rune Allnor <all...@tele.ntnu.no> wrote:
> On May 9, 7:51=A0pm, Andy365 <andreas_w_paul...@yahoo.com> wrote:
>
> > Hello,
> > I have a signal, f(t), that has been sampled non uniformly
> > (irregular).
> > I need to find the DTF of this signal, F(omega).
>
> Wrong. You need to find the spectrum F(w) of this,
> sequence, not the DFT. The DFT is useful only with
> regularly sampled data, whereas the signal you are
> describing might be seen as a sequence of irregularly
> spaced Dirac deltas.
>
> Use the straight-forward inner product with the
> basis functions.
>
> > Since the FFT is very fast and I already have an implementation of it
> > that I am familiar with;
>
> That doesn't matter. The FFT is the wrong tool to use.
> A hammer is no good if the task is to cut a plank in half.
>
> > I want to regularize the data;
> > that is approximate the signal at $t=3Di*\Delta t$, where i=3D0, 1, 2, =
...
> > and $\Delta t$ is the sampling.
>
> When? Before applying the FFT? Or is the interpolation
> the purpose of the FFT?
>
> Rune

Thank you Rune!
Yes you are right;
my signal is a sum of irregularly spaced Dirac deltas multiplied with
sample values,
therefore the Fourier transform of this is a sum of plane waves
multiplied with sample values.
And yes the spectrum is my goal, and the interpolation is just a step
towards this.
However in reality my signal is in 3 dimensions and I may have say
about 10 000 irregular samples.
I think that adding together the plane wave value over 10 000 waves
for each point will be very time consuming and that it therefore is
better to use FFT.


Andreas

On May 10, 9:44=A0am, Andy365 <andreas_w_paul...@yahoo.com> wrote:

  ...

> However in reality my signal is in 3 dimensions and I may have say
> about 10 000 irregular samples.
> I think that adding together the plane wave value over 10 000 waves
> for each point will be very time consuming and that it therefore is
> better to use FFT.

You just don't get it. FFT (fast Fourier transform) is a class of
algorithms that perform a DFT (discrete Fourier transform) on
regularly sampled data. Using the procedure on irregularly sampled
data is no more useful than deciphering coded data with the wrong key.
While it may be true that using known correct methods on your samples
is impractical, only wishful thinking leaps from there to the
conclusion that incorrect methods will therefore yield a useful
result.

Jerry
--
Engineering is the art of making what you want from things you can get.