Fitting parametric curves and surfaces by \(l_\infty\) distance regression. (English) Zbl 1086.65004
Consider the problem of fitting the parameters of a parametric curve or surface to a given set of data. Whereas this problem is commonly considered with respect to a least squares norm, it is appropriate in certain applications to use a supremum norm. This leads to the \(l_\infty\) distance regression problem that can be formalized as
\[
\min_{a,t_1, \ldots,t_m} \max_{1\leq i\leq m} \| x_i - x(a, t_i)\| _\infty.
\]
The authors present and analyze numerical methods for the solution of this problem based on Gauss-Newton techniques. In particular they discuss how to handle the difficulties that are introduced by the fact that the exact solution is, in general, not unique.
Reviewer: Kai Diethelm (Braunschweig)
MSC:
| 65D10 | Numerical smoothing, curve fitting |
| 65K05 | Numerical mathematical programming methods |
| 65D17 | Computer-aided design (modeling of curves and surfaces) |
| 90C30 | Nonlinear programming |
References:
| [1] | A. Atieg and G. A. Watson, A class of methods for fitting a curve or surface to data by minimizing the sum of squares of orthogonal distances, J. Comput. Appl. Math., 158 (2003), pp. 277–296. · Zbl 1034.65007 |
| [2] | A. Atieg and G. A. Watson, Use oflpnorms in fitting curves and surfaces to data, Aust. N. Z. Ind. Appl. Math. J., 45 (E) (2004), pp. C187–C200. · Zbl 1063.65523 |
| [3] | S. J. Ahn, W. Rauh, and H.-J. Warnecke, Least-squares orthogonal distances fitting of circle, sphere, ellipse, hyperbola, and parabola, Pattern Recognition, 34 (2001), pp. 2283–2303. · Zbl 0991.68127 |
| [4] | S. J. Ahn, E. Westkämper, and W. Rauh, Orthogonal distance fitting of parametric curves and surfaces, in J. Levesley, I. J. Anderson, and J. C. Mason (eds.), Algorithms for Approximation IV, University of Huddersfield, 2002, pp. 122–129. · Zbl 1017.68555 |
| [5] | M. Berman, Estimating the parameters of a circle when angular differences are known, Appl. Stat., 32 (1983), pp. 1–6. |
| [6] | M. Gulliksson, I. Söderkvist, and G. A. Watson, Implicit surface fitting using directional constraints, BIT, 41 (2001), pp. 331–344. · Zbl 0982.65018 |
| [7] | P. T. Boggs, R. H. Byrd, and R. B. Schnabel, A stable and efficient algorithm for nonlinear orthogonal distance regression, SIAM J. Sci. Stat. Comput., 8 (1987), pp. 1052–1078. · Zbl 0637.65150 |
| [8] | G. Hadley, Linear Programming, Addison-Wesley, Reading, Mass., 1962. |
| [9] | H.-P. Helfrich and D. Zwick, A trust region algorithm for parametric curve and surface fitting, J. Comput. Appl. Math., 73 (1996), pp. 119–134. · Zbl 0861.65010 |
| [10] | H.-P. Helfrich and D. Zwick, l1andlitting of geometric elements, in J. Levesley, I. J. Anderson, and J. C. Mason (eds.), Algorithms for Approximation IV, University of Huddersfield, 2002, pp. 122–129. |
| [11] | J. R. Rice, Tchebycheff approximation in a compact metric space, Bull. Am. Math. Soc., 68 (1962), pp. 405–410. · Zbl 0111.26501 |
| [12] | C. Ross, I. J. Anderson, J. C. Mason, and D. A. Turner, Approximating coordinate data that has outliers, in P. Ciarlini, A. B. Forbes, F. Pavese and D. Richter (eds.), Advanced Mathematical and Computational Tools in Metrology IV, Series on Advances in Mathematics for Applied Sciences, Volume 53, World Scientific, Singapore, 2000, pp. 210–219. · Zbl 0971.62084 |
| [13] | H. Späth, Estimating the parameters of an ellipse when angular differences are known, Comput. Stat., 14 (1999), pp. 491–500. · Zbl 0939.62050 |
| [14] | H. Späth, Least squares fitting of spheres and ellipsoids using not orthogonal distances, Math. Commun., 6 (2001), pp. 89–96. · Zbl 0987.65020 |
| [15] | R. Strebel, D. Sourlier, and W. Gander, A comparison of orthogonal least squares fitting in coordinate metrology, in S. Van Huffel (ed.), Recent Advances in Total Least Squares and Errors-in-Variables Techniques, SIAM, Philadelphia, 1997, pp. 249–258. · Zbl 0879.65007 |
| [16] | D. A. Turner, The Approximation of Cartesian Co-ordinate Data by Parametric Orthogonal Distance Regression, PhD Thesis, University of Huddersfield, 1999. |
| [17] | D. A. Turner, I. J. Anderson, J. C. Mason, M. G. Cox, and A. B. Forbes, An efficient separation-of-variables approach to parametric orthogonal distance regression, in P. Ciarlini, A. B. Forbes, F. Pavese, and D. Richter (eds.), Advanced Mathematical and Computational Tools in Metrology IV, Series on Advances in Mathematics for Applied Sciences, Volume 53, World Scientific, Singapore, 2000, pp. 246–255. · Zbl 0961.62115 |
| [18] | G. A. Watson, Approximation Theory and Numerical Methods, Wiley, 1980. · Zbl 0442.65005 |
| [19] | G. A. Watson, Least squares fitting of circles and ellipses to measured data, BIT, 39 (1999), pp. 176–191. · Zbl 0921.65004 |
| [20] | G. A. Watson, Some problems in orthogonal and non-orthogonal distance regression, in J. Levesley, I. J. Anderson, and J. C. Mason (eds.), Algorithms for Approximation IV, University of Huddersfield, 2002, pp. 294–302. |
| [21] | G. A. Watson, On the Gauss-Newton method forl1orthogonal distance regression, IMA J. Numer. Anal., 22 (2002), pp. 345–357. · Zbl 1017.65004 |
| [22] | G. A. Watson, Incorporating angular information into parametric models, BIT, 42 (2002), pp. 867–878. · Zbl 1012.65016 |
| [23] | G. A. Watson and C. Yiu, On the solution of the errors in variables problem using thel1norm, BIT, 31 (1991), pp. 697–710. · Zbl 0745.65012 |
| [24] | D. S. Zwick, Applications of orthogonal distance regression in metrology, in S. Van Huffel (ed.), Recent Advances in Total Least Squares and Errors-in-Variables Techniques, SIAM, Philadelphia, 1997, pp. 265–272. · Zbl 0879.65009 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
