Code covered by the BSD License  

Highlights from
Extended DFT

4.83333

4.8 | 8 ratings Rate this file 64 Downloads (last 30 days) File Size: 23.2 KB File ID: #11020
image thumbnail

Extended DFT

by

 

08 May 2006 (Updated )

Program EDFT produce high-resolution N-point DFT for N greater than the length of data vector.

| Watch this File

File Information
Description

EDFT (Extended Discrete Fourier Transform) algorithm produces N-point DFT of sequence X where N is greater than the length of input data. Unlike the Fast Fourier Transform (FFT), where unknown readings outside of X are zero-padded, the EDFT algorithm for calculation of the DFT using only available data and the extended frequency set (therefore, named 'Extended DFT'). EDFT function application is simple and similar to the FFT, besides EDFT have the following additional features:
1. EDFT can extrapolate input sequence X to length N. That is, if apply EDFT for N>length(X), get the results:
F=edft(X,N)=edft(Y)=fft(Y); Y=ifft(F),
where Y is X plus non-zero forward and backward extrapolation of X to length N and/or interpolation if unknown data inside of X have been replaced by NaN (Not-a-Number).
2. EDFT can increase frequency resolution up to 1/(N*T), where T is sampling period. It is well known, that zero-padding do not increase frequency resolution of DFT, therefore the resolution of FFT algorithm is limited by the length of sequence length(X)*T. Of course, there is no magic, just FFT resolution is equal on all N frequencies, while EDFT is able to increase the resolution on some frequencies and decrease on others. The sum of resolutions along the frequency axis for both algorithms remain equal to N*length(X)*T.
3. EDFT can estimate amplitudes and phases of sinusoidal components in sequence X. Like as FFT output fft(X,N)/length(X) is proportional to amplitudes of sinusoids in X, also adding a second output argument for EDFT return the amplitude spectrum S of sequence X:
[F,S]=edft(X,N).
4. Input sequence of EDFT may contain NaN. The proposed algorithm can interpolate and reconstruct of missing readings or even data segments (gaps) inside of sequence X. You just need to replace unknown readings by NaN and run edft(X) or edft(X,N).
5. EDFT can run with limit to maximum number of iterations (input argument I) or either in non-iterative (I=1) mode
[F,S]=edft(X,N,I) or
[F,S,Stopit]=edft(X,N,I,W),
where W is weight vector and consisting of specific weights for each frequency in F. W is proportional to the amplitude spectrum of the signal. So, a`priori knowledge about form of the input sequence amplitude spectrum S can be used to setup appropriate weight vector W, otherwise default (equal) weight W=ones(size(F)) will be applied for the first iteration.
'Stopit' is an informative (optional) output parameter. The first row of 'Stopit' showing the number of performed iteration, the second row indicate breaking of iteration reason (see EDFT help).
6. Is it possible to estimate DFT of nonuniformly (irregularly) sampled input sequence by proposed algorithm? Yes, it is. As result, the Nonuniform EDFT (NEDFT) program introduced for processing of input sequence X sampled at arbitrary time moments tk. NEDFT call line:
[F,S]=nedft(X,tk,fn) will perform DFT of sequence X(tk) and return outputs F(fn) and S(fn).
If frequencies fn are on different grid then used by FFT and EDFT algorithms, a simple Inverse NEDFT (INEDFT) program should be applied to reconstruct Y(tn), call line:
Y=inedft(F,fn,tn).
7. Two-dimensional EDFT of array X can be calculated by applying function edft2.m, call line
F=edft2(x,mrows,ncols).
See programs edft.m, nedft.m, inedft.m and edft2.m help for detailed info.
Launch also DEMO programs. Demoedft.m and Demonedft.m allows to verify the proposed algorithm's performance over iterations for the simulated test signal.
Download pdf file on site http://arxiv.org/abs/1303.2033 to get more comprehensive insight into suggested algorithm. Run program edft_fig.m to recreate computer simulation results presented in the pdf file.

MATLAB release MATLAB 5.2 (R10)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (14)
01 Jul 2014 Alfonso

It did the job perfectly

11 Feb 2014 Vilnis Liepins

Good question. Like as FFT<>IFFT, also EDFT<>IFFT is a pair of DFTs adequately connecting two domains. Unlike FFT, the EDFT adapts to the frequency domain (see details on site http://arxiv.org/abs/1303.2033) and this leads to data extrapolation. Thus, "Super Resolution" is dictated by the known laws physics, from where the longer data, the higher the resolution. Thanks.

03 Feb 2014 Royi Avital

Hello,
This is great a great technique.
I'd be happy if you explain more clearly the intuition behind the "Super Resolution" in it.

Thank You.

15 Jan 2013 Sean

in the function nedft.m I am getting an error:

Undefined function 'finite' for input arguments of type 'double'.

Error in NEDFT (line 119)
if sum(~all(finite(X)))|sum(~all(finite(tk)))|sum(~all(finite(fn))),

Documentation (2012a) says:

Function finite Being Removed

The finite function is obsolete. Use of the finite function now causes an error in MATLAB.

Compatibility Considerations

Replace all instances of finite with isfinite

22 May 2012 Jon Griffiths  
16 May 2012 marcello

Very useful and full working code ! Great support from the author !
Thanks.

01 Feb 2012 Vilnis Liepins

Hi,
See this math as an example: http://www.c-f-systems.com/Docs/CFS-245IntegralLeastSquares.pdf

29 Jan 2012 Royi Avital

Hello,
Could you please refer as to the math background?

Thanks.

15 Dec 2009 Bryan

Very interesting and useful code. Well written, documented well and it worked the first time.

28 Jun 2007 zqm zqm

Thank you for the improvement!

06 Apr 2007 zqm zqm

Changes



2007-03-14 Correct spelling errors
2007-02-21 Mirror modifications in desciption
2007-01-24 Programs for nonuniformly sampled sequence spectral analysis added: nedft.m, inedft.m, demonedft.m, description and code updated.
2006-09-03 Added EDFT_Reference_Article.pdf file

where is the 'EDFT_Reference_Article.pdf '?

20 May 2006 Michal Kvasnicka

Now EDFT works well. Thanks!!!

16 May 2006 Michal Kvasnicka

DEMOEDTF still does not show any changes of every subplots during iteration process!!! Every subplots shows no differences between each iteration step.

11 May 2006 Michal Kvasnicka

DEMO does not show any changes during interation process!!!

Updates
09 May 2006

Additional 'division by zero' controls added to M-file.

10 May 2006

A smal bug fix to improve metrix and Demo plottings.

11 May 2006

Correct spelling errors

15 May 2006

Separate demoedft.m file created to demonstrate Extended DFT performance.

17 May 2006

Update demoedft.m file. Hopefully by now subplots are showing changes during iteration process for all Matlab versions.

18 May 2006

Changing plots colour in demoedft.m

25 May 2006

Relative threshold added to EDFT iterations Stopping criteria

09 Jun 2006

EDFT.m modified. Now input data may contain NaN indicating lost data or missing samples.
DEMOEDFT.m changed - demo where half of data replaced with NaN added.

09 Jun 2006

Minor modifications

05 Sep 2006

Added EDFT_Reference_Article.pdf file

24 Jan 2007

Programs for nonuniformly sampled sequence spectral analysis added: nedft.m, inedft.m, demonedft.m, description and code updated.

21 Feb 2007

Mirror modifications in desciption

14 Mar 2007

Correct spelling errors

08 May 2007

Improve performance of nedft.m and edft.m programs. Add missing pdf file.

09 May 2007

Mirror corrections for pdf file

09 May 2007

update was unsuccessful - repeating

24 May 2007

Small corrections in algorithm description.

24 May 2007

Clear unnecessary line in nedft.m

11 Jun 2007

A special case processing improved, contact info updated.

11 Jun 2007

mirror changes

13 Jun 2007

Replacing corrupted image in pdf file.

28 Jun 2007

Two-dimensional EDFT program edft2.m added. Code updated.

01 Mar 2008

Update of edft.m file, allowing to use all NaNs column&row in edft2.m input matrix.

05 Nov 2009

Update ExtendedDFT.pdf file

29 May 2010

minor changes

22 Oct 2010

Small changes in stopping iterations criteria

03 Feb 2011

Programs edft_f2.m and edft_f3.m added

23 Jan 2012

Update contacts info and pdf file.

25 Jan 2012

mirror changes

28 Feb 2013

Obsolete finite function romoved from code (thanks Sean for your comment). Documentation updated.

02 May 2013

Added the link to external document

16 Oct 2013

EDFT package updated. Pdf file removed as a latest version of it will be available on arxiv site.

13 Feb 2014

Minor changes - just a code refactoring.

02 Apr 2014

Bug in edft.m line 135 corrected. Thanks David M.-S. for your quick response.

12 Sep 2014

Demo files updated

17 Sep 2014

Mirror changes

17 Sep 2014

)

23 Sep 2014

A small corrections made in demoedft output.

Contact us