Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T23:06:24.891Z Has data issue: false hasContentIssue false
  • English
  • Français

THE BEST LEAST ABSOLUTE DEVIATIONS LINE – PROPERTIES AND TWO EFFICIENT METHODS FOR ITS DERIVATION

Part of: Operations research and management science Numerical approximation and computational geometry Functional-differential and differential-difference equations Probabilistic methods, simulation and stochastic differential equations Linear inference, regression

Published online by Cambridge University Press:  01 October 2008

KRISTIAN SABO  and
RUDOLF SCITOVSKI
KRISTIAN SABO
Affiliation:
Department of Mathematics, University of Osijek, Trg Ljudevita Gaja 6, HR-31000 Osijek, Croatia (email: ksabo@mathos.hr)
RUDOLF SCITOVSKI*
Affiliation:
Department of Mathematics, University of Osijek, Trg Ljudevita Gaja 6, HR-31000 Osijek, Croatia (email: scitowsk@mathos.hr)
*
✉For correspondence; e-mail: scitowsk@mathos.hr
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Given a set of points in the plane, the problem of existence and finding the least absolute deviations line is considered. The most important properties are stated and proved and two efficient methods for finding the best least absolute deviations line are proposed. Compared to other known methods, our proposed methods proved to be considerably more efficient.

Keywords

least absolute deviationsLADl1-norm approximationweighted median problem

MSC classification

Secondary: 65D10: Smoothing, curve fitting 65C20: Models, numerical methods 62J05: Linear regression 90C56: Derivative-free methods and methods using generalized derivatives 90B85: Continuous location 34K29: Inverse problems

Information

Type
Research Article
Information
The ANZIAM Journal , Volume 50 , Issue 2 , October 2008 , pp. 185 - 198
Copyright
Copyright © Australian Mathematical Society 2009

References

[1]Atieg, A. and Watson, G. A., “Use of l p norms in fitting curves and surfaces to data”, ANZIAM J. 45 (2004) C187–C200.CrossRefGoogle Scholar
[2]Bargiela, A. and Hartley, J. K., “Orthogonal linear regression algorithm based on augmented matrix formulation”, Comput. Oper. Res. 20 (1993) 829–836.CrossRefGoogle Scholar
[3]Barrodale, A. and Roberts, F. D. K., “An improved algorithm for discrete l 1 linear approximation”, SIAM J. Numer. Anal. 10 (1973) 839–848.CrossRefGoogle Scholar
[4]Björck, Å., Numerical methods for least squares problems (SIAM, Philadelphia, PA, 1996).CrossRefGoogle Scholar
[5]Bloomfield, P. and Steiger, W., Least absolute deviations: theory, applications, and algorithms (Birkhäuser, Boston, 1983).Google Scholar
[6]Brimberg, J., Juel, H. and Schöbel, A., “Properties of three-dimensional median line location models”, Ann. Oper. Res. 122 (2003) 71–85.CrossRefGoogle Scholar
[7]Cupec, R., Scene reconstruction and free space representation for biped walking robots (VDI Verlag, Düsseldorf, 2005).Google Scholar
[8]Dasgupta, M. and Mishra, S. K., Least absolute deviation estimation of linear econometric models: A literature review. http:// mpra.ub.uni-muenchen.de/ 1781/.Google Scholar
[9]Demidenko, E. Z., Optimization and regression (Nauka, Moscow, 1989) (in Russian).Google Scholar
[10]Dennis, J. E. and Schnabel, R. B., Numerical methods for unconstrained optimization and nonlinear equations (SIAM, Philadelphia, PA, 1996).CrossRefGoogle Scholar
[11]Dodge (ed.), Y., “Statistical data analysis based on the L 1-norm and related methods”, in Proceedings of the Third International Conference on Statistical Data Analysis Based on the L 1-norm and Related Methods (Elsevier, Neuchâtel, 1997).Google Scholar
[12]Gurwitz, C., “Weighted median algorithms for L 1 approximation”, BIT 30 (1990) 101–110.CrossRefGoogle Scholar
[13]Hadeler, K. P., Jukić, D. and Sabo, K., “Least squares problems for Michaelis Menten kinetics”, Math. Methods Appl. Sci. 30 (2007) 1231–1241.CrossRefGoogle Scholar
[14]Hirai, K., Hirose, M., Haikawa, Y. and Takenaka, T., “The development of Honda humanoid robot”, in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (IEEE, Leuven, Belgium, 1998) 1321–1326.Google Scholar
[15]Jukić, D., Sabo, K. and Scitovski, R., “Total least squares fitting Michaelis–Menten enzyme kinetic model function”, J. Comput. Appl. Math. 201 (2007) 230–246.CrossRefGoogle Scholar
[16]Jukić, D. and Scitovski, R., “The best least squares approximation problem for a 3-parametric exponential regression model”, ANZIAM J. 42 (2000) 254–266.CrossRefGoogle Scholar
[17]Karst, O. J., “Linear curve fitting using least deviations”, J. Amer. Statist. Assoc. 53 (1958) 118–132.CrossRefGoogle Scholar
[18]Kelley, C. T., Iterative methods for optimization (SIAM, Philadelphia, PA, 1999).CrossRefGoogle Scholar
[19]Korneenko, N. M. and Martini, H., “Hyperplane approximation and related topics”, in New trends in discrete and computational geometry (ed. J. Pach), (Springer, Berlin, 1993).Google Scholar
[20]Lewis, R. M., Torczon, V. and Trosset, M. W., “Direct search methods: then and now”, J. Comput. Appl. Math. 124 (2000) 191–207.CrossRefGoogle Scholar
[21]Li, Y. and Arce, G. R., “A maximum likelihood approach to least absolute deviation regression”, EURASIP J. Appl. Signal Process. 12 (2004) 1762–1769.Google Scholar
[22]Madsen, K. and Nielsen, H. B., “A finite smoothing algorithm for linear l 1 estimation”, SIAM J. Optim. 3 (1993) 223–235.CrossRefGoogle Scholar
[23]Nelder, J. A. and Mead, R., “A simplex method for function minimization”, Comput. J. 7 (1965) 308–313.CrossRefGoogle Scholar
[24]Osborne, M. R., Finite algorithms in optimization and data analysis (Wiley, Chichester, 1985).Google Scholar
[25]Schlossmacher, E. J., “An iterative technique for absolute deviations curve fitting”, J. Amer. Statist. Assoc. 68 (1973) 857–859.CrossRefGoogle Scholar
[26]Schöbel, A., Locating lines and hyperplanes: theory and algorithms (Springer, Berlin, 1999).CrossRefGoogle Scholar
[27]Scitovski, R., Ungar, Š. and Jukić, D., “Approximating surface by moving total least squares method”, Appl. Math. Comput. 93 (1998) 219–232.Google Scholar
[28]Späth, H., “On discrete linear orthogonal L p approximation”, ZAMM 62 (1982) 354–355.Google Scholar
[29]Späth, H., Mathematical algorithms for linear regression (Academic Press Professional, San Diego, 1992).Google Scholar
[30]Späth, H., “Identifying spatial point sets”, Math. Commun. 8 (2003) 69–76.Google Scholar
[31]Späth, H. and Watson, G. A., “On orthogonal linear l 1 approximation”, Numer. Math. 51 (1987) 531–543.CrossRefGoogle Scholar
[32]Tarantola, A., Inverse problem theory and methods for model parameter estimation (SIAM, Philadelphia, PA, 2005).CrossRefGoogle Scholar
[33]Trendafilov, N. T. and Watson, G. A., “The l 1 oblique Procrustes problem”, Statist. Comput. 14 (2004) 39–51.CrossRefGoogle Scholar
[34]Watson, G. A., Approximation theory and numerical methods (Wiley, Chichester, 1980).Google Scholar
[35]Watson, G. A., “Aspects of approximation with emphasis on the univariate case”, in The state of the art in numerical analysis, IMA Conference Series (eds. I. S. Duff and G. A. Watson), (Oxford University Press Inc., New York, 1997).Google Scholar
[36]Watson, G. A., “On the Gauss–Newton method for l 1 orthogonal distance regression”, IMA J. Numer. Anal. 22 (2002) 345–357.CrossRefGoogle Scholar
[37]Wesolowsky, G. O., “A new descent algorithm for the least absolute value regression problem”, Comm. Statist. Simulation Comput. B10 (1981) 479–491.CrossRefGoogle Scholar
[38]Wolfram, S., The mathematica book (Wolfram Media, Champaign, IL, 2007).Google Scholar