EDFT (Extended Discrete Fourier Transform) algorithm produces Npoint 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 zeropadded, 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 applied EDFT to N>length(X), get the results:
F=edft(X,N)=edft(Y)=fft(Y), where Y=ifft(F) and the length(Y)=N.
Y is X plus nonzero forward and backward extrapolation of X to length N and/or interpolation if unknown data inside of X have been replaced by NaN (NotaNumber).
2. EDFT can increase frequency resolution up to 1/(N*T), where T is sampling period. It is well known, that zeropadding 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 remains 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 a limit to the maximum number of iterations (input argument I) or either in noniterative (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 the form of the input sequence amplitude spectrum S can be used to setup appropriate weight vector W, otherwise the 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 the performed iterations, the second row indicates breaking of iteration reason (see EDFT help).
6. Is it possible to estimate DFT of nonuniformly (irregularly) sampled input sequence by the proposed algorithm? Yes, it is. As a 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. Twodimensional 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 a suggested algorithm. Run program edft_fig.m to recreate computer simulation results presented in the pdf file.
1.45.0.0  Code update for nedft.m and edft.m functions. 

1.44.0.0  The default matrix inversion method changed in edft.m 

1.43.0.0  Documetation related update 

1.42.0.0  A small corrections made in demoedft output. 

1.41.0.0  ) 

1.40.0.0  Mirror changes 

1.39.0.0  Demo files updated 

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

1.37.0.0  Minor changes  just a code refactoring. 

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

1.9.0.0  Added the link to external document 

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

1.6.0.0  mirror changes 

1.5.0.0  Update contacts info and pdf file. 

1.4.0.0  Programs edft_f2.m and edft_f3.m added 

1.3.0.0  Small changes in stopping iterations criteria 

1.2.0.0  minor changes 

1.1.0.0  Update ExtendedDFT.pdf file 

1.0.0.0  Documentation update 

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

Twodimensional EDFT program edft2.m added. Code updated. 

Replacing corrupted image in pdf file. 

mirror changes 

A special case processing improved, contact info updated. 

Clear unnecessary line in nedft.m 

Small corrections in algorithm description. 

update was unsuccessful  repeating 

Mirror corrections for pdf file 

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

Correct spelling errors 

Mirror modifications in desciption 

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

Added EDFT_Reference_Article.pdf file 

Minor modifications 

EDFT.m modified. Now input data may contain NaN indicating lost data or missing samples.


Relative threshold added to EDFT iterations Stopping criteria 

Changing plots colour in demoedft.m 

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

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

Correct spelling errors 

A smal bug fix to improve metrix and Demo plottings. 

Additional 'division by zero' controls added to Mfile. 
Create scripts with code, output, and formatted text in a single executable document.
Al Sm (view profile)
VeryVery usefull contribution for solving HUDGE problems of "chromaticnoise" compensation in XPS spectroscopy.
Thank you.
Aleksei.
Hooman (view profile)
junjie wang (view profile)
Very useful and full working code! Thanks a lot!
Alfonso (view profile)
It did the job perfectly
Vilnis Liepins (view profile)
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.
Sean (view profile)
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
Jon Griffiths (view profile)
marcello (view profile)
Very useful and full working code ! Great support from the author !
Thanks.
Vilnis Liepins (view profile)
Hi,
See this math as an example: http://www.cfsystems.com/Docs/CFS245IntegralLeastSquares.pdf
Bryan (view profile)
Very interesting and useful code. Well written, documented well and it worked the first time.
Thank you for the improvement!
Changes
20070314 Correct spelling errors
20070221 Mirror modifications in desciption
20070124 Programs for nonuniformly sampled sequence spectral analysis added: nedft.m, inedft.m, demonedft.m, description and code updated.
20060903 Added EDFT_Reference_Article.pdf file
where is the 'EDFT_Reference_Article.pdf '?
Now EDFT works well. Thanks!!!
DEMOEDTF still does not show any changes of every subplots during iteration process!!! Every subplots shows no differences between each iteration step.
DEMO does not show any changes during interation process!!!