A practical approximation algorithm for the LMS line estimator

作     者：Mount, David M. Netanyahu, Nathan S. Romanik, Kathleen Silverman, Ruth Wu, Angela Y. 

作者机构：Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA Bar Ilan Univ Dept Comp Sci Ramat Gan Israel Univ Maryland Ctr Automat Res College Pk MD 20742 USA White Oak Technol Inc Silver Spring MD USA American Univ Dept Comp Sci Washington DC 20016 USA 

出 版 物：《COMPUTATIONAL STATISTICS & DATA ANALYSIS》 (计算统计学与数据分析)

年 卷 期：2007年第51卷第5期

页      面：2461-2486页

核心收录：

学科分类：08[工学] 0714[理学-统计学（可授理学、经济学学位）] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：least median-of-squares regression robust estimation line fitting approximation algorithms randomized algorithms line arrangements 

摘      要：The problem of fitting a straight line to a finite collection of points in the plane is an important problem in statistical estimation. Robust estimators are widely used because of their lack of sensitivity to outlying data points. The least median-of-squares (LMS) regression line estimator is among the best known robust estimators. Given a set of it points in the plane, it is defined to be the line that minimizes the median squared residual or, more generally, the line that minimizes the residual of any given quantile q, where 0 = 0, and a quantile approximation, which approximates the fraction of points that lie within the strip to within a given error bound epsilon(q) = 0. We present two randomized approximation algorithms for the LMS line estimator. The first is a conceptually simple quantile approximation algorithm, which given fixed q and epsilon(q) 0 runs in 0(n log n) time. The second is a practical algorithm, which can solve both types of approximation problems or be used as an exact algorithm. We prove that when used as a quantile approximation, this algorithm s expected running time is O(n log(2) n). We present empirical evidence that the latter algorithm is quite efficient for a wide variety of input distributions, even when used as an exact algorithm. (c) 2006 Elsevier B.V. All rights reserved.