A Levinson-Galerkin algorithm for regularized trigonometric approximation

Trigonometric polynomials are widely used for the approximation of a smooth function from a set of nonuniformly spaced samples. If the samples are per turbed by noise, a good choice for the polynomial degree of the trigonometr ic approximation becomes an essential issue to avoid overfitting and underf itting of the data. Standard methods for trigonometric least squares approx imation assume that the degree for the approximating polynomial is known a priori, which is usually not the case in practice. We derive a multilevel a lgorithm that recursively adapts to the least squares solution of suitable degree. We analyze under which conditions this multilevel approach yields t he optimal solution. The proposed algorithm computes the solution in at mos t O (rM + M-2) operations (M being the polynomial degree of the approximati on and r being the umber of samples) by solving a family of nested Toeplitz systems. It is shown how the presented method can be extended to multivari ate trigonometric approximation. We demonstrate the performance of the algo rithm by applying it in echocardiography to the recovery of the boundary of the left ventricle of the heart.