The complexity of computing the MCD-estimator

Publication: Research - peer-reviewJournal article – Annual report year: 2004

View graph of relations

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.
Original languageEnglish
JournalTheoretical Computer Science
Publication date2004
Volume326
Issue1-3
Pages383-398
ISSN0304-3975
DOIs
StatePublished
CitationsWeb of Science® Times Cited: 9
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 2751301