TY - JOUR
T1 - Algorithms and complexity for least median of squares regression
AU - Steele, J. M.
AU - Steiger, W. L.
N1 - Funding Information:
supported in part by NSF grant DMS-8414069.
PY - 1986/5
Y1 - 1986/5
N2 - Given n points {(xi, yi)} in the plane we study the problem of calculating the least median of squares regression line. This involves the study of the function f{hook}(α, β) = median(|yi-(α+βxi)|); it is piecewise linear and can have a quadratic number of local minima. Several algorithms that locate a minimizer of f{hook} are presented. The best of these has time complexity O(n3) in the worst case. Our most practical algorithm appears to be one which has worst case behavior of O(n3 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).
AB - Given n points {(xi, yi)} in the plane we study the problem of calculating the least median of squares regression line. This involves the study of the function f{hook}(α, β) = median(|yi-(α+βxi)|); it is piecewise linear and can have a quadratic number of local minima. Several algorithms that locate a minimizer of f{hook} are presented. The best of these has time complexity O(n3) in the worst case. Our most practical algorithm appears to be one which has worst case behavior of O(n3 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).
UR - http://www.scopus.com/inward/record.url?scp=0022711462&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0022711462&partnerID=8YFLogxK
U2 - 10.1016/0166-218X(86)90009-0
DO - 10.1016/0166-218X(86)90009-0
M3 - Article
AN - SCOPUS:0022711462
VL - 14
SP - 93
EP - 100
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
SN - 0166-218X
IS - 1
ER -