TY - JOUR
TI - Algorithms and Complexity for a Statistical Problem. Minimum Median Residual Fitting
DO - https://doi.org/doi:10.7282/T3V98CJQ
AU - Steiger, William L.
AU - Steele, J. Michael
PY - 1984-11
AB - 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.
LA - English
ER -