Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: FFT,IFFT, and NDFT,NFFT
Date: Mon, 29 Jun 2009 19:05:02 +0000 (UTC)
Organization: Uofc
Lines: 158
Message-ID: <h2b38u$8pm$1@fred.mathworks.com>
References: <h25v6u$5ia$1@fred.mathworks.com> <6ced5282-e4f9-4712-9546-158d71c222b0@j14g2000vbp.googlegroups.com> <66f78a0c-7e01-41c9-b57e-4f7a967bc853@f10g2000vbf.googlegroups.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1246302302 9014 172.30.248.38 (29 Jun 2009 19:05:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Mon, 29 Jun 2009 19:05:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1662491
Xref: news.mathworks.com comp.soft-sys.matlab:551506


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.