AbstractGiven 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.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).