An approximation algorithm for least median of squares regression

被引：19

作者：

Olson, CF ^{[1
]}

机构：

[1] CORNELL UNIV,DEPT COMP SCI,ITHACA,NY 14853

来源：

INFORMATION PROCESSING LETTERS | 1997年 / 63卷 / 05期

关键词：

least median of squares regression; approximation algorithms; computational geometry; design of algorithms;

D O I：

10.1016/S0020-0190(97)00132-4

中图分类号：

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

学科分类号：

0812 ;

摘要：

Least median of squares (LMS) regression is a robust method to fit equations to observed data (typically in a linear model). This paper describes an approximation algorithm for LMS regression. The algorithm generates a regression solution with median residual no more than twice the optimal median residual. Random sampling is used to provide a simple O(n log(2) n) expected time algorithm in the two-dimensional case that is successful with high probability. This algorithm is also extended to arbitrary dimension d with O(n(d-1) log n) worst-case complexity for fixed d > 2. (C) 1997 Elsevier Science B.V.

引用

页码：237 / 241

页数：5

共 50 条

[21] A new approach to least median of squares and regression through the origin
Kayhan, Yasemin
Gunay, Suleyman
COMMUNICATIONS IN STATISTICS-THEORY AND METHODS, 2008, 37 (05) : 773 - 781
[22] LMSMVE - A PROGRAM FOR LEAST MEDIAN OF SQUARES REGRESSION AND ROBUST DISTANCES
DALLAL, GE
ROUSSEEUW, PJ
COMPUTERS AND BIOMEDICAL RESEARCH, 1992, 25 (04): : 384 - 391
[23] APPROXIMATION OF LEAST-SQUARES REGRESSION ON NESTED SUBSPACES
COX, DD
ANNALS OF STATISTICS, 1988, 16 (02): : 713 - 732
[24] AN EFFICIENT ALGORITHM FOR THE CLASSICAL LEAST SQUARES APPROXIMATION
Dimitrov, Dimitar K.
Peixoto, Lourenco L.
SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2020, 42 (05): : A3233 - A3249
[25] AN ALGORITHM FOR RESTRICTED LEAST-SQUARES REGRESSION
DYKSTRA, RL
JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1983, 78 (384) : 837 - 842
[26] LEAST MEDIAN OF WEIGHTED SQUARES IN LOGISTIC-REGRESSION WITH LARGE STRATA
CHRISTMANN, A
BIOMETRIKA, 1994, 81 (02) : 413 - 417
[27] COMPUTING LEAST MEDIAN OF SQUARES REGRESSION LINES AND GUIDED TOPOLOGICAL SWEEP
EDELSBRUNNER, H
SOUVAINE, DL
JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1990, 85 (409) : 115 - 119
[28] Regression by Least Median Squares in the Calculation of Transition Times for Calibration in Chronopotentiometry
Department of Chemistry, Fac. of Food Science and Chemistry, University of Burgos, Pza. Misael Bañuelos s/n, E-09001 Burgos, Spain
不详
不详
Electroanalysis, 10 (927-931):
[29] Regression by least median squares in the calculation of transition times for calibration in chronopotentiometry
Ortiz, MC
Palacios, JL
Sarabia, LA
Piangerelli, MG
Cingolani, D
ELECTROANALYSIS, 1996, 8 (10) : 927 - 931
[30] Regression by Least Median Squares in the Calculation of Transition Times for Calibration in Chronopotentiometry
Ortiz, M. C.
Palacios, J. L.
Sarabia, L. A.
Piangerelli, M. G.
Electroanalysis, 8 (10):

← 1 2 3 4 5 →