Algorithms and complexity for least median of squares regression (Q1072298)

Given n points \(\{(x_ i,y_ i)\}\) in the plane we study the problem of calculating the least median of squares regression line. This involves the study of the function \(f(\alpha,\beta)=median(| y_ i-(\alpha +\beta x_ i)|);\) it is piecewise linear and can have a quadratic number of local minima. Several algorithms that locate a minimizer of f are presented. The best of these has time complexity \(O(n^ 3)\) in the worst case. Our most practical algorithm appears to be one which has worst case behavior of \(O(n^ 3\log (n))\), but we provide a probabilistic speed-up of this algorithm which appears to have expected time complexity of O((n log(n))\({}^ 2)\).