Thread Subject: FFT,IFFT, and NDFT,NFFT

1. When we have irregular sampling, we can use NDFT on it instead of FFT
NDFT equation
f_j = \sum_{k=-N/2}^{N/2-1} \hat f_k e^{(-2 *pi*i*k*x_j)}

k= (-N/2:N/2-1)
x_j=time domain (j=0,1,2____M-1)

So what my question is, whenever we have non uniform sampling in the one domain will we get uniform sampling in another domain. For ex if my time domain is irregular, will i be getting regular sampling in frequency domain


2. Inverting NDFT is not a easy task as in FFT, In ifft A inverse is equal to A conjugate, because of uniform sampling or fixed sampling in time domain that why IFFT is easy to apply. Please correct me if am wrong.

If any one interested in non uniform sampling, here is one good article
http://www.mathematik.tu-chemnitz.de/preprint/quellen/2006/PREPRINT_01.pdf
I didnt understand quiet few things in it, if any one wana discuss..:) will be happy

"guj " <gulatiakshay@gmail.com> wrote in message <h25v6u$5ia$1@fred.mathworks.com>...
> 1. When we have irregular sampling, we can use NDFT on it instead of FFT
> NDFT equation
> f_j = \sum_{k=-N/2}^{N/2-1} \hat f_k e^{(-2 *pi*i*k*x_j)}
>
> k= (-N/2:N/2-1)
> x_j=time domain (j=0,1,2____M-1)
>
> So what my question is, whenever we have non uniform sampling in the one domain will we get uniform sampling in another domain. For ex if my time domain is irregular, will i be getting regular sampling in frequency domain
>
>
> 2. Inverting NDFT is not a easy task as in FFT, In ifft A inverse is equal to A conjugate, because of uniform sampling or fixed sampling in time domain that why IFFT is easy to apply. Please correct me if am wrong.
>
> If any one interested in non uniform sampling, here is one good article
> http://www.mathematik.tu-chemnitz.de/preprint/quellen/2006/PREPRINT_01.pdf
> I didnt understand quiet few things in it, if any one wana discuss..:) will be happy




And Matlab peoples please install latex on server, it will be good to post equations on these threads

On Jun 27, 1:25 pm, "guj " <gulatiaks...@gmail.com> wrote:
> 1. When we have irregular sampling, we can use NDFT on it instead of FFT
> NDFT equation
> f_j = \sum_{k=-N/2}^{N/2-1} \hat f_k e^{(-2 *pi*i*k*x_j)}
>
> k= (-N/2:N/2-1)
> x_j=time domain (j=0,1,2____M-1)
>
> So what my question is, whenever we have non uniform sampling in the one domain will we get uniform sampling in another domain. For ex if my time domain is irregular, will i be getting regular sampling in frequency domain

More like: In some cases of nonequispaced samples, the NFFT can
produce equispaced Fourier coefficients.

If you want other coefficients at other spacings you could seek, for
example, a nonequispaced discrete wavelet transform.
>
> 2. Inverting NDFT is not a easy task as in FFT, In ifft A inverse is equal to A conjugate, because of uniform sampling or fixed sampling in time domain that why IFFT is easy to apply. Please correct me if am wrong.

Why would you want any other function to invert the direction of the
NFFT than an IDFT? Any finite set of the equispaced Fourier
coefficients could represent any of an infinite number of NFFT'd
nonequispaced sample sets. So, how would you choose one and why?
> ...

Dale B. Dalrymple

dbd <dbd@ieee.org> wrote in message <a9e25a3a-e4b4-49e4-bff1-87f869d70c97@e21g2000yqb.googlegroups.com>...
> On Jun 27, 1:25 pm, "guj " <gulatiaks...@gmail.com> wrote:
> > 1. When we have irregular sampling, we can use NDFT on it instead of FFT
> > NDFT equation
> > f_j = \sum_{k=-N/2}^{N/2-1} \hat f_k e^{(-2 *pi*i*k*x_j)}
> >
> > k= (-N/2:N/2-1)
> > x_j=time domain (j=0,1,2____M-1)
> >
> > So what my question is, whenever we have non uniform sampling in the one domain will we get uniform sampling in another domain. For ex if my time domain is irregular, will i be getting regular sampling in frequency domain
>
> More like: In some cases of nonequispaced samples, the NFFT can
> produce equispaced Fourier coefficients.
>
> If you want other coefficients at other spacings you could seek, for
> example, a nonequispaced discrete wavelet transform.
> >
> > 2. Inverting NDFT is not a easy task as in FFT, In ifft A inverse is equal to A conjugate, because of uniform sampling or fixed sampling in time domain that why IFFT is easy to apply. Please correct me if am wrong.
>
> Why would you want any other function to invert the direction of the
> NFFT than an IDFT? Any finite set of the equispaced Fourier
> coefficients could represent any of an infinite number of NFFT'd
> nonequispaced sample sets. So, how would you choose one and why?

-------------------------------------------------------------------------------------------------------
> More like: In some cases of nonequispaced samples, the NFFT can
> produce equispaced Fourier coefficients.

So you are saying, that when we have irregular sampling in one domain by application of NFFT or IDFT, we will get regular sampling in other domain, than why we cant we apply IFFT on it

> Why would you want any other function to invert the direction of the
> NFFT than an IDFT? Any finite set of the equispaced Fourier
> coefficients could represent any of an infinite number of NFFT'd
> nonequispaced sample sets. So, how would you choose one and why?

Actually my question was about how IFFT is easy to invert than IDFT. Is it because IFFT has equispaced sampling and which make A transpose equal to A conjugate.

And how NFFT can be inverted. I am inverting NFFT as it will be faster than IDFT

> > ...
>
> Dale B. Dalrymple

On Jun 27, 4:25 pm, "guj " <gulatiaks...@gmail.com> wrote:
> 1. When we have irregular sampling, we can use NDFT on it instead of FFT
> NDFT equation
> f_j = \sum_{k=-N/2}^{N/2-1} \hat f_k e^{(-2 *pi*i*k*x_j)}
>
> k= (-N/2:N/2-1)
> x_j=time domain (j=0,1,2____M-1)
>
> So what my question is, whenever we have non uniform sampling in the one domain will we get uniform sampling in another domain. For ex if my time domain >is irregular, will i be getting regular sampling in frequency domain

Using the DFT you can specify whatever spectral sampling you wish.
See below.

> 2. Inverting NDFT is not a easy task as in FFT, In ifft A inverse is equal to A conjugate, because of uniform sampling or fixed sampling in time domain that >why IFFT is easy to apply. Please correct me if am wrong.

Correct.

In the DFT function below, two forms of spectra
(Fourier and Least-Squares) are calculated for arbitrary
temporal sampling.

Then their inverses are calculated and compared with
the original function.

This DFT function was written more for understanding than
for practicality.

Much faster versions of the DFT can be found by searching
with the keyword "nfft"

From

http://groups.google.com/group/comp.soft-sys.matlab/
msg/a7a4479b8b402719

Newsgroups: comp.soft-sys.matlab, comp.dsp, sci.math.num-analysis
From: Greg Heath <he...@alumni.brown.edu>
Date: Tue, 13 May 2008 23:16:00 -0700 (PDT)
Subject: Re: Non-uniform Spacing

function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)

