An approximation algorithm for least median of squares regression

Least median of squares (LMS) regression is a robust method to fit equations to observed data (typically in a linear model). This paper describes an approximation algorithm for LMS regression. The algorithm generates a regression solution with median residual no more than twice the optimal median residual. Random sampling is used to provide a simple O(n log(2) n) expected time algorithm in the two-dimensional case that is successful with high probability. This algorithm is also extended to arbitrary dimension d with O(n(d-1) log n) worst-case complexity for fixed d > 2. (C) 1997 Elsevier Science B.V.