A Levinson-Galerkin algorithm for regularized trigonometric approximation

DOI10.1137/S1064827597329254MaRDI QIDQ2706432zbMATH OpenOpenAlexFDO

Authors Thomas Strohmer

Publication date 19 March 2001

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9901123

zbMATH Keywords

algorithmfittingGalerkin algorithmLevinson algorithmmultilevel methodperformanceregularizationToeplitz matrixtrigonometric least squares approximation

Mathematics Subject Classification ID

Trigonometric approximation (42A10) Numerical smoothing, curve fitting (65D10) Iterative numerical methods for linear systems (65F10) Numerical methods for trigonometric approximation and interpolation (65T40)

Abstract: Trigonometric polynomials are widely used for the approximation of a smooth function $f$ from a set of nonuniformly spaced samples ${f(x_j)}_{j=0}^{N-1}$. If the samples are perturbed by noise, controlling the smoothness of the trigonometric approximation becomes an essential issue to avoid overfitting and underfitting of the data. Using the polynomial degree as regularization parameter we derive a multi-level algorithm that iteratively adapts to the least squares solution of optimal smoothness. The proposed algorithm computes the solution in at most $calO(NM+M^2)$ operations ($M$ being the polynomial degree of the approximation) 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.

Review text

This paper presents a study of the trigonometric least squares approximation of a smooth function from a set of nonuniformly spaced samples. The author derives an efficient algorithm that computes the trigonometric approximations that provides the optimal between fitting the given data and preserving smoothness of the solution. Here optimality is meant in the sense that the solution has minimal degree among all trigonometric polynomials that satisfy a certain least squares criterion. The algorithm recursively adapts to the least squares approximation of optimal degree by solving a family of nested Toeplitz systems in at most \(\mathcal O(Mr+M^2)\) operations (\( M\) being the polynomial degree of the approximation and \(r\) being the number of samples). It is shown how the presented method can be extended to multivariate trigonometric approximation. The author demonstrates the performance of the algorithm by applying it in echocardiography to the recovery of the boundary of the left ventricle of the heart.

Recommendations

• scientific article; zbMATH DE number 741186
• On numerical methods for discrete least-squares approximation by trigonometric polynomials
• Galerkin method with trigonometric basis on stable numerical differentiation
• Discrete Least Squares Approximation by Trigonometric Polynomials
• Galerkin-Levin method for highly oscillatory integrals
• Levenberg-Marquardt methods and trust region methods for nonlinear equations
• A Levenberg-Marquardt method with approximate projections
• Discrete least squares approximation of piecewise-linear functions by trigonometric polynomials
• A modified Levenberg-Marquardt method with trust-region techniques
• On an improved-Levin oscillatory quadrature method

Cited in

(5)

• Density theorems for nonuniform sampling of bandlimited functions using derivatives or bunched measurements
• Fast scattered data approximation with Neumann and other boundary conditions
• Data-driven algorithms for signal processing with trigonometric rational functions
• Lasso trigonometric polynomial approximation for periodic function recovery in equidistant points
• Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma

This page was built for publication: A Levinson-Galerkin algorithm for regularized trigonometric approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2706432)