Path: news.mathworks.com!newsfeed-00.mathworks.com!newsfeed2.dallas1.level3.net!news.level3.com!postnews.google.com!t13g2000yqt.googlegroups.com!not-for-mail
From: Greg <heath@alumni.brown.edu>
Newsgroups: comp.soft-sys.matlab
Subject: Re: FFT,IFFT, and NDFT,NFFT
Date: Sat, 4 Jul 2009 04:17:55 -0700 (PDT)
Organization: http://groups.google.com
Lines: 147
Message-ID: <1d7bf892-a5eb-4cc5-b418-a93f7735339b@t13g2000yqt.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: 69.141.163.135
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Trace: posting.google.com 1246706275 8990 127.0.0.1 (4 Jul 2009 11:17:55 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sat, 4 Jul 2009 11:17:55 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: t13g2000yqt.googlegroups.com; posting-host=69.141.163.135; 
	posting-account=mUealwkAAACvQrLWvunjg50tRAnsNtJR
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; .NET CLR 
	2.0.50727),gzip(gfe),gzip(gfe)
Xref: news.mathworks.com comp.soft-sys.matlab:552763


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