Algorithms and Complexity for a Statistical Problem. Minimum Median Residual Fitting

Given n points f'xi,yi)} in the plane we study the problem of fitting the minimum median squared residual (MM2 R) line. This involves the study of the function fia,g) = median(Jyj - (a + Oxfl); 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 0(n3) in the worst case. Our most practical algorithm appears to be one which has worst case behavior of only 0(n3 log(n)), but which we conjecture to have expected time complexity 0((n log(n))2 ). Generalizations to k dimensions are mentioned.Technical report DCS-TR-14