New algorithms for computing the least trimmed squares regression estimator (Q5941333)

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 \textit{P. J. Rousseeuw} [J. Am. Stat. Assoc. 79, 871-880 (1984; Zbl 0547.62046)], is a high breakdown estimator. 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.