The complexity of computing the MCD-estimator

被引：15
作者：
Bernholt, T
Fischer, P
机构：
[1] Univ Dortmund, Lehrstuhl Informat 2, D-44221 Dortmund, Germany
[2] Tech Univ Denmark, IMM, DK-2800 Lyngby, Denmark
来源：
THEORETICAL COMPUTER SCIENCE | 2004年 / 326卷 / 1-3期
关键词：
computational statistics; efficient algorithms; NP-completeness; combinatorial geometry;
D O I：
10.1016/j.tcs.2004.08.005
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In modem statistics the robust estimation of parameters is a central problem, i.e., an estimation that is not or only slightly affected by outliers in the data. The minimum covariance determinant (MCD) estimator (J. Amer. Statist. Assoc. 79 (1984) 871) is probably one of the most important robust estimators of location and scatter. The complexity of computing the MCD, however, was unknown and generally thought to be exponential even if the dimensionality of the data is fixed. Here we present a polynomial time algorithm for MCD for fixed dimension of the data. In contrast we show that computing the MCD-estimator is NP-hard if the dimension varies. (C) 2004 Elsevier B.V. All rights reserved.
引用
收藏
页码：383 / 398
页数：16
相关论文
共 11 条
[1]   The largest nonidentifiable outlier: a comparison of multivariate simultaneous outlier identification rules [J].
Becker, C ;
Gather, U .
COMPUTATIONAL STATISTICS & DATA ANALYSIS, 2001, 36 (01) :119-127
[2]   ASYMPTOTICS FOR THE MINIMUM COVARIANCE DETERMINANT ESTIMATOR [J].
BUTLER, RW ;
DAVIES, PL ;
JHUN, M .
ANNALS OF STATISTICS, 1993, 21 (03) :1385-1400
[3]   ASYMPTOTIC-BEHAVIOR OF S-ESTIMATES OF MULTIVARIATE LOCATION PARAMETERS AND DISPERSION MATRICES [J].
DAVIES, PL .
ANNALS OF STATISTICS, 1987, 15 (03) :1269-1292
[4]  
Grubel R., 1988, METRIKA, V35, P49
[5]   Improved feasible solution algorithms for high breakdown estimation [J].
Hawkins, DM ;
Olive, DJ .
COMPUTATIONAL STATISTICS & DATA ANALYSIS, 1999, 30 (01) :1-11
[6]   THE FEASIBLE SOLUTION ALGORITHM FOR THE MINIMUM COVARIANCE DETERMINANT ESTIMATOR IN MULTIVARIATE DATA [J].
HAWKINS, DM .
COMPUTATIONAL STATISTICS & DATA ANALYSIS, 1994, 17 (02) :197-210
[7]  
Horn R. A., 1986, Matrix analysis
[8]   Identification of outliers in multivariate data [J].
Rocke, DM ;
Woodruff, DL .
JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1996, 91 (435) :1047-1061
[9]   A fast algorithm for the minimum covariance determinant estimator [J].
Rousseeuw, PJ ;
Van Driessen, K .
TECHNOMETRICS, 1999, 41 (03) :212-223
[10]   LEAST MEDIAN OF SQUARES REGRESSION [J].
ROUSSEEUW, PJ .
JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1984, 79 (388) :871-880
12