Recursive Algorithm for L1 Norm Estimation in Linear Models
Publication: Journal of Surveying Engineering
Volume 137, Issue 1
Abstract
L1 norm estimator has been widely used as a robust parameter estimation method for outlier detection. Different algorithms have been applied for L1 norm minimization among which the linear programming problem based on the simplex method is well known. In the present contribution, in order to solve an L1 norm minimization problem in a linear model, an interior point algorithm is developed which is based on Dikin’s method. The method can be considered as an appropriate alternative for the classical simplex method, which is sometimes time-consuming. The proposed method, compared with the simplex method, is thus easier for implementation and faster in performance. Furthermore, a recursive form of the Dikin’s method is derived, which resembles the recursive least-squares method. Two simulated numerical examples show that the proposed algorithm gives as accurate results as the simplex method but in considerably less time. When dealing with a large number of observations, this algorithm can thus be used instead of the iteratively reweighted least-squares method and the simplex method.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
We would like to acknowledge the editor-in-chief and three anonymous reviewers for their useful comments, which significantly improved the presentation of this paper.
References
Amiri-Simkooei, A. R. (2003). “Formulation of L1 norm minimization in Gauss-Markov models.” J. Surv. Eng., 129(1), 37–43.
Baarda, W. (1968). A testing procedure for use in geodetic networks, Publication on Geodesy, Netherlands Geodetic Commission, Delft, The Netherlands.
Barrodale, I., and Roberts, F. (1972). “Solution of an overdetermined equations in the L1 norm.” Mathematics Rep. No. 69, University of Victoria, Victoria, B.C., Canada.
Barrodale, I., and Roberts, F. (1973). “An improved algorithm for discrete L1 linear approximation.” SIAM (Soc. Ind. Appl. Math.) J. Numer. Anal., 10(5), 839–848.
Baselga, S. (2007). “A global optimization solution of robust estimation.” J. Surv. Eng., 133(3), 123–128.
Bazaraa, M. S., Jarvis, J. J., and Sherali, H. D. (1990). Linear programming and network flows, 2nd Ed., Wiley, New York.
Dantzig, G. B. (1963). Linear programming and extensions, Princeton University Press, Princeton, N.J.
Dantzig, G. B., and Thapa, M. N. (1997). Linear programming 1: Introduction, Springer, New York.
Hekimoglu, S. (1997). “The finite sample breakdown points of conventional iterative outlier detection procedures.” J. Surv. Eng., 123(1), 15–31.
Junhuan, P. (2005). “The asymptotic variance-covariance matrix, Baarda test and reliability of L1 norm estimates.” J. Geodyn., 78, 668–682.
Koch, K. R. (1999). Parameter estimation and hypothesis testing in linear models, Springer, Berlin.
Krarup, T., Juhl, J., and Kubik, K. (1980). “Götterdämmerung over least squares adjustment.” Proc., 14th Congress of the Int. Society of Photogrammetry, Vol. B3, 369–378.
Maronna, R. A., Martin, R. D., and Yohai, V. J. (2006). Robust statistics: Theory and methods, Wiley series in probability and statistics, U.K.
Marshall, J., and Bethel, J. (1996). “Basic concepts of L1 norm minimization for surveying applications.” J. Surv. Eng., 122(4), 168–179.
Pope, A. J. (1976). “The statistics of residuals and the detection of outliers.” NOAA Technical Rep. No. NOS65 NGS1, U.S. Department of Commerce, National Geodetic Survey, Rockville, Md.
Portnoy, S., and Koenker, R. (1997). “The Gaussian hare and the Laplacian tortoise: Computability of squared-error versus absolute-error estimators.” Stat. Sci., 12(4), 279–300.
Roos, C., Terlaky, T., and Vial, J. P. (2005). Interior point methods for linear optimization, Revised Ed., Springer, New York.
Teunissen, P. J. G., Simons, D. G., and Tiberius, C. C. J. M. (2005). “Probability and observation theory.” Lecture notes AE2-E01, Delft University of Technology, Delft, The Netherlands.
Xu, G. (2007). GPS: Theory, algorithms, and applications, 2nd Ed., Springer, Berlin.
Yang, Y. (1994). “Robust estimation for dependent observations.” Manuscr. Geod., 19, 10–17.
Yang, Y. (1999). “Robust estimation of geodetic datum transformation.” J. Geodyn., 73, 268–274.
Information & Authors
Information
Published In
Journal of Surveying Engineering
Volume 137 • Issue 1 • February 2011
Pages: 1 - 8
Copyright
© 2011 ASCE.
History
Received: May 26, 2009
Accepted: Feb 24, 2010
Published online: Feb 26, 2010
Published in print: Feb 2011
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.