|
|
|
|
An Approximation Algorithm for Least Median of Squares Regression
Clark F. Olson Information Processing Letters, 63(5): 237-241, September 1997. Download (339 K) 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 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. |
