fourier transformation (non-periodically data)
Jürg
first problem:
I have a series of measurement data in dependency of time, but the
time-values are not in a periodically fashion.
So I do not have 1sec:45V; 2sec:44V; 3sec:46V; 4sec:67V; ...
What I have: My values are at "random" time-points and the stepwide
between the measurement points are not constant. But more or less
equal distributed.
How can I calculate a frequency-spectrum (like a fourier transform)?
second problem:
I have measurement data like above, but in dependency of many
dimensions. So I have a set of randomly distributes points in n-
dimensional space and a measurement-value is assigned to each point.
How can i calculate a frequency-spectrum (like a fourier transform)?
Thanks in advance for any hints and discussion.
Jörg
Martin Brown
> Hello group,
>
> first problem:
> I have a series of measurement data in dependency of time, but the
> time-values are not in a periodically fashion.
> So I do not have 1sec:45V; 2sec:44V; 3sec:46V; 4sec:67V; ...
> What I have: My values are at "random" time-points and the stepwide
> between the measurement points are not constant. But more or less
> equal distributed.
> How can I calculate a frequency-spectrum (like a fourier transform)?
If it is a modest number of points and only a few experiments you could
actually compute the slow DFT of the actual dataset. It isn't that fast
but it may still be faster than implementing the alternative below.
Otherwise the basic method is to regrid the raw data onto a uniform grid
with a small kernel convolutional gridding function (typically 3 pixels
either side) that controls periodic aliassing. Then take the FFT of that
array. There are a number of practical tricks and gotchas to doing it
right.
sinc(x)exp(-kx^2) was used in the past for this regridding function
although prolate spheroidal Bessel functions will work better.
Also worth gridding fake data of unity at every point convolved with the
gridding function so that you can get an idea of what your point spread
function looks like based on the uneven Fourier space coverage.
Methods exist in radio astronomy and spectral analysis to take the raw
FFT output and the dirty beam/PSF and do a deconvolution or CLEAN. You
have to be a little bit careful about the interpretation after these..
>
> second problem:
> I have measurement data like above, but in dependency of many
> dimensions. So I have a set of randomly distributes points in n-
> dimensional space and a measurement-value is assigned to each point.
> How can i calculate a frequency-spectrum (like a fourier transform)?
>
> Thanks in advance for any hints and discussion.
> J�rg
Same way except that it requires a lot more work to do the regridding in
multiple dimensions. Aperture synthesis radio astronomy codes are
optimised for the 2D case and MRI tomography codes are optimised for the
3D case. You might find it useful to search the help files for AIPS.
Regards,
Martin Brown
Peter Spellucci
In article <52644123-bace-4753...@u7g2000yqm.googlegroups.com>,
from my annotations:
<<<<<<<<
We are pleased to announce version 3.0 of our C library for computing the
nonequispaced discrete Fourier transform in one or more dimensions.
Our library is free software, and based on FFTW3.
Visit the NFFT web-site at
http://www.uni-chemnitz.de/~potts/nfft
for the software, documentation, and related links.
NFFT3 is a software library written in C for computing nonequispaced fast
Fourier and related transformations. In detail, NFFT3 implements
1) The nonequispaced fast Fourier transform (NFFT)
- the forward transform,
- its adjoint transform.
2) Generalisations of the NFFT
- to arbitrary nodes in time _and_ frequency domain,
- to the two dimensional unit sphere,
- to the hyperbolic cross,
- to real-valued data, i.e. (co)sine transforms.
3) Generalised inverses based on iterative methods.
4) Applications in
- medical imaging (magnetic resonance imaging and computerised tomography),
- summation schemes (fast Gauss transform, convolution with singular
kernels, and convolution on the sphere),
- polar FFTs, discrete Radon transform, ridgelet transform.
If you have comments, questions, or suggestions don't hesitate to email
Jens Keiner (kei...@math.uni-luebeck.de),
Stefan Kunis (ku...@mathematik.tu-chemnitz.de), or
Daniel Potts (po...@mathematik.tu-chemnitz.de).
>>>>
hth
peter
Jürg
First thank you for your answer.
> If it is a modest number of points and only a few experiments you could
> actually compute the slow DFT of the actual dataset. It isn't that fast
> but it may still be faster than implementing the alternative below.
I have to re-read again the description of dtf. I did not realize,
that I can process nonequispaced (I learend this word from Peter
below...) data with dft. I do not need a real-time application if this
takes some seconds its okay.
> Otherwise the basic method is to regrid the raw data onto a uniform grid
> with a small kernel convolutional gridding function (typically 3 pixels
> either side) that controls periodic aliassing. Then take the FFT of that
> array. There are a number of practical tricks and gotchas to doing it
> right.
> sinc(x)exp(-kx^2) was used in the past for this regridding function
> although prolate spheroidal Bessel functions will work better.
> Also worth gridding fake data of unity at every point convolved with the
> gridding function so that you can get an idea of what your point spread
> function looks like based on the uneven Fourier space coverage.
I already played a little around with regriding. I'll have a closer
look again. Now I have some more hints redarding this topic.
> Methods exist in radio astronomy and spectral analysis to take the raw
> FFT output and the dirty beam/PSF and do a deconvolution or CLEAN. You
> have to be a little bit careful about the interpretation after these..
Same as above - I'll have a look.
> > second problem:
> Same way except that it requires a lot more work to do the regridding in
> multiple dimensions. Aperture synthesis radio astronomy codes are
> optimised for the 2D case and MRI tomography codes are optimised for the
> 3D case. You might find it useful to search the help files for AIPS.
I'll have a look. But I need for more than 3 dimensions.
Regards,
Jörg
Jürg
thanks for the hint! I had a short look and it seem to fit. As far as
I've seen, there's also papers to download. So I have to read. I hope
they are readable and understandalbe for a non-mathematician like me.
If I understood corectly the "NNFFT" (nonequispaced in time and
frequency fast Fourier transform) seems the right for me.
Regards, Jörg
Martin Brown
> Hello Martin,
>
> First thank you for your answer.
>
>> If it is a modest number of points and only a few experiments you could
>> actually compute the slow DFT of the actual dataset. It isn't that fast
>> but it may still be faster than implementing the alternative below.
> I have to re-read again the description of dtf. I did not realize,
> that I can process nonequispaced (I learend this word from Peter
> below...) data with dft. I do not need a real-time application if this
> takes some seconds its okay.
It depends how nicely your not exactly equispaced data is distributed in
the time domain. The other method if computational cost is no barrier is
to build a Fourier model that is consistent with the actual observations
using MEM or some other constrained non-linear optimisation.
>> Otherwise the basic method is to regrid the raw data onto a uniform grid
>> with a small kernel convolutional gridding function (typically 3 pixels
>> either side) that controls periodic aliassing. Then take the FFT of that
>> array. There are a number of practical tricks and gotchas to doing it
>> right.
>> sinc(x)exp(-kx^2) was used in the past for this regridding function
>> although prolate spheroidal Bessel functions will work better.
>> Also worth gridding fake data of unity at every point convolved with the
>> gridding function so that you can get an idea of what your point spread
>> function looks like based on the uneven Fourier space coverage.
>
> I already played a little around with regriding. I'll have a closer
> look again. Now I have some more hints redarding this topic.
I'd really suggest you don't try to roll your own and try the package
that Peter has pointed to or another tested implementation. There are a
lot of possibilities for systematic error in the regridding of bulk
data. Even experienced mathematicians have been known to get it wrong.
If you have some kind of analytic or semi-analytic approximation to the
density of the points in the raw space you can also correct for that.
After that stage all the usual caveats of using FFTs apply.
>> Methods exist in radio astronomy and spectral analysis to take the raw
>> FFT output and the dirty beam/PSF and do a deconvolution or CLEAN. You
>> have to be a little bit careful about the interpretation after these..
> Same as above - I'll have a look.
>
>>> second problem:
>> Same way except that it requires a lot more work to do the regridding in
>> multiple dimensions. Aperture synthesis radio astronomy codes are
>> optimised for the 2D case and MRI tomography codes are optimised for the
>> 3D case. You might find it useful to search the help files for AIPS.
>
> I'll have a look. But I need for more than 3 dimensions.
Obviously it gets costly to do the gridding convolutions rather rapidly
with increasing dimensionality. I am curious. What sort of raw data do
you have that is collected in more than 3 dimensions ?
Regards,
Martin Brown
Jürg
> It depends how nicely your not exactly equispaced data is distributed in
> the time domain. The other method if computational cost is no barrier is
> to build a Fourier model that is consistent with the actual observations
> using MEM or some other constrained non-linear optimisation.
With MEM you mean "Maximum-Entropy Method"?
> I'd really suggest you don't try to roll your own and try the package
> that Peter has pointed to or another tested implementation. There are a
> lot of possibilities for systematic error in the regridding of bulk
> data. Even experienced mathematicians have been known to get it wrong.
Dos the package Peter has pointed to using regriding? On the other
hand "regriding" seens for me not so a nice solution. Especially for
cases with more than one dimension.
> If you have some kind of analytic or semi-analytic approximation to the
> density of the points in the raw space you can also correct for that.
> After that stage all the usual caveats of using FFTs apply.
I do not have any analytic approximation and/or solution. But it would
be very nice to have. But an fourier-transformation would be one kind
of model? Or Iam wrong?
> Obviously it gets costly to do the gridding convolutions rather rapidly
> with increasing dimensionality. I am curious. What sort of raw data do
> you have that is collected in more than 3 dimensions ?
This is "artificial" data collected by simulation software. Each input
value is treated as an "dimension" - I just get an result in form of
an floating-point-value.
Jörg
Gordon Sande
> Hallo Martin,
>
>> It depends how nicely your not exactly equispaced data is distributed in
>> the time domain. The other method if computational cost is no barrier is
>> to build a Fourier model that is consistent with the actual observations
>> using MEM or some other constrained non-linear optimisation.
> With MEM you mean "Maximum-Entropy Method"?
>
>> I'd really suggest you don't try to roll your own and try the package
>> that Peter has pointed to or another tested implementation. There are a
>> lot of possibilities for systematic error in the regridding of bulk
>> data. Even experienced mathematicians have been known to get it wrong.
> Dos the package Peter has pointed to using regriding? On the other
> hand "regriding" seens for me not so a nice solution. Especially for
> cases with more than one dimension.
>
>> If you have some kind of analytic or semi-analytic approximation to the
>> density of the points in the raw space you can also correct for that.
>> After that stage all the usual caveats of using FFTs apply.
> I do not have any analytic approximation and/or solution. But it would
> be very nice to have. But an fourier-transformation would be one kind
> of model? Or Iam wrong?
Fourier methods are tightly tied to the assumptions of time (or space etc)
invariance and superposition. If those are not part of your "no model" then
it is a serious question of why you want to use Fourier methods. Fourier
methods are popular because many problems have the right kinds of invariance
and superposition. When the assumptions are met the methods are powerful but
without them they are more just fashion and following the herd. The assumptions
may be met even if your observations are not the most convenient to
exploit them
easily.
>> Obviously it gets costly to do the gridding convolutions rather rapidly
>> with increasing dimensionality. I am curious. What sort of raw data do
>> you have that is collected in more than 3 dimensions ?
> This is "artificial" data collected by simulation software. Each input
> value is treated as an "dimension" - I just get an result in form of
> an floating-point-value.
>
> J�rg
Martin Brown
> Hallo Martin,
>
>> It depends how nicely your not exactly equispaced data is distributed in
>> the time domain. The other method if computational cost is no barrier is
>> to build a Fourier model that is consistent with the actual observations
>> using MEM or some other constrained non-linear optimisation.
> With MEM you mean "Maximum-Entropy Method"?
Yes.
>
>> I'd really suggest you don't try to roll your own and try the package
>> that Peter has pointed to or another tested implementation. There are a
>> lot of possibilities for systematic error in the regridding of bulk
>> data. Even experienced mathematicians have been known to get it wrong.
> Dos the package Peter has pointed to using regriding? On the other
> hand "regriding" seens for me not so a nice solution. Especially for
> cases with more than one dimension.
I don't know. It is too far outside the sort of stuff I do these days.
>
>> If you have some kind of analytic or semi-analytic approximation to the
>> density of the points in the raw space you can also correct for that.
>> After that stage all the usual caveats of using FFTs apply.
> I do not have any analytic approximation and/or solution. But it would
> be very nice to have. But an fourier-transformation would be one kind
> of model? Or Iam wrong?
Fourier transform is a generalised rotation of the data onto a new
orthogonal set of basis functions. If your data looks more sensible
there than in real space it makes it easier to interpret eg NMR.
>> Obviously it gets costly to do the gridding convolutions rather rapidly
>> with increasing dimensionality. I am curious. What sort of raw data do
>> you have that is collected in more than 3 dimensions ?
> This is "artificial" data collected by simulation software. Each input
> value is treated as an "dimension" - I just get an result in form of
> an floating-point-value.
It might be worth taking a step back and finding out what is the
original problem you are trying to address? Applying an ad hoc Fourier
transform to random data will just give a meaningless result. It is only
ever going to work there is some underlying periodicity in it.
Regards,
Martin Brown