Recursive Algorithm for L1 Norm Estimation in Linear Models
- 1 February 2011
- journal article
- Published by American Society of Civil Engineers (ASCE) in Journal of Surveying Engineering
- Vol. 137 (1) , 1-8
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 ...Keywords
This publication has 13 references indexed in Scilit:
- Global Optimization Solution of Robust EstimationJournal of Surveying Engineering, 2007
- The asymptotic variance–covariance matrix, Baarda test and the reliability of L1-norm estimatesJournal of Geodesy, 2005
- Formulation of L1 Norm Minimization in Gauss-Markov ModelsJournal of Surveying Engineering, 2003
- Robust estimation of geodetic datum transformationJournal of Geodesy, 1999
- Parameter Estimation and Hypothesis Testing in Linear Models1999
- The Gaussian hare and the Laplacian tortoise: computability of squared-error versus absolute-error estimatorsStatistical Science, 1997
- Finite Sample Breakdown Points of Outlier Detection ProceduresJournal of Surveying Engineering, 1997
- Basic Concepts ofL1Norm Minimization for Surveying ApplicationsJournal of Surveying Engineering, 1996
- An Improved Algorithm for Discrete $l_1 $ Linear ApproximationSIAM Journal on Numerical Analysis, 1973
- Linear Programming and Extensions1963