% function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
%
% Modification of AJ Johnson's dft for nonuniform sampling
%
% Computes XFT (Discrete Fourier Transform) at frequencies
% given in f, given samples x taken at times t:
%
% XFT(f) = sum(k=1,N){ dts(k) *x(k) * exp(-2*pi*j*t(k)*f) }
% = W *(x.*dts)
%
% where dts is a symmetrized modification of diff(t).
%
% Also computes the Least-Squared-Error Spectrum at
% frequencies given in f, given samples x taken at
% times t:
%
% XLS(f) = (W'\x)./dfs;
%
% where dfs is a symmetrized modification of diff(f).
%
% NMSEFT is the normalized mean-square-error of reconstucting
% x from X using the Inverse Fourier Transform formula. If
% mean(x) = 0, then the MSE is unnormalized.
%
% NMSELS is the normalized mean-square-error of reconstucting
% x from X using Least Squares. If mean(x) = 0, then the MSE
% is unnormalized.
%
% For comparison with MATLAB's FFT when the spacing is uniform,
% double the end values x(1) and x(end) and divide X by dt0 =
% mean(diff(t))

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

N = length(x);
if length(t)~= N
   error('x and t do not have the same length')
end;

dt = diff(t); % asymmetric "dt"
dts = 0.5*([dt; 0]+[0; dt]); % symmetric "dt"
meanx = sum(x.*dts)/sum(dts);

df = diff(f); % asymmetric "df"
dfs = 0.5*([df; 0]+[0; df]); % symmetric "df"

W = exp(-2*pi*j * f*t');

XFT = W * (x.*dts);
XLS = (W'\x)./dfs;

xFT = real(W'*(XFT.*dfs));
xLS = real(W'*(XLS.*dfs));

MSE0 = mse(abs(x-meanx));
if MSE0 == 0, MSE0 = 1, end;

NMSEFT = mse(abs(x-xFT))/MSE0;
NMSELS = mse(abs(x-xLS))/MSE0;

return

Greg <heath@alumni.brown.edu> wrote in message <6ced5282-e4f9-4712-9546-158d71c222b0@j14g2000vbp.googlegroups.com>...
> On Jun 27, 4:25?pm, "guj " <gulatiaks...@gmail.com> wrote:
> > 1. When we have irregular sampling, we can use NDFT on it instead of FFT
> > NDFT equation
> > f_j = \sum_{k=-N/2}^{N/2-1} \hat f_k e^{(-2 *pi*i*k*x_j)}
> >
> > k= (-N/2:N/2-1)
> > x_j=time domain (j=0,1,2____M-1)
> >
> > So what my question is, whenever we have non uniform sampling in the one domain will we get uniform sampling in another domain. For ex if my time domain >is irregular, will i be getting regular sampling in frequency domain
>
> Using the DFT you can specify whatever spectral sampling you wish.
> See below.
>
> > 2. Inverting NDFT is not a easy task as in FFT, In ifft A inverse is equal to A conjugate, because of uniform sampling or fixed sampling in time domain that >why IFFT is easy to apply. Please correct me if am wrong.
>
> Correct.
>
> In the DFT function below, two forms of spectra
> (Fourier and Least-Squares) are calculated for arbitrary
> temporal sampling.
>
> Then their inverses are calculated and compared with
> the original function.
>
> This DFT function was written more for understanding than
> for practicality.
>
> Much faster versions of the DFT can be found by searching
> with the keyword "nfft"
>
> From
>
> http://groups.google.com/group/comp.soft-sys.matlab/
> msg/a7a4479b8b402719
>
> Newsgroups: comp.soft-sys.matlab, comp.dsp, sci.math.num-analysis
> From: Greg Heath <he...@alumni.brown.edu>
> Date: Tue, 13 May 2008 23:16:00 -0700 (PDT)
> Subject: Re: Non-uniform Spacing
>
> function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
>
> % function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
> %
> % Modification of AJ Johnson's dft for nonuniform sampling
> %
> % Computes XFT (Discrete Fourier Transform) at frequencies
> % given in f, given samples x taken at times t:
> %
> % XFT(f) = sum(k=1,N){ dts(k) *x(k) * exp(-2*pi*j*t(k)*f) }
> % = W *(x.*dts)
> %
> % where dts is a symmetrized modification of diff(t).
> %
> % Also computes the Least-Squared-Error Spectrum at
> % frequencies given in f, given samples x taken at
> % times t:
> %
> % XLS(f) = (W'\x)./dfs;
> %
> % where dfs is a symmetrized modification of diff(f).
> %
> % NMSEFT is the normalized mean-square-error of reconstucting
> % x from X using the Inverse Fourier Transform formula. If
> % mean(x) = 0, then the MSE is unnormalized.
> %
> % NMSELS is the normalized mean-square-error of reconstucting
> % x from X using Least Squares. If mean(x) = 0, then the MSE
> % is unnormalized.
> %
> % For comparison with MATLAB's FFT when the spacing is uniform,
> % double the end values x(1) and x(end) and divide X by dt0 =
> % mean(diff(t))
>
> x = x(:); % Format 'x' into a column vector
> t = t(:); % Format 't' into a column vector
> f = f(:); % Format 'f' into a column vector
>
> N = length(x);
> if length(t)~= N
> error('x and t do not have the same length')
> end;
>
> dt = diff(t); % asymmetric "dt"
> dts = 0.5*([dt; 0]+[0; dt]); % symmetric "dt"
> meanx = sum(x.*dts)/sum(dts);
>
> df = diff(f); % asymmetric "df"
> dfs = 0.5*([df; 0]+[0; df]); % symmetric "df"
>
> W = exp(-2*pi*j * f*t');
>
> XFT = W * (x.*dts);
> XLS = (W'\x)./dfs;
>
> xFT = real(W'*(XFT.*dfs));
> xLS = real(W'*(XLS.*dfs));
>
> MSE0 = mse(abs(x-meanx));
> if MSE0 == 0, MSE0 = 1, end;
>
> NMSEFT = mse(abs(x-xFT))/MSE0;
> NMSELS = mse(abs(x-xLS))/MSE0;
>
> return
>


Well,

DFT can be bench mark for NFFT results, because i cant check my fast nfft results with FFT. Again i am having few questions, and i think i am confuse........

1. We are having irregular sampling in time domain, and we are getting regular sampling in frequency domain, why cant i invert it using IFFT even when my sampling is regular..and Can NFFT results can be inverted using IDFT.

2. What is difference between Fourier spectra and least square spectra, I thought Least Squares are method to get fourier spectra

On Jun 29, 9:13 am, "guj " <gulatiaks...@gmail.com> wrote:
> Greg <he...@alumni.brown.edu> wrote in message <6ced5282-e4f9-4712-9546-158d71c22...@j14g2000vbp.googlegroups.com>...
> > On Jun 27, 4:25?pm, "guj " <gulatiaks...@gmail.com> wrote:
> > > 1. When we have irregular sampling, we can use NDFT on it instead of FFT
> > > NDFT equation
> > > f_j = \sum_{k=-N/2}^{N/2-1} \hat f_k e^{(-2 *pi*i*k*x_j)}
>
> > > k= (-N/2:N/2-1)
> > > x_j=time domain (j=0,1,2____M-1)
>
> > > So what my question is, whenever we have non uniform sampling in the one domain will we get uniform sampling in another domain. For ex if my time domain >is irregular, will i be getting regular sampling in frequency domain
>
> > Using the DFT you can specify whatever spectral sampling you wish.
> > See below.
>
> > > 2. Inverting NDFT is not a easy task as in FFT, In ifft A inverse is equal to A conjugate, because of uniform sampling or fixed sampling in time domain that >why IFFT is easy to apply. Please correct me if am wrong.
>
> > Correct.
>
> > In the DFT function below, two forms of spectra
> > (Fourier and Least-Squares) are calculated for arbitrary
> > temporal sampling.
>
> > Then their inverses are calculated and compared with
> > the original function.
>
> > This DFT function was written more for understanding than
> > for practicality.
>
> > Much faster versions of the DFT can be found by searching
> > with the keyword "nfft"
>
> > From
>
> >http://groups.google.com/group/comp.soft-sys.matlab/
> > msg/a7a4479b8b402719
>
> > Newsgroups: comp.soft-sys.matlab, comp.dsp, sci.math.num-analysis
> > From: Greg Heath <he...@alumni.brown.edu>
> > Date: Tue, 13 May 2008 23:16:00 -0700 (PDT)
> > Subject: Re: Non-uniform Spacing
>
> > function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
>
> > % function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
> > %
> > % Modification of AJ Johnson's dft for nonuniform sampling
> > %
> > % Computes XFT (Discrete Fourier Transform) at frequencies
> > % given in f, given samples x taken at times t:
> > %
> > % XFT(f) = sum(k=1,N){ dts(k) *x(k) * exp(-2*pi*j*t(k)*f) }
> > % = W *(x.*dts)
> > %
> > % where dts is a symmetrized modification of diff(t).
> > %
> > % Also computes the Least-Squared-Error Spectrum at
> > % frequencies given in f, given samples x taken at
> > % times t:
> > %
> > % XLS(f) = (W'\x)./dfs;
> > %
> > % where dfs is a symmetrized modification of diff(f).
> > %
> > % NMSEFT is the normalized mean-square-error of reconstucting
> > % x from X using the Inverse Fourier Transform formula. If
> > % mean(x) = 0, then the MSE is unnormalized.
> > %
> > % NMSELS is the normalized mean-square-error of reconstucting
> > % x from X using Least Squares. If mean(x) = 0, then the MSE
> > % is unnormalized.
> > %
> > % For comparison with MATLAB's FFT when the spacing is uniform,
> > % double the end values x(1) and x(end) and divide X by dt0 =
> > % mean(diff(t))
>
> > x = x(:); % Format 'x' into a column vector
> > t = t(:); % Format 't' into a column vector
> > f = f(:); % Format 'f' into a column vector
>
> > N = length(x);
> > if length(t)~= N
> > error('x and t do not have the same length')
> > end;
>
> > dt = diff(t); % asymmetric "dt"
> > dts = 0.5*([dt; 0]+[0; dt]); % symmetric "dt"
> > meanx = sum(x.*dts)/sum(dts);
>
> > df = diff(f); % asymmetric "df"
> > dfs = 0.5*([df; 0]+[0; df]); % symmetric "df"
>
> > W = exp(-2*pi*j * f*t');
>
> > XFT = W * (x.*dts);
> > XLS = (W'\x)./dfs;
>
> > xFT = real(W'*(XFT.*dfs));
> > xLS = real(W'*(XLS.*dfs));
>
> > MSE0 = mse(abs(x-meanx));
> > if MSE0 == 0, MSE0 = 1, end;
>
> > NMSEFT = mse(abs(x-xFT))/MSE0;
> > NMSELS = mse(abs(x-xLS))/MSE0;
>
> > return
>
> Well,
>
.> DFT can be bench mark for NFFT results, because i cant check my
fast nfft results with FFT. Again i am having few questions, and i
think i am confuse........

There are many potential sources of confusion. One is from the
meanings of the term 'fast'. In the conventional equispaced DFT and
FFT, 'fast' means the the results of convolutions with basis functions
in the definition of the DFT can be calculated in a time proportional
to the log of the convolution size instead of proportional to the
convolution size. This has been a useful speed-up and it gets better
as the convolution size grows. This is not what you can expect 'fast'
to mean in the label of any other algorithm. 'Fast' commonly seems to
mean 'the fastest way the programmer know that day'. Since there have
been a lot of programmers and a lot of days, there are a lot of
meanings of 'fast'. So don't count on the DFT=>FFT type performance
comparison from the word 'fast'. Check the algorithm, results and
benchmarks to find what 'fast' means each time.

.>
.> 1. We are having irregular sampling in time domain, and we are
getting regular sampling in frequency domain, why cant i invert it
using IFFT even when my sampling is regular..and Can NFFT results can
be inverted using IDFT.

However you got the equispaced spectrum, you can get equispaced time
samples that correspond via a conventional IFFT/IDFT. Whether this is
'inversion' of the NFFT is a semantic question and so, another
potential source of confusion.

.> ...
.
Dale B. Dalrymple

dbd <dbd@ieee.org> wrote in message <66f78a0c-7e01-41c9-b57e-4f7a967bc853@f10g2000vbf.googlegroups.com>...
> On Jun 29, 9:13 am, "guj " <gulatiaks...@gmail.com> wrote:
> > Greg <he...@alumni.brown.edu> wrote in message <6ced5282-e4f9-4712-9546-158d71c22...@j14g2000vbp.googlegroups.com>...
> > > On Jun 27, 4:25?pm, "guj " <gulatiaks...@gmail.com> wrote:
> > > > 1. When we have irregular sampling, we can use NDFT on it instead of FFT
> > > > NDFT equation
> > > > f_j = \sum_{k=-N/2}^{N/2-1} \hat f_k e^{(-2 *pi*i*k*x_j)}
> >
> > > > k= (-N/2:N/2-1)
> > > > x_j=time domain (j=0,1,2____M-1)
> >
> > > > So what my question is, whenever we have non uniform sampling in the one domain will we get uniform sampling in another domain. For ex if my time domain >is irregular, will i be getting regular sampling in frequency domain
> >
> > > Using the DFT you can specify whatever spectral sampling you wish.
> > > See below.
> >
> > > > 2. Inverting NDFT is not a easy task as in FFT, In ifft A inverse is equal to A conjugate, because of uniform sampling or fixed sampling in time domain that >why IFFT is easy to apply. Please correct me if am wrong.
> >
> > > Correct.
> >
> > > In the DFT function below, two forms of spectra
> > > (Fourier and Least-Squares) are calculated for arbitrary
> > > temporal sampling.
> >
> > > Then their inverses are calculated and compared with
> > > the original function.
> >
> > > This DFT function was written more for understanding than
> > > for practicality.
> >
> > > Much faster versions of the DFT can be found by searching
> > > with the keyword "nfft"
> >
> > > From
> >
> > >http://groups.google.com/group/comp.soft-sys.matlab/
> > > msg/a7a4479b8b402719
> >
> > > Newsgroups: comp.soft-sys.matlab, comp.dsp, sci.math.num-analysis
> > > From: Greg Heath <he...@alumni.brown.edu>
> > > Date: Tue, 13 May 2008 23:16:00 -0700 (PDT)
> > > Subject: Re: Non-uniform Spacing
> >
> > > function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
> >
> > > % function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
> > > %
> > > % Modification of AJ Johnson's dft for nonuniform sampling
> > > %
> > > % Computes XFT (Discrete Fourier Transform) at frequencies
> > > % given in f, given samples x taken at times t:
> > > %
> > > % XFT(f) = sum(k=1,N){ dts(k) *x(k) * exp(-2*pi*j*t(k)*f) }
> > > % = W *(x.*dts)
> > > %
> > > % where dts is a symmetrized modification of diff(t).
> > > %
> > > % Also computes the Least-Squared-Error Spectrum at
> > > % frequencies given in f, given samples x taken at
> > > % times t:
> > > %
> > > % XLS(f) = (W'\x)./dfs;
> > > %
> > > % where dfs is a symmetrized modification of diff(f).
> > > %
> > > % NMSEFT is the normalized mean-square-error of reconstucting
> > > % x from X using the Inverse Fourier Transform formula. If
> > > % mean(x) = 0, then the MSE is unnormalized.
> > > %
> > > % NMSELS is the normalized mean-square-error of reconstucting
> > > % x from X using Least Squares. If mean(x) = 0, then the MSE
> > > % is unnormalized.
> > > %
> > > % For comparison with MATLAB's FFT when the spacing is uniform,
> > > % double the end values x(1) and x(end) and divide X by dt0 =
> > > % mean(diff(t))
> >
> > > x = x(:); % Format 'x' into a column vector
> > > t = t(:); % Format 't' into a column vector
> > > f = f(:); % Format 'f' into a column vector
> >
> > > N = length(x);
> > > if length(t)~= N
> > > error('x and t do not have the same length')
> > > end;
> >
> > > dt = diff(t); % asymmetric "dt"
> > > dts = 0.5*([dt; 0]+[0; dt]); % symmetric "dt"
> > > meanx = sum(x.*dts)/sum(dts);
> >
> > > df = diff(f); % asymmetric "df"
> > > dfs = 0.5*([df; 0]+[0; df]); % symmetric "df"
> >
> > > W = exp(-2*pi*j * f*t');
> >
> > > XFT = W * (x.*dts);
> > > XLS = (W'\x)./dfs;
> >
> > > xFT = real(W'*(XFT.*dfs));
> > > xLS = real(W'*(XLS.*dfs));
> >
> > > MSE0 = mse(abs(x-meanx));
> > > if MSE0 == 0, MSE0 = 1, end;
> >
> > > NMSEFT = mse(abs(x-xFT))/MSE0;
> > > NMSELS = mse(abs(x-xLS))/MSE0;
> >
> > > return
> >
> > Well,
> >
> .> DFT can be bench mark for NFFT results, because i cant check my
> fast nfft results with FFT. Again i am having few questions, and i
> think i am confuse........
>
> There are many potential sources of confusion. One is from the
> meanings of the term 'fast'. In the conventional equispaced DFT and
> FFT, 'fast' means the the results of convolutions with basis functions
> in the definition of the DFT can be calculated in a time proportional
> to the log of the convolution size instead of proportional to the
> convolution size. This has been a useful speed-up and it gets better
> as the convolution size grows. This is not what you can expect 'fast'
> to mean in the label of any other algorithm. 'Fast' commonly seems to
> mean 'the fastest way the programmer know that day'. Since there have
> been a lot of programmers and a lot of days, there are a lot of
> meanings of 'fast'. So don't count on the DFT=>FFT type performance
> comparison from the word 'fast'. Check the algorithm, results and
> benchmarks to find what 'fast' means each time.
>
> .>
> .> 1. We are having irregular sampling in time domain, and we are
> getting regular sampling in frequency domain, why cant i invert it
> using IFFT even when my sampling is regular..and Can NFFT results can
> be inverted using IDFT.
>
> However you got the equispaced spectrum, you can get equispaced time
> samples that correspond via a conventional IFFT/IDFT. Whether this is
> 'inversion' of the NFFT is a semantic question and so, another
> potential source of confusion.
>
> .> ...
> .
> Dale B. Dalrymple



> However you got the equispaced spectrum, you can get equispaced time
> samples that correspond via a conventional IFFT/IDFT. Whether this is
> 'inversion' of the NFFT is a semantic question and so, another
> potential source of confusion

But we started with the irregular sampling, how can IDFT will give equispaced sampling....Results should be completely different on application of IDFT and FFT on this sample. IDFT will going to reconstruct the original signal where as FFT will construct equispaced signal which will be completely wrong representation of the original signal. Correct me if i am wrong

2. And which is the best way to compare the algorithms in MATLAB. Will you suggest tic toc; to be appropriate way to compare IDFT and FFT ....

3. And again i am anticipating same results from NFFT and IDFT in terms of reconstruction of signal. As most of the papers i read have some minimal error between them.

4. Again I am always amazed in most of papers for NFFT, i never seen author reconstructing a signal back, they are more concerned with the Fourier spectra. I am wondering why dont they reconstruct it back. Like Greengard paper, although application is on the MRI images but what is the use of algorithm if you cant go back in original domain.

On Jun 29, 12:13 pm, "guj " <gulatiaks...@gmail.com> wrote:
> Greg <he...@alumni.brown.edu> wrote in message <6ced5282-e4f9-4712-9546-158d71c22...@j14g2000vbp.googlegroups.com>...
> > On Jun 27, 4:25?pm, "guj " <gulatiaks...@gmail.com> wrote:
> > > 1. When we have irregular sampling, we can use NDFT on it instead of FFT
> > > NDFT equation
> > > f_j = \sum_{k=-N/2}^{N/2-1} \hat f_k e^{(-2 *pi*i*k*x_j)}
>
> > > k= (-N/2:N/2-1)
> > > x_j=time domain (j=0,1,2____M-1)
>
> > > So what my question is, whenever we have non uniform sampling in the one domain will we get uniform sampling in another domain. For ex if my time domain >is irregular, will i be getting regular sampling in frequency domain
>
> > Using the DFT you can specify whatever spectral sampling you wish.
> > See below.
>
> > > 2. Inverting NDFT is not a easy task as in FFT, In ifft A inverse is equal to A conjugate, because of uniform sampling or fixed sampling in time domain that >why IFFT is easy to apply. Please correct me if am wrong.
>
> > Correct.
>
> > In the DFT function below, two forms of spectra
> > (Fourier and Least-Squares) are calculated for arbitrary
> > temporal sampling.
>
> > Then their inverses are calculated and compared with
> > the original function.
>
> > This DFT function was written more for understanding than
> > for practicality.
>
> > Much faster versions of the DFT can be found by searching
> > with the keyword "nfft"
>
> > From
>
> >http://groups.google.com/group/comp.soft-sys.matlab/
> > msg/a7a4479b8b402719
>
> > Newsgroups: comp.soft-sys.matlab, comp.dsp, sci.math.num-analysis
> > From: Greg Heath <he...@alumni.brown.edu>
> > Date: Tue, 13 May 2008 23:16:00 -0700 (PDT)
> > Subject: Re: Non-uniform Spacing
>
> > function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
>
> > % function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
> > %
> > % Modification of AJ Johnson's dft for nonuniform sampling
> > %
> > % Computes XFT (Discrete Fourier Transform) at frequencies
> > % given in f, given samples x taken at times t:
> > %
> > % XFT(f) = sum(k=1,N){ dts(k) *x(k) * exp(-2*pi*j*t(k)*f) }
> > % = W *(x.*dts)
> > %
> > % where dts is a symmetrized modification of diff(t).
> > %
> > % Also computes the Least-Squared-Error Spectrum at
> > % frequencies given in f, given samples x taken at
> > % times t:
> > %
> > % XLS(f) = (W'\x)./dfs;
> > %
> > % where dfs is a symmetrized modification of diff(f).
> > %
> > % NMSEFT is the normalized mean-square-error of reconstucting
> > % x from X using the Inverse Fourier Transform formula. If
> > % mean(x) = 0, then the MSE is unnormalized.
> > %
> > % NMSELS is the normalized mean-square-error of reconstucting
> > % x from X using Least Squares. If mean(x) = 0, then the MSE
> > % is unnormalized.
> > %
> > % For comparison with MATLAB's FFT when the spacing is uniform,
> > % double the end values x(1) and x(end) and divide X by dt0 =
> > % mean(diff(t))
>
> > x = x(:); % Format 'x' into a column vector
> > t = t(:); % Format 't' into a column vector
> > f = f(:); % Format 'f' into a column vector
>
> > N = length(x);
> > if length(t)~= N
> > error('x and t do not have the same length')
> > end;
>
> > dt = diff(t); % asymmetric "dt"
> > dts = 0.5*([dt; 0]+[0; dt]); % symmetric "dt"
> > meanx = sum(x.*dts)/sum(dts);
>
> > df = diff(f); % asymmetric "df"
> > dfs = 0.5*([df; 0]+[0; df]); % symmetric "df"
>
> > W = exp(-2*pi*j * f*t');
>
> > XFT = W * (x.*dts);
> > XLS = (W'\x)./dfs; XLS = (W'\x)./dfs;
>
> > xFT = real(W'*(XFT.*dfs));
> > xLS = real(W'*(XLS.*dfs));
>
> > MSE0 = mse(abs(x-meanx));
> > if MSE0 == 0, MSE0 = 1, end;
>
> > NMSEFT = mse(abs(x-xFT))/MSE0;
> > NMSELS = mse(abs(x-xLS))/MSE0;
>
> > return
>
> Well,
>
> DFT can be bench mark for NFFT results, because i cant check my fast nfft results with FFT. Again i am having few questions, and i think i am confuse........
>
> 1. We are having irregular sampling in time domain, and we are getting regular sampling in frequency domain, why cant i invert it using IFFT even when my sampling is regular..

IFFT assumes both spacings are uniform

>and Can NFFT results can be inverted using IDFT.

Only for uniform sampling,

 > 2. What is difference between Fourier spectra and least square
spectra,
 I thought Least Squares are method to get fourier spectra

The defining equation is

x = W'*(X.*dfs);

i.e., that x can be represented by a sum of
sines and cosines. The minimum norm and Basic
LS solutions are

XLSmn = (pinv(W')*x)./dfs
XLSb = (W'\x)./dfs

whereas the "Fourier Spectra" are given by

XFT = W * (x.*dts)

The least squares solutions reduce to the Fourier
spectra only under special conditions of W and
dts.

Hope this helps.

Greg

On Jul 4, 7:17 am, Greg <he...@alumni.brown.edu> wrote:
> On Jun 29, 12:13 pm, "guj " <gulatiaks...@gmail.com> wrote:
>
>
>
>
>
> > Greg <he...@alumni.brown.edu> wrote in message <6ced5282-e4f9-4712-9546-158d71c22...@j14g2000vbp.googlegroups.com>...
> > > On Jun 27, 4:25?pm, "guj " <gulatiaks...@gmail.com> wrote:
> > > > 1. When we have irregular sampling, we can use NDFT on it instead of FFT
> > > > NDFT equation
> > > > f_j = \sum_{k=-N/2}^{N/2-1} \hat f_k e^{(-2 *pi*i*k*x_j)}
>
> > > > k= (-N/2:N/2-1)
> > > > x_j=time domain (j=0,1,2____M-1)
>
> > > > So what my question is, whenever we have non uniform sampling in the one domain will we get uniform sampling in another domain. For ex if my time domain >is irregular, will i be getting regular sampling in frequency domain
>
> > > Using the DFT you can specify whatever spectral sampling you wish.
> > > See below.
>
> > > > 2. Inverting NDFT is not a easy task as in FFT, In ifft A inverse is equal to A conjugate, because of uniform sampling or fixed sampling in time domain that >why IFFT is easy to apply. Please correct me if am wrong.
>
> > > Correct.
>
> > > In the DFT function below, two forms of spectra
> > > (Fourier and Least-Squares) are calculated for arbitrary
> > > temporal sampling.
>
> > > Then their inverses are calculated and compared with
> > > the original function.
>
> > > This DFT function was written more for understanding than
> > > for practicality.
>
> > > Much faster versions of the DFT can be found by searching
> > > with the keyword "nfft"
>
> > > From
>
> > >http://groups.google.com/group/comp.soft-sys.matlab/
> > > msg/a7a4479b8b402719
>
> > > Newsgroups: comp.soft-sys.matlab, comp.dsp, sci.math.num-analysis
> > > From: Greg Heath <he...@alumni.brown.edu>
> > > Date: Tue, 13 May 2008 23:16:00 -0700 (PDT)
> > > Subject: Re: Non-uniform Spacing
>
> > > function   [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
>
> > > % function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
> > > %
> > > % Modification of AJ Johnson's dft for nonuniform sampling
> > > %
> > > % Computes XFT (Discrete Fourier Transform) at frequencies
> > > % given in f, given samples x taken at times t:
> > > %
> > > % XFT(f) = sum(k=1,N){ dts(k) *x(k) * exp(-2*pi*j*t(k)*f) }
> > > %        = W *(x.*dts)
> > > %
> > > % where dts is a symmetrized modification of diff(t).
> > > %
> > > % Also computes the Least-Squared-Error Spectrum at
> > > % frequencies given in f, given samples x taken at
> > > % times t:
> > > %
> > > % XLS(f) = (W'\x)./dfs;
> > > %
> > > % where dfs is a symmetrized modification of diff(f).
> > > %
> > > % NMSEFT is the normalized mean-square-error of reconstucting
> > > % x from X using the Inverse Fourier Transform formula. If
> > > % mean(x) = 0, then the MSE is unnormalized.
> > > %
> > > % NMSELS is the normalized mean-square-error of reconstucting
> > > % x from X using Least Squares. If mean(x) = 0, then the MSE
> > > % is unnormalized.
> > > %
> > > % For comparison with MATLAB's FFT when the spacing is uniform,
> > > % double the end values x(1) and x(end) and divide X by dt0 =
> > > % mean(diff(t))
>
> > > x = x(:); % Format 'x' into a column vector
> > > t = t(:); % Format 't' into a column vector
> > > f = f(:); % Format 'f' into a column vector
>
> > > N = length(x);
> > > if length(t)~= N
> > >    error('x and t do not have the same length')
> > > end;
>
> > > dt    = diff(t);                % asymmetric "dt"
> > > dts   = 0.5*([dt; 0]+[0; dt]);  % symmetric "dt"
> > > meanx = sum(x.*dts)/sum(dts);
>
> > > df   = diff(f);                 % asymmetric "df"
> > > dfs  = 0.5*([df; 0]+[0; df]);   % symmetric "df"
>
> > > W    = exp(-2*pi*j * f*t');
>
> > > XFT  = W * (x.*dts);
> > > XLS  = (W'\x)./dfs; XLS  = (W'\x)./dfs;
>
> > > xFT = real(W'*(XFT.*dfs));
> > > xLS = real(W'*(XLS.*dfs));
>
> > > MSE0  = mse(abs(x-meanx));
> > > if MSE0 == 0, MSE0 = 1, end;
>
> > > NMSEFT = mse(abs(x-xFT))/MSE0;
> > > NMSELS = mse(abs(x-xLS))/MSE0;
>
> > > return
>
> > Well,
>
> > DFT can be bench mark for NFFT results, because i cant check my fast nfft results with FFT.  Again i am having few questions, and i think i am confuse........
>
> > 1. We are having irregular sampling in time domain, and we are getting regular sampling in frequency domain, why cant i invert it using IFFT even when my sampling is regular..
>
> IFFT assumes both spacings are uniform
>
> >and Can NFFT results can be inverted using IDFT.
>
> Only for uniform sampling,
>
>  > 2. What is difference between Fourier spectra and least square
> spectra,
>  I thought Least Squares are method to get fourier spectra
>
> The defining equation is
>
> x = W'*(X.*dfs);
>
> i.e., that x can be represented by a sum of
> sines and cosines. The minimum norm and Basic
> LS solutions are
>
> XLSmn = (pinv(W')*x)./dfs
> XLSb   = (W'\x)./dfs
>
> whereas the "Fourier Spectra" are given by
>
> XFT   =  W * (x.*dts)
>
> The least squares solutions reduce to the Fourier
> spectra only under special conditions of W and
> dts.

If you wish to invert the "Fourier Spectrum"
you have to start with the above equation
to get

xFTmn = (pinv(W)*XFT)./dts;

xFTb = (W\XFT)./dts;

Hope this helps.

Greg

On Jun 28, 12:33 pm, Greg <he...@alumni.brown.edu> wrote:
> On Jun 27, 4:25 pm, "guj " <gulatiaks...@gmail.com> wrote:
-----SNIP
> function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
>
> % function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
> %
> % Modification of AJ Johnson's dft for nonuniform sampling
> %
> % Computes XFT (Discrete Fourier Transform) at frequencies
> % given in f, given samples x taken at times t:
> %
> % XFT(f) = sum(k=1,N){ dts(k) *x(k) * exp(-2*pi*j*t(k)*f) }
> % = W *(x.*dts)
> %
> % where dts is a symmetrized modification of diff(t).
> %
> % Also computes the Least-Squared-Error Spectrum at
> % frequencies given in f, given samples x taken at
> % times t:
> %
> % XLS(f) = (W'\x)./dfs;
> %
> % where dfs is a symmetrized modification of diff(f).
> %
> % NMSEFT is the normalized mean-square-error of reconstucting
> % x from X using the Inverse Fourier Transform formula. If
> % mean(x) = 0, then the MSE is unnormalized.

Correction:

If mean(x) = x, i.e., x is constant, then the MSE is unnormalized.


> % NMSELS is the normalized mean-square-error of reconstucting
> % x from X using Least Squares. If mean(x) = 0, then the MSE
> % is unnormalized.

Correction:

If mean(x) = x, i.e., x is constant, then the MSE is unnormalized.

> % For comparison with MATLAB'sFFTwhen the spacing is uniform,
> % double the end values x(1) and x(end) and divide X by dt0 =
> % mean(diff(t))

-----SNIP

Hope this helps.

Greg

Greg <heath@alumni.brown.edu> wrote in message <e104f561-edaa-4505-84c2-cf6bcfb49179@s31g2000yqs.googlegroups.com>...
> On Jun 28, 12:33 pm, Greg <he...@alumni.brown.edu> wrote:
> > On Jun 27, 4:25 pm, "guj " <gulatiaks...@gmail.com> wrote:
> -----SNIP
> > function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
> >
> > % function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
> > %
> > % Modification of AJ Johnson's dft for nonuniform sampling
> > %
> > % Computes XFT (Discrete Fourier Transform) at frequencies
> > % given in f, given samples x taken at times t:
> > %
> > % XFT(f) = sum(k=1,N){ dts(k) *x(k) * exp(-2*pi*j*t(k)*f) }
> > % = W *(x.*dts)
> > %
> > % where dts is a symmetrized modification of diff(t).
> > %
> > % Also computes the Least-Squared-Error Spectrum at
> > % frequencies given in f, given samples x taken at
> > % times t:
> > %
> > % XLS(f) = (W'\x)./dfs;
> > %
> > % where dfs is a symmetrized modification of diff(f).
> > %
> > % NMSEFT is the normalized mean-square-error of reconstucting
> > % x from X using the Inverse Fourier Transform formula. If
> > % mean(x) = 0, then the MSE is unnormalized.
>
> Correction:
>
> If mean(x) = x, i.e., x is constant, then the MSE is unnormalized.
>
>
> > % NMSELS is the normalized mean-square-error of reconstucting
> > % x from X using Least Squares. If mean(x) = 0, then the MSE
> > % is unnormalized.
>
> Correction:
>
> If mean(x) = x, i.e., x is constant, then the MSE is unnormalized.
>
> > % For comparison with MATLAB'sFFTwhen the spacing is uniform,
> > % double the end values x(1) and x(end) and divide X by dt0 =
> > % mean(diff(t))
>
> -----SNIP
>
> Hope this helps.
>
> Greg


What are your comments on the code below:
FFT is giving the same result as DFT for Non uniform sampling. I am curious to know the difference between NDFT and DFT ...Notation


clear
dt=.01;
N=101;
func=sin([0:N-1]/4);
f=1/dt/N/2*[-N:2:N-2];

figure(1)
clf
subplot(3,1,1)
plot(dt*[0:N-1],func)
subplot(3,1,2)
plot(f,fftshift(abs(fft(func))))
k=1:N;
n=1:N;
DFT=exp(-i*2*pi*((k(:)-1)*(n-1)/N));
subplot(3,1,3)
plot(f,fftshift(abs(DFT*func(:))))

z=round(rand(1,N));
temp1=func;
temp2=z.*func;
lives=find(z~=0);
func=temp2(lives);
DFT=DFT(:,lives);

figure(2)
clf
subplot(3,1,1)
plot(dt*[0:N-1],temp1,dt*[0:N-1],temp2)
subplot(3,1,2)
plot(f,fftshift(abs(fft(temp2))))
subplot(3,1,3)
plot(f,fftshift(abs(DFT*func(:))))

Here is NDFT, algorithm

freq=(-N/2):(N/2-1); f_hat=a;
      f=zeros(M,1);
      for k=1:N
        f=f+f_hat(k).*exp(-2*pi*i*x*freq(k));
      end;
So question is Which one is right for Non uniform sampling..Is matlab DFT formula (which i have taken from help) is same as FFT and can handle only fixed sample...what factor in DFT algorithm constraining it for fixed sampling.

In DFT, algorithm we are multiplying our Coefficient with twiddle factor, that twiddle factor is equally spaced ...is that the constrain...

twiddle factor= exp(-2*pi*i*k*n/N) ..IN this when we divide it by N, we only mean to normalise it..isnt it..also 2pi is my sampling frequency ...

All these doubts are there because of the code which i have written above and i am dubious why its giving same result as fft ..Also what FFT do when it incur a irregular sampling....although it give wrong result but what is its working on such kind of input

On Jul 6, 1:47 pm, "guj " <gulatiaks...@gmail.com> wrote:

>
> What are your comments on the code below:
> FFT is giving the same result as DFT for Non uniform sampling. I am curious to know the difference between NDFT and DFT ...Notation

> CODE REMOVED

> So question is Which one is right for Non uniform sampling..

Neither

> Is matlab DFT formula (which i have taken from help) is same as FFT

Yes

> and can handle only fixed sample...

Yes

> what factor in DFT algorithm constraining it for fixed sampling.
>
> In DFT, algorithm we are multiplying our Coefficient with twiddle factor, that twiddle factor is equally spaced ...is that the constrain...
>

The FFT and the conventionally defined DFT it is equivalent to are
only defined for equispaced inputs and outputs when used to transform
from time to frequency domains. These functions follow the GIGO
principle. If you input anything else (Garbage In) , you will output
something else (Garbage Out)
.
> twiddle factor= exp(-2*pi*i*k*n/N) ..IN this when we divide it by N, we only mean to normalise it..isnt it..also 2pi is my sampling frequency ...
>
> All these doubts are there because of the code which i have written above and i am dubious why its giving same result as fft
That is what it is defined to do.

> ..Also what FFT do when it incur a irregular sampling....although it give wrong result but what is its working on such kind of input

Remember GIGO!


Dale B. Dalrymple

dbd <dbd@ieee.org> wrote in message <61a1276a-88b8-48a1-8883-215a2f29732f@q40g2000prh.googlegroups.com>...
> On Jul 6, 1:47 pm, "guj " <gulatiaks...@gmail.com> wrote:
>
> >
> > What are your comments on the code below:
> > FFT is giving the same result as DFT for Non uniform sampling. I am curious to know the difference between NDFT and DFT ...Notation
>
> > CODE REMOVED
>
> > So question is Which one is right for Non uniform sampling..
>
> Neither
>
> > Is matlab DFT formula (which i have taken from help) is same as FFT
>
> Yes
>
> > and can handle only fixed sample...



So MATLAB DFT Fornula which is

>
> Yes
>
> > what factor in DFT algorithm constraining it for fixed sampling.
> >
> > In DFT, algorithm we are multiplying our Coefficient with twiddle factor, that twiddle factor is equally spaced ...is that the constrain...
> >
>
> The FFT and the conventionally defined DFT it is equivalent to are
> only defined for equispaced inputs and outputs when used to transform
> from time to frequency domains. These functions follow the GIGO
> principle. If you input anything else (Garbage In) , you will output
> something else (Garbage Out)
> .
> > twiddle factor= exp(-2*pi*i*k*n/N) ..IN this when we divide it by N, we only mean to normalise it..isnt it..also 2pi is my sampling frequency ...
> >
> > All these doubts are there because of the code which i have written above and i am dubious why its giving same result as fft
> That is what it is defined to do.
>
> > ..Also what FFT do when it incur a irregular sampling....although it give wrong result but what is its working on such kind of input
>
> Remember GIGO!
>
>
> Dale B. Dalrymple




So DFT formula e
DFT = x(n) exp(-i*2*pi*((k(:)-1)*(n-1)/N is valid only for equispaced sampling

and NDFT formula is

 nonequispaced dft
%
% N/2-1
% f(j) = sum f_hat(k+N/2+1)*exp(-2*pi*i*k*x(j)), 1 <= j <= M.
% k=-N/2

where x(j) is non equispaced nodes

i think now i am on right track, This is Direct way of NDFT..there are also horners way and matrix approach..each take different computational resources and time. And DFT is just a DIRECT way of Fourier transform but with fixed sampling.....and FFT is a Butterfly approach of same DFT algorithm ....result will be same in both case and both handles the fixed sampling.

On Jul 6, 4:47 pm, "guj " <gulatiaks...@gmail.com> wrote:
> Greg <he...@alumni.brown.edu> wrote in message <e104f561-edaa-4505-84c2-cf6bcfb49...@s31g2000yqs.googlegroups.com>...
> > On Jun 28, 12:33 pm, Greg <he...@alumni.brown.edu> wrote:
> > > On Jun 27, 4:25 pm, "guj " <gulatiaks...@gmail.com> wrote:
> > -----SNIP
> > > function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
>
> > > % function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
> > > %
> > > % Modification of AJ Johnson's dft for nonuniform sampling
> > > %
> > > % Computes XFT (Discrete Fourier Transform) at frequencies
> > > % given in f, given samples x taken at times t:
> > > %
> > > % XFT(f) = sum(k=1,N){ dts(k) *x(k) * exp(-2*pi*j*t(k)*f) }
> > > % = W *(x.*dts)
> > > %
> > > % where dts is a symmetrized modification of diff(t).
> > > %
> > > % Also computes the Least-Squared-Error Spectrum at
> > > % frequencies given in f, given samples x taken at
> > > % times t:
> > > %
> > > % XLS(f) = (W'\x)./dfs;
> > > %
> > > % where dfs is a symmetrized modification of diff(f).
> > > %
> > > % NMSEFT is the normalized mean-square-error of reconstucting
> > > % x from X using the Inverse Fourier Transform formula. If
> > > % mean(x) = 0, then the MSE is unnormalized.
>
> > Correction:
>
> > If mean(x) = x, i.e., x is constant, then the MSE is unnormalized.
>
> > > % NMSELS is the normalized mean-square-error of reconstucting
> > > % x from X using Least Squares. If mean(x) = 0, then the MSE
> > > % is unnormalized.
>
> > Correction:
>
> > If mean(x) = x, i.e., x is constant, then the MSE is unnormalized.
>
> > > % For comparison with MATLAB'sFFTwhen the spacing is uniform,
> > > % double the end values x(1) and x(end) and divide X by dt0 =
> > > % mean(diff(t))
>
> > -----SNIP
>
> > Hope this helps.
>
> > Greg
>
> What are your comments on the code below:
> FFT is giving the same result as DFT for Non uniform sampling.

Both are inappropiarte for nonuniform sampling. See the above
code where nonconstant dt is taken into account.

> I am curious to know the difference between NDFT and DFT ...Notation
>
> clear
> dt=.01;
> N=101;
> func=sin([0:N-1]/4);

BETTER TO USE A COLUMN VECTOR

> f=1/dt/N/2*[-N:2:N-2];

INCORRECT FOR N ODD

> figure(1)
> clf
> subplot(3,1,1)
> plot(dt*[0:N-1],func)
> subplot(3,1,2)
> plot(f,fftshift(abs(fft(func))))

DIVIDE BY N TO GET CORRECT SCALE

> k=1:N;
> n=1:N;
> DFT=exp(-i*2*pi*((k(:)-1)*(n-1)/N));

POOR TERMINOLOGY CHANGE "DFT" TO "W"

> subplot(3,1,3)
> plot(f,fftshift(abs(DFT*func(:))))
>
> z=round(rand(1,N));
> temp1=func;
> temp2=z.*func;
> lives=find(z~=0);
> func=temp2(lives);

POOR TERMINOLOGY. 50% DIMENSION REDUCTION.
==> CHANGE NAME OF SAMPLED FUNC TO FUNCZ
HOWEVER, A 50% REDUCTION STILL LEAVES
~ 50 POINTS FOR 4 PERIODS OF FUNC.
MUCH MORE INSTUCTIVE TO HAVE LESS
THAN ~8 SAMPLES PER PERIOD. TRY A 2/3
REDUCTION

> DFT=DFT(:,lives);
>
> figure(2)
> clf
> subplot(3,1,1)
> plot(dt*[0:N-1],temp1,dt*[0:N-1],temp2)

NEED A PLOT OF FUNC AND FUNCZ

> subplot(3,1,2)
> plot(f,fftshift(abs(fft(temp2))))
> subplot(3,1,3)
> plot(f,fftshift(abs(DFT*func(:))))
>
> Here is NDFT, algorithm
>
> freq=(-N/2):(N/2-1);

WHY IS df = 1?
WHAT HAPPENS WHEN N is odd?

>f_hat=a;

WHAt IS a ???

> f=zeros(M,1);
> for k=1:N
> f=f+f_hat(k).*exp(-2*pi*i*x*freq(k));
> end;
> So question is Which one is right for Non uniform sampling

What are you comparing?
The previous examples go from time to frequency
Whereas your NDFT code goes from frequency to time.
????

If the DFT and IDFT are to be approximations to the
continuous time FT and IFT, the nonuniform differentials
dt and df have to be taken into account.

Go back to the code I posted (DFTgh1) to see how the nonuniform
factors dt and df affect the calculation.

In particular, the IDFT formula is not the inverse of
the DFT formula, or vice versa, when either spacing is nonuniform!

>..Is matlab DFT formula (which i have taken from help) is same
> as FFT and can handle only fixed sample...

The MATLAB formula, AS WELL AS YOUR NDFT, are only valid for
uniform sampling.

>what factor in DFT algorithm constraining it for fixed sampling.

The lack of nonconstant dt. See the formula in DFTgh1

> In DFT, algorithm we are multiplying our Coefficient with twiddle
< factor, that twiddle factor is equally spaced ...is that the
constrain...
>
> twiddle factor= exp(-2*pi*i*k*n/N)

Yes. That is a special case for dt and df constant.

The general form is W(k,n) = exp(-2*pi*i*f(k)*t(n))


> ..IN this when we divide it by N, we only mean to normalise it..isnt
> it..also 2pi is my sampling frequency ...

???

> All these doubts are there because of the code which i have written above and i am dubious why its giving same result as fft ..Also what FFT do when it incur a irregular sampling....although it give wrong result but what is its working on such kind of input.

Go back to the continuous time Fourier integral for a
function that is zero outside of [0,T]. Then approximate
the integral with a sum over N nonuniformly spaced samples.
Notice that you cannot ignore the nonconstant differential
dt. If you do it right, you should come up with something
that looks like the formula in DFTgh1.

Hope this helps.

Greg

Greg <heath@alumni.brown.edu> wrote in message <7bdc64ef-1a65-45b9-8f2e-82fd3c4bbfa2@h11g2000yqb.googlegroups.com>...
> On Jul 6, 4:47 pm, "guj " <gulatiaks...@gmail.com> wrote:
> > Greg <he...@alumni.brown.edu> wrote in message <e104f561-edaa-4505-84c2-cf6bcfb49...@s31g2000yqs.googlegroups.com>...
> > > On Jun 28, 12:33 pm, Greg <he...@alumni.brown.edu> wrote:
> > > > On Jun 27, 4:25 pm, "guj " <gulatiaks...@gmail.com> wrote:
> > > -----SNIP
> > > > function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
> >
> > > > % function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
> > > > %
> > > > % Modification of AJ Johnson's dft for nonuniform sampling
> > > > %
> > > > % Computes XFT (Discrete Fourier Transform) at frequencies
> > > > % given in f, given samples x taken at times t:
> > > > %
> > > > % XFT(f) = sum(k=1,N){ dts(k) *x(k) * exp(-2*pi*j*t(k)*f) }
> > > > % = W *(x.*dts)
> > > > %
> > > > % where dts is a symmetrized modification of diff(t).
> > > > %
> > > > % Also computes the Least-Squared-Error Spectrum at
> > > > % frequencies given in f, given samples x taken at
> > > > % times t:
> > > > %
> > > > % XLS(f) = (W'\x)./dfs;
> > > > %
> > > > % where dfs is a symmetrized modification of diff(f).
> > > > %
> > > > % NMSEFT is the normalized mean-square-error of reconstucting
> > > > % x from X using the Inverse Fourier Transform formula. If
> > > > % mean(x) = 0, then the MSE is unnormalized.
> >
> > > Correction:
> >
> > > If mean(x) = x, i.e., x is constant, then the MSE is unnormalized.
> >
> > > > % NMSELS is the normalized mean-square-error of reconstucting
> > > > % x from X using Least Squares. If mean(x) = 0, then the MSE
> > > > % is unnormalized.
> >
> > > Correction:
> >
> > > If mean(x) = x, i.e., x is constant, then the MSE is unnormalized.
> >
> > > > % For comparison with MATLAB'sFFTwhen the spacing is uniform,
> > > > % double the end values x(1) and x(end) and divide X by dt0 =
> > > > % mean(diff(t))
> >
> > > -----SNIP
> >
> > > Hope this helps.
> >
> > > Greg
> >
> > What are your comments on the code below:
> > FFT is giving the same result as DFT for Non uniform sampling.
>
> Both are inappropiarte for nonuniform sampling. See the above
> code where nonconstant dt is taken into account.
>
> > I am curious to know the difference between NDFT and DFT ...Notation
> >
> > clear
> > dt=.01;
> > N=101;
> > func=sin([0:N-1]/4);
>
> BETTER TO USE A COLUMN VECTOR
>
> > f=1/dt/N/2*[-N:2:N-2];
>
> INCORRECT FOR N ODD
>
> > figure(1)
> > clf
> > subplot(3,1,1)
> > plot(dt*[0:N-1],func)
> > subplot(3,1,2)
> > plot(f,fftshift(abs(fft(func))))
>
> DIVIDE BY N TO GET CORRECT SCALE
>
> > k=1:N;
> > n=1:N;
> > DFT=exp(-i*2*pi*((k(:)-1)*(n-1)/N));
>
> POOR TERMINOLOGY CHANGE "DFT" TO "W"
>
> > subplot(3,1,3)
> > plot(f,fftshift(abs(DFT*func(:))))
> >
> > z=round(rand(1,N));
> > temp1=func;
> > temp2=z.*func;
> > lives=find(z~=0);
> > func=temp2(lives);
>
> POOR TERMINOLOGY. 50% DIMENSION REDUCTION.
> ==> CHANGE NAME OF SAMPLED FUNC TO FUNCZ
> HOWEVER, A 50% REDUCTION STILL LEAVES
> ~ 50 POINTS FOR 4 PERIODS OF FUNC.
> MUCH MORE INSTUCTIVE TO HAVE LESS
> THAN ~8 SAMPLES PER PERIOD. TRY A 2/3
> REDUCTION
>
> > DFT=DFT(:,lives);
> >
> > figure(2)
> > clf
> > subplot(3,1,1)
> > plot(dt*[0:N-1],temp1,dt*[0:N-1],temp2)
>
> NEED A PLOT OF FUNC AND FUNCZ
>
> > subplot(3,1,2)
> > plot(f,fftshift(abs(fft(temp2))))
> > subplot(3,1,3)
> > plot(f,fftshift(abs(DFT*func(:))))
> >
> > Here is NDFT, algorithm
> >
> > freq=(-N/2):(N/2-1);
>
> WHY IS df = 1?
> WHAT HAPPENS WHEN N is odd?
>
> >f_hat=a;
>
> WHAt IS a ???
>
> > f=zeros(M,1);
> > for k=1:N
> > f=f+f_hat(k).*exp(-2*pi*i*x*freq(k));
> > end;
> > So question is Which one is right for Non uniform sampling
>
> What are you comparing?
> The previous examples go from time to frequency
> Whereas your NDFT code goes from frequency to time.
> ????
>
> If the DFT and IDFT are to be approximations to the
> continuous time FT and IFT, the nonuniform differentials
> dt and df have to be taken into account.
>
> Go back to the code I posted (DFTgh1) to see how the nonuniform
> factors dt and df affect the calculation.
>
> In particular, the IDFT formula is not the inverse of
> the DFT formula, or vice versa, when either spacing is nonuniform!
>
> >..Is matlab DFT formula (which i have taken from help) is same
> > as FFT and can handle only fixed sample...
>
> The MATLAB formula, AS WELL AS YOUR NDFT, are only valid for
> uniform sampling.
>
> >what factor in DFT algorithm constraining it for fixed sampling.
>
> The lack of nonconstant dt. See the formula in DFTgh1
>
> > In DFT, algorithm we are multiplying our Coefficient with twiddle
> < factor, that twiddle factor is equally spaced ...is that the
> constrain...
> >
> > twiddle factor= exp(-2*pi*i*k*n/N)
>
> Yes. That is a special case for dt and df constant.
>
> The general form is W(k,n) = exp(-2*pi*i*f(k)*t(n))
>
>
> > ..IN this when we divide it by N, we only mean to normalise it..isnt
> > it..also 2pi is my sampling frequency ...
>
> ???
>
> > All these doubts are there because of the code which i have written above and i am dubious why its giving same result as fft ..Also what FFT do when it incur a irregular sampling....although it give wrong result but what is its working on such kind of input.
>
> Go back to the continuous time Fourier integral for a
> function that is zero outside of [0,T]. Then approximate
> the integral with a sum over N nonuniformly spaced samples.
> Notice that you cannot ignore the nonconstant differential
> dt. If you do it right, you should come up with something
> that looks like the formula in DFTgh1.
>
> Hope this helps.
>
> Greg
>



I gone through the derivation of DFT Expression, and found that during derivation it is assumed that our Fourier coffecients are uniformly spaced both in time and frequency domain. Also when we make the samples non uniform, our signal or Fourier coffecients are no longer orthogonal which is the again the second basis for the derivation of DFT Expression. So these arguments are strong enough to prove the DFT Expression is not valid for the non uniform sampling ...Please correct me if i am wrong.

And now, I am working on some thing like DFTgh1

Thanks

Greg <heath@alumni.brown.edu> wrote in message <7bdc64ef-1a65-45b9-8f2e-82fd3c4bbfa2@h11g2000yqb.googlegroups.com>...
> On Jul 6, 4:47 pm, "guj " <gulatiaks...@gmail.com> wrote:
> > Greg <he...@alumni.brown.edu> wrote in message <e104f561-edaa-4505-84c2-cf6bcfb49...@s31g2000yqs.googlegroups.com>...
> > > On Jun 28, 12:33 pm, Greg <he...@alumni.brown.edu> wrote:
> > > > On Jun 27, 4:25 pm, "guj " <gulatiaks...@gmail.com> wrote:
> > > -----SNIP
> > > > function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
> >
> > > > % function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
> > > > %
> > > > % Modification of AJ Johnson's dft for nonuniform sampling
> > > > %
> > > > % Computes XFT (Discrete Fourier Transform) at frequencies
> > > > % given in f, given samples x taken at times t:
> > > > %
> > > > % XFT(f) = sum(k=1,N){ dts(k) *x(k) * exp(-2*pi*j*t(k)*f) }
> > > > % = W *(x.*dts)
> > > > %
> > > > % where dts is a symmetrized modification of diff(t).
> > > > %
> > > > % Also computes the Least-Squared-Error Spectrum at
> > > > % frequencies given in f, given samples x taken at
> > > > % times t:
> > > > %
> > > > % XLS(f) = (W'\x)./dfs;
> > > > %
> > > > % where dfs is a symmetrized modification of diff(f).
> > > > %
> > > > % NMSEFT is the normalized mean-square-error of reconstucting
> > > > % x from X using the Inverse Fourier Transform formula. If
> > > > % mean(x) = 0, then the MSE is unnormalized.
> >
> > > Correction:
> >
> > > If mean(x) = x, i.e., x is constant, then the MSE is unnormalized.
> >
> > > > % NMSELS is the normalized mean-square-error of reconstucting
> > > > % x from X using Least Squares. If mean(x) = 0, then the MSE
> > > > % is unnormalized.
> >
> > > Correction:
> >
> > > If mean(x) = x, i.e., x is constant, then the MSE is unnormalized.
> >
> > > > % For comparison with MATLAB'sFFTwhen the spacing is uniform,
> > > > % double the end values x(1) and x(end) and divide X by dt0 =
> > > > % mean(diff(t))
> >
> > > -----SNIP
> >
> > > Hope this helps.
> >
> > > Greg
> >
> > What are your comments on the code below:
> > FFT is giving the same result as DFT for Non uniform sampling.
>
> Both are inappropiarte for nonuniform sampling. See the above
> code where nonconstant dt is taken into account.
>
> > I am curious to know the difference between NDFT and DFT ...Notation
> >
> > clear
> > dt=.01;
> > N=101;
> > func=sin([0:N-1]/4);
>
> BETTER TO USE A COLUMN VECTOR
>
> > f=1/dt/N/2*[-N:2:N-2];
>
> INCORRECT FOR N ODD
>
> > figure(1)
> > clf
> > subplot(3,1,1)
> > plot(dt*[0:N-1],func)
> > subplot(3,1,2)
> > plot(f,fftshift(abs(fft(func))))
>
> DIVIDE BY N TO GET CORRECT SCALE
>
> > k=1:N;
> > n=1:N;
> > DFT=exp(-i*2*pi*((k(:)-1)*(n-1)/N));
>
> POOR TERMINOLOGY CHANGE "DFT" TO "W"
>
> > subplot(3,1,3)
> > plot(f,fftshift(abs(DFT*func(:))))
> >
> > z=round(rand(1,N));
> > temp1=func;
> > temp2=z.*func;
> > lives=find(z~=0);
> > func=temp2(lives);
>
> POOR TERMINOLOGY. 50% DIMENSION REDUCTION.
> ==> CHANGE NAME OF SAMPLED FUNC TO FUNCZ
> HOWEVER, A 50% REDUCTION STILL LEAVES
> ~ 50 POINTS FOR 4 PERIODS OF FUNC.
> MUCH MORE INSTUCTIVE TO HAVE LESS
> THAN ~8 SAMPLES PER PERIOD. TRY A 2/3
> REDUCTION
>
> > DFT=DFT(:,lives);
> >
> > figure(2)
> > clf
> > subplot(3,1,1)
> > plot(dt*[0:N-1],temp1,dt*[0:N-1],temp2)
>
> NEED A PLOT OF FUNC AND FUNCZ
>
> > subplot(3,1,2)
> > plot(f,fftshift(abs(fft(temp2))))
> > subplot(3,1,3)
> > plot(f,fftshift(abs(DFT*func(:))))
> >
> > Here is NDFT, algorithm
> >
> > freq=(-N/2):(N/2-1);
>
> WHY IS df = 1?
> WHAT HAPPENS WHEN N is odd?
>
> >f_hat=a;
>
> WHAt IS a ???
>
> > f=zeros(M,1);
> > for k=1:N
> > f=f+f_hat(k).*exp(-2*pi*i*x*freq(k));
> > end;
> > So question is Which one is right for Non uniform sampling
>
> What are you comparing?
> The previous examples go from time to frequency
> Whereas your NDFT code goes from frequency to time.
> ????
>
> If the DFT and IDFT are to be approximations to the
> continuous time FT and IFT, the nonuniform differentials
> dt and df have to be taken into account.
>
> Go back to the code I posted (DFTgh1) to see how the nonuniform
> factors dt and df affect the calculation.
>
> In particular, the IDFT formula is not the inverse of
> the DFT formula, or vice versa, when either spacing is nonuniform!
>
> >..Is matlab DFT formula (which i have taken from help) is same
> > as FFT and can handle only fixed sample...
>
> The MATLAB formula, AS WELL AS YOUR NDFT, are only valid for
> uniform sampling.
>
> >what factor in DFT algorithm constraining it for fixed sampling.
>
> The lack of nonconstant dt. See the formula in DFTgh1
>
> > In DFT, algorithm we are multiplying our Coefficient with twiddle
> < factor, that twiddle factor is equally spaced ...is that the
> constrain...
> >
> > twiddle factor= exp(-2*pi*i*k*n/N)
>
> Yes. That is a special case for dt and df constant.
>
> The general form is W(k,n) = exp(-2*pi*i*f(k)*t(n))
>
>
> > ..IN this when we divide it by N, we only mean to normalise it..isnt
> > it..also 2pi is my sampling frequency ...
>
> ???
>
> > All these doubts are there because of the code which i have written above and i am dubious why its giving same result as fft ..Also what FFT do when it incur a irregular sampling....although it give wrong result but what is its working on such kind of input.
>
> Go back to the continuous time Fourier integral for a
> function that is zero outside of [0,T]. Then approximate
> the integral with a sum over N nonuniformly spaced samples.
> Notice that you cannot ignore the nonconstant differential
> dt. If you do it right, you should come up with something
> that looks like the formula in DFTgh1.
>
> Hope this helps.
>
> Greg
>




TRIVIAL Doubt :)

There are quite few number of algorithms which deals with application of FFT on irregular sample data points .........



So Mathematician start these with a complex sequence u_p p=-N:N and a set of arbitary points x_j j=0...2N-1, a straight forward exact evaluation of the sum

u(x) = sum{p=-N:N} u_p e ^(i p x) for x=x0,x1,......x2N-1

So we are basically evaluating polynomial at set of points which are not fixed (i;e x)......and we can invert it later to get it back. (They dont assume space domain or frequency domain)

My question is when we talk in term of Engineering language, here x is the time domain for me and p is frequency domain. Whole point is!

if i apply above on my signal which is sampled irregularly in time domain, i will get the spectra in frequency domain on inverting it back i will be back in time domain (Am i right)

if i am right then i dont understand why we take summation over time when we want to go from time domain to frequency domain, like from going to time domain to frequency domain my summation should be from x=o to 2N-1........

I really didnt get mathmatician ways, rnt they r going from equispaced points to non equispaced points...WELL some body plz clear my doubts ...

"guj " <gulatiakshay@gmail.com> wrote in message <h3iasa$g6v$1@fred.mathworks.com>...
> Greg <heath@alumni.brown.edu> wrote in message <7bdc64ef-1a65-45b9-8f2e-82fd3c4bbfa2@h11g2000yqb.googlegroups.com>...
> > On Jul 6, 4:47 pm, "guj " <gulatiaks...@gmail.com> wrote:
> > > Greg <he...@alumni.brown.edu> wrote in message <e104f561-edaa-4505-84c2-cf6bcfb49...@s31g2000yqs.googlegroups.com>...
> > > > On Jun 28, 12:33 pm, Greg <he...@alumni.brown.edu> wrote:
> > > > > On Jun 27, 4:25 pm, "guj " <gulatiaks...@gmail.com> wrote:
> > > > -----SNIP
> > > > > function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
> > >
> > > > > % function [XFT,XLS,NMSEFT,NMSELS] = DFTgh1(x,t,f)
> > > > > %
> > > > > % Modification of AJ Johnson's dft for nonuniform sampling
> > > > > %
> > > > > % Computes XFT (Discrete Fourier Transform) at frequencies
> > > > > % given in f, given samples x taken at times t:
> > > > > %
> > > > > % XFT(f) = sum(k=1,N){ dts(k) *x(k) * exp(-2*pi*j*t(k)*f) }
> > > > > % = W *(x.*dts)
> > > > > %
> > > > > % where dts is a symmetrized modification of diff(t).
> > > > > %
> > > > > % Also computes the Least-Squared-Error Spectrum at
> > > > > % frequencies given in f, given samples x taken at
> > > > > % times t:
> > > > > %
> > > > > % XLS(f) = (W'\x)./dfs;
> > > > > %
> > > > > % where dfs is a symmetrized modification of diff(f).
> > > > > %
> > > > > % NMSEFT is the normalized mean-square-error of reconstucting
> > > > > % x from X using the Inverse Fourier Transform formula. If
> > > > > % mean(x) = 0, then the MSE is unnormalized.
> > >
> > > > Correction:
> > >
> > > > If mean(x) = x, i.e., x is constant, then the MSE is unnormalized.
> > >
> > > > > % NMSELS is the normalized mean-square-error of reconstucting
> > > > > % x from X using Least Squares. If mean(x) = 0, then the MSE
> > > > > % is unnormalized.
> > >
> > > > Correction:
> > >
> > > > If mean(x) = x, i.e., x is constant, then the MSE is unnormalized.
> > >
> > > > > % For comparison with MATLAB'sFFTwhen the spacing is uniform,
> > > > > % double the end values x(1) and x(end) and divide X by dt0 =
> > > > > % mean(diff(t))
> > >
> > > > -----SNIP
> > >
> > > > Hope this helps.
> > >
> > > > Greg
> > >
> > > What are your comments on the code below:
> > > FFT is giving the same result as DFT for Non uniform sampling.
> >
> > Both are inappropiarte for nonuniform sampling. See the above
> > code where nonconstant dt is taken into account.
> >
> > > I am curious to know the difference between NDFT and DFT ...Notation
> > >
> > > clear
> > > dt=.01;
> > > N=101;
> > > func=sin([0:N-1]/4);
> >
> > BETTER TO USE A COLUMN VECTOR
> >
> > > f=1/dt/N/2*[-N:2:N-2];
> >
> > INCORRECT FOR N ODD
> >
> > > figure(1)
> > > clf
> > > subplot(3,1,1)
> > > plot(dt*[0:N-1],func)
> > > subplot(3,1,2)
> > > plot(f,fftshift(abs(fft(func))))
> >
> > DIVIDE BY N TO GET CORRECT SCALE
> >
> > > k=1:N;
> > > n=1:N;
> > > DFT=exp(-i*2*pi*((k(:)-1)*(n-1)/N));
> >
> > POOR TERMINOLOGY CHANGE "DFT" TO "W"
> >
> > > subplot(3,1,3)
> > > plot(f,fftshift(abs(DFT*func(:))))
> > >
> > > z=round(rand(1,N));
> > > temp1=func;
> > > temp2=z.*func;
> > > lives=find(z~=0);
> > > func=temp2(lives);
> >
> > POOR TERMINOLOGY. 50% DIMENSION REDUCTION.
> > ==> CHANGE NAME OF SAMPLED FUNC TO FUNCZ
> > HOWEVER, A 50% REDUCTION STILL LEAVES
> > ~ 50 POINTS FOR 4 PERIODS OF FUNC.
> > MUCH MORE INSTUCTIVE TO HAVE LESS
> > THAN ~8 SAMPLES PER PERIOD. TRY A 2/3
> > REDUCTION
> >
> > > DFT=DFT(:,lives);
> > >
> > > figure(2)
> > > clf
> > > subplot(3,1,1)
> > > plot(dt*[0:N-1],temp1,dt*[0:N-1],temp2)
> >
> > NEED A PLOT OF FUNC AND FUNCZ
> >
> > > subplot(3,1,2)
> > > plot(f,fftshift(abs(fft(temp2))))
> > > subplot(3,1,3)
> > > plot(f,fftshift(abs(DFT*func(:))))
> > >
> > > Here is NDFT, algorithm
> > >
> > > freq=(-N/2):(N/2-1);
> >
> > WHY IS df = 1?
> > WHAT HAPPENS WHEN N is odd?
> >
> > >f_hat=a;
> >
> > WHAt IS a ???
> >
> > > f=zeros(M,1);
> > > for k=1:N
> > > f=f+f_hat(k).*exp(-2*pi*i*x*freq(k));
> > > end;
> > > So question is Which one is right for Non uniform sampling
> >
> > What are you comparing?
> > The previous examples go from time to frequency
> > Whereas your NDFT code goes from frequency to time.
> > ????
> >
> > If the DFT and IDFT are to be approximations to the
> > continuous time FT and IFT, the nonuniform differentials
> > dt and df have to be taken into account.
> >
> > Go back to the code I posted (DFTgh1) to see how the nonuniform
> > factors dt and df affect the calculation.
> >
> > In particular, the IDFT formula is not the inverse of
> > the DFT formula, or vice versa, when either spacing is nonuniform!
> >
> > >..Is matlab DFT formula (which i have taken from help) is same
> > > as FFT and can handle only fixed sample...
> >
> > The MATLAB formula, AS WELL AS YOUR NDFT, are only valid for
> > uniform sampling.
> >
> > >what factor in DFT algorithm constraining it for fixed sampling.
> >
> > The lack of nonconstant dt. See the formula in DFTgh1
> >
> > > In DFT, algorithm we are multiplying our Coefficient with twiddle
> > < factor, that twiddle factor is equally spaced ...is that the
> > constrain...
> > >
> > > twiddle factor= exp(-2*pi*i*k*n/N)
> >
> > Yes. That is a special case for dt and df constant.
> >
> > The general form is W(k,n) = exp(-2*pi*i*f(k)*t(n))
> >
> >
> > > ..IN this when we divide it by N, we only mean to normalise it..isnt
> > > it..also 2pi is my sampling frequency ...
> >
> > ???
> >
> > > All these doubts are there because of the code which i have written above and i am dubious why its giving same result as fft ..Also what FFT do when it incur a irregular sampling....although it give wrong result but what is its working on such kind of input.
> >
> > Go back to the continuous time Fourier integral for a
> > function that is zero outside of [0,T]. Then approximate
> > the integral with a sum over N nonuniformly spaced samples.
> > Notice that you cannot ignore the nonconstant differential
> > dt. If you do it right, you should come up with something
> > that looks like the formula in DFTgh1.
> >
> > Hope this helps.
> >
> > Greg
> >
>
>
>
>
> TRIVIAL Doubt :)
>
> There are quite few number of algorithms which deals with application of FFT on irregular sample data points .........
>
>
>
> So Mathematician start these with a complex sequence u_p p=-N:N and a set of arbitary points x_j j=0...2N-1, a straight forward exact evaluation of the sum
>
> u(x) = sum{p=-N:N} u_p e ^(i p x) for x=x0,x1,......x2N-1
>
> So we are basically evaluating polynomial at set of points which are not fixed (i;e x)......and we can invert it later to get it back. (They dont assume space domain or frequency domain)
>
> My question is when we talk in term of Engineering language, here x is the time domain for me and p is frequency domain. Whole point is!
>
> if i apply above on my signal which is sampled irregularly in time domain, i will get the spectra in frequency domain on inverting it back i will be back in time domain (Am i right)
>
> if i am right then i dont understand why we take summation over time when we want to go from time domain to frequency domain, like from going to time domain to frequency domain my summation should be from x=o to 2N-1........
>
> I really didnt get mathmatician ways, rnt they r going from equispaced points to non equispaced points...WELL some body plz clear my doubts ...

Correction when x_j is equispaced its equal to x_j=j*pi/N