New algorithms for computing the least trimmed squares regression estimator
The outlier detection in multiple linear regression is a difficult problem because of the masking effect. A procedure that works successfully uses residuals based on a high breakdown estimator. The least trimmed squares (LTS) estimator, which was proposed by Rousseeuw (J. Amer. Statist. Assoc. 79 (1984)), is a high breakdown estimator. In this paper we propose two algorithms to compute the LTS estimator. The first algorithm is probabilistic and is based on an exchange procedure. The second algorithm is exact and based on a branch-and-bound technique that guarantees global optimality without exhaustive evaluation. We discuss the implementation of these algorithms using orthogonal decomposition procedures and propose several accelerations. The application of the new algorithms to real and simulated data sets shows that they significantly reduce the computational cost with respect to the algorithms previously described in the literature.
least trimmed squares outliers multiple linear regression high breakdown point branch and bound exchange algorithm