Path: news.mathworks.com!newsfeed-00.mathworks.com!newsfeed2.dallas1.level3.net!news.level3.com!postnews.google.com!f10g2000vbf.googlegroups.com!not-for-mail
From: dbd <dbd@ieee.org>
Newsgroups: comp.soft-sys.matlab
Subject: Re: FFT,IFFT, and NDFT,NFFT
Date: Mon, 29 Jun 2009 10:59:15 -0700 (PDT)
Organization: http://groups.google.com
Lines: 143
Message-ID: <66f78a0c-7e01-41c9-b57e-4f7a967bc853@f10g2000vbf.googlegroups.com>
References: <h25v6u$5ia$1@fred.mathworks.com> <6ced5282-e4f9-4712-9546-158d71c222b0@j14g2000vbp.googlegroups.com> 
	<h2ap6d$dp7$1@fred.mathworks.com>
NNTP-Posting-Host: 75.3.203.41
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Trace: posting.google.com 1246298355 19858 127.0.0.1 (29 Jun 2009 17:59:15 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Mon, 29 Jun 2009 17:59:15 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: f10g2000vbf.googlegroups.com; posting-host=75.3.203.41; 
	posting-account=E_gaFgoAAACfAhF2MzvkivNAUVGQbrBP
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.1.20) 
	Gecko/20081217 Firefox/2.0.0.20 (.NET CLR 3.5.30729),gzip(gfe),gzip(gfe)
Xref: news.mathworks.com comp.soft-sys.matlab:551491


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