New Algorithms for L1 Norm Regression
Abstract
In this paper, we propose four algorithms for L1 norm computation of regression parameters, where two of them are more efficient for simple and multiple regression models. However, we start with restricted simple linear regression and corresponding derivation and computation of the weighted median problem. In this respect, a computing function is coded. With discussion on the m parameters model, we continue to expand the algorithm to include unrestricted simple linear regression, and two crude and efficient algorithms are proposed. The procedures are then generalized to the m parameters model by presenting two new algorithms, where the algorithm 4 is selected as more efficient. Various properties of these algorithms are discussed.
References
I. Barrodale, F.D.K. Roberts (1974) Algorithm 478: Solution of an overdetermined system of equations in the L1 norm. Comm. ACM, 17, 319-320.
C.M. Bender, S.A. Orszag (1978) Advanced mathematical methods for scientists and engineers, McGraw-Hill.
Bijan Bidabad (1987a) Least absolute error estimation. The First International Conference on Statistical Data Analysis Based on the L1 norm and Related Methods, Neuchatel, Switzerland. http://www.bidabad.com/doc/lae-I.pdf
Bijan Bidabad (1987b) Least absolute error estimation, part II. Submitted to the First International Conference on Statistical Data Analysis Based on the L1 norm and Related Methods, Neuchatel, Switzerland. http://www.bidabad.com/doc/lae-II.pdf
Bijan Bidabad (1988a) A proposed algorithm for least absolute error estimation. Proc. of the Third Seminar of Mathematical Analysis. Shiraz Univ., 24-34, Shiraz, Iran.
Bijan Bidabad (1988b) A proposed algorithm for least absolute error estimation, part II. Proc. of the Third Seminar of Mathematical Analysis, Shiraz Univ., 35-50, Shiraz, Iran.
Bijan Bidabad (1989a) Discrete and continuous L1 norm regressions, proposition of discrete approximation algorithms and continuous smoothing of concentration surface, Ph.D. thesis, Islamic Azad Univ., Tehran, Iran. http://www.bidabad.com/doc/L1-norm-thesis-en.pdf
Bijan Bidabad (1989b) Discrete and continuous L1 norm regressions, proposition of discrete approximation algorithms and continuous smoothing of concentration surface, Ph.D. thesis, Islamic Azad Univ., Tehran, Iran. Farsi translation. http://www.bidabad.com/doc/L1-norm-thesis-fa.pdf
Bijan Bidabad (2005). L1 norm based computational algorithms. http://www.bidabad.com/doc/l1-article6.pdf
Bijan Bidabad (2005). L1 norm solution of overdetermined system of linear equations. http://www.bidabad.com/doc/l1-article5.pdf
Bijan Bidabad (2005). L1 norm based data analysis and related methods. http://www.bidabad.com/doc/l1-articl1.pdf
Bijan Bidabad (2005). New algorithms for the L1 norm regression. http://www.bidabad.com/doc/l1-article2.pdf
Bijan Bidabad (2005). Comparative study of the L1 norm regression algorithms. http://www.bidabad.com/doc/l1-articl3.pdf
Bijan Bidabad (2005). Continuous L1 norm estimation of Lorenz curve. http://www.bidabad.com/doc/l1-articl4.pdf
Bijan Bidabad (1993). Estimating Lorenz curve for Iran by using continuous L1 norm estimation, Economics and Management Journal, Islamic Azad University, No. 19, winter 1993, pp. 83-101. http://www.bidabad.com/doc/iraninc-l1.pdf
Bijan Bidabad (2005). Continuous L1 norm estimation of Lorenz curve when probability density function is known.
Bijan Bidabad (2005). USA Income distribution counter-business-cyclical trend (Estimating Lorenz curve using continuous L1 norm estimation). First meeting of the Society for the Study of Economic Inequality (ECINEQ), Palma de Mallorca, Spain, July 20-22, 2005.
http://www.uib.es/congres/ecopub/ecineq/general.html
http://www.uib.es/congres/ecopub/ecineq/papers/039Bidabab.pdf
http://www.bidabad.com/doc/estimating-lorenz-us.pdf
Bijan Bidabad, Hamid Shahrestani. (2008) An implied inequality index using L1 norm estimation of Lorenz curve. Global Conference on Business and Finance Proceedings. Mercedes Jalbert, managing editor, ISSN 1931-0285 CD, ISSN 1941-9589 Online, Volume 3, Number 2, 2008, The Institute for Business and Finance Research, Ramada Plaza Herradura, San Jose, Costa Rica, May 28-31, 2008, pp. 148-163. Global Journal of Business Research, Vol. 4, No. 1, 2010, pp.29-45.
http://www.bidabad.com/doc/L1-Implied-inequality-index-4.pdf
http://www.theibfr.com/archive/ISSN-1941-9589-V3-N2-2008.pdf
http://www.bidabad.com/doc/SSRN-id1631861.pdf
P. Bloomfield, W. Steiger (1980) Least absolute deviations curve fitting. SIAM J. Sci. Stat. Comput. 1, 290-301.
R.J. Boscovich (1757) De litteraria expeditione per pontificiam ditionem, et synopsis amplioris operis..., 'Bononiensi' scientiarum et artum instituto atque academia commetarii, vol.4, 353-396. Reprinted with a Serbo-Croatian translation by N. Cubranic, Institute of higher geodesy, University of Zagreb 1961.
J. Chambers (1971) Algorithm 410: partial sorting. Comm. ACM, 14, 357-358.
F.H. Clarke (1983) Optimization and nonsmooth analysis. Wiley, New York C.A.R. Hoare (1961) Algorithm 63 partition; 64, quicksort; and 65, find., Comm. ACM, 4, July, 321-322.
C.A.R. Hoare (1962) Quicksort. Comput. J., 5, 10-15.
O.J. Karst (1958) Linear curve fitting using least deviations. JASA, 53, 118-132.
P.S. Laplace (1812) Theorie analytique des probabilites, Mme courcier Paris 1820 Reprinted in his oeuvres, vol.7, Imprimerie Royale, Paris, 1847, and Gauthier-Villars et fils, Paris 1886.
P.S. Laplace (1818) Duexieme supplement to Laplace (1812).
S. Scowen (1965) Algorithm 271 Quickersort. Comm. ACM, 8, 669-670.
R.S. Singleton (1969) Algorithm 347 Sort. Comm. ACM, 12, 185-186.
L.D. Taylor (1974) Estimating by minimizing the sum of absolute errors. In
P. Zarembka (ed.) Frontiers in econometrics. Academic Press.
Copyright (c) 2019 Bijan Bidabad
This work is licensed under a Creative Commons Attribution 4.0 International License.
