ALGORITHMS AND COMPLEXITY FOR LEAST MEDIAN OF SQUARES REGRESSION

被引：46

作者：

STEELE, JM ^{[1
]}

STEIGER, WL ^{[1
]}

机构：

[1] RUTGERS STATE UNIV,DEPT COMP SCI,NEW BRUNSWICK,NJ 08903

来源：

DISCRETE APPLIED MATHEMATICS | 1986年 / 14卷 / 01期

关键词：

COMPUTER PROGRAMMING - Algorithms;

D O I：

10.1016/0166-218X(86)90009-0

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Given n points left brace (x//i,Y//i) right brace 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 ) equals median( vertical y//i minus ( alpha plus beta x//i) vertical ); 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(nn))**2).

引用

页码：93 / 100

页数：8