On numerical methods for discrete least-squares approximation by trigonometric polynomials

Fast, efficient and reliable algorithms for discrete least-squares approximation of a real-valued function given at arbitrary distinct nodes in $[0,2\pi )$ by trigonometric polynomials are presented. The algorithms are based on schemes for the solution of inverse unitary eigenproblems and require only $\mathrm{O}(mn)$ arithmetic operations as compared to $\mathrm{O}(mn^2)$ operations needed for algorithms that ignore the structure of the problem. An algorithm which solves this problem with real-valued data and real-valued solution using only real arithmetic is given. Numerical examples are presented that show that the proposed algorithms produce consistently accurate results that are often better than those obtained by general QR decomposition methods for the least-squares problem.