An update algorithm for Fourier coefficients

In this article we present a new technique to obtain the Discrete Fourier coefficients for a moving data window of an arbitrary length. Unlike the classic approaches we derive an update algorithm by exploiting results of update formulas for orthogonal polynomials. For the vector space of polynomials we define a discrete inner product by evaluating the functions on the complex unit circle at equidistant points. With certain weights for the inner product the coefficients of the best approximating polynomial with respect to this inner product are the wanted Fourier coefficients. Therefore we can apply updating strategies for orthogonal polynomials to obtain Fourier coefficients. By this approach we obtain a constant number of arithmetic operations for every single Fourier coefficient. Moreover the algorithm is numerically stable, fast, and flexible since it can be applied to obtain the Discrete Fourier Transformation for data windows with a length not equal to powers of two.