Computing the update of the repeated median in linear time regression line

被引：19

作者：

Bernholt, T

Fried, R

机构：

[1] Univ Dortmund, Fachbereich Informat, D-44221 Dortmund, Germany

[2] Univ Dortmund, Fachbereich Statist, D-44221 Dortmund, Germany

来源：

INFORMATION PROCESSING LETTERS | 2003年 / 88卷 / 03期

关键词：

robust regression; time series analysis; robust filtering; repeated median; computational geometry; efficient algorithms;

D O I：

10.1016/S0020-0190(03)00350-8

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The repeated median line estimator is a highly robust method for fitting a regression line to a set of n data points in the plane. In this paper, we consider the problem of updating the estimate after a point is removed from or added to the data set. This problem occurs, e.g., in statistical online monitoring, where the computational effort is often critical. We present a deterministic algorithm for the update working in O(n) time and O(n(2)) space. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：111 / 117

页数：7

共 6 条

[1] REPORTING AND COUNTING SEGMENT INTERSECTIONS [J].