**ABSTRACT**
### A Levinson-Galerkin algorithm for trigonometric approximation

#### Thomas Strohmer

Trigonometric polynomials are widely used for the approximation of a smooth
function from a set of nonuniformly spaced samples. If the samples are
perturbed by noise, a good choice for the polynomial degree of the
trigonometric approximation becomes an essential issue to avoid overfitting
and underfitting of the data. Standard methods for trigonometric least
squares approximation assume that the degree for the approximating
polynomial is known a priori, which is usually not the case in practice.
We derive a multi-level algorithm that recursively adapts to the
least squares solution of suitable degree. We analyze under which
conditions this multi-approach yields the optimal solution. The proposed
algorithm computes the solution in at most $\ord(rM + M^2)$ operations ($M$
being the polynomial degree of the approximation and $r$ being the number
of samples) by solving
a family of nested Toeplitz systems. It is shown how the presented method
can be extended to multivariate trigonometric approximation. We demonstrate
the performance of the algorithm by applying it in echocardiography to
the recovery of the boundary of the Left Ventricle of the heart.

Download the paper as a GNU-ziped postscript file (291780 byte).