Path: news.mathworks.com!newsfeed-00.mathworks.com!newsfeed2.dallas1.level3.net!news.level3.com!postnews.google.com!b15g2000yqd.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 12:54:54 -0700 (PDT)
Organization: http://groups.google.com
Lines: 172
Message-ID: <18eda20f-8ea3-48e7-8bb8-64099e34ccf2@b15g2000yqd.googlegroups.com>
References: <h25v6u$5ia$1@fred.mathworks.com> <6ced5282-e4f9-4712-9546-158d71c222b0@j14g2000vbp.googlegroups.com> 
	<h2ap6d$dp7$1@fred.mathworks.com> <1d7bf892-a5eb-4cc5-b418-a93f7735339b@t13g2000yqt.googlegroups.com>
NNTP-Posting-Host: 69.141.163.135
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1246737297 923 127.0.0.1 (4 Jul 2009 19:54:57 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sat, 4 Jul 2009 19:54:57 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: b15g2000yqd.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:552806


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