Please use this identifier to cite or link to this item:
Title: An exact least trimmed squares algorithm for a range of coverage values
Authors: Hofmann, Marc H. 
Gatu, Cristian 
Kontoghiorghes, Erricos John 
Keywords: Outliers (Statistics);Algorithms
Issue Date: 2010
Publisher: Taylor & Francis Online
Source: Journal of Computational and Graphical Statistics, 2010, Volume 19, Issue 1, Pages 191-204
Abstract: A new algorithm to solve exact least trimmed squares (LTS) regression is presented. The adding row algorithm (ARA) extends existing methods that compute the LTS estimator for a given coverage. It employs a tree-based strategy to compute a set of LTS regressors for a range of coverage values. Thus, prior knowledge of the optimal coverage is not required. New nodes in the regression tree are generated by updating the QR decomposition of the data matrix after adding one observation to the regression model. The ARA is enhanced by employing a branch and bound strategy. The branch and bound algorithm is an exhaustive algorithm that uses a cutting test to prune nonoptimal subtrees. It significantly improves over the ARA in computational performance. Observation preordering throughout the traversal of the regression tree is investigated. A computationally efficient and numerically stable calculation of the bounds using Givens rotations is designed around the QR decomposition, avoiding the need to explicitly update the triangular factor when an observation is added. This reduces the overall computational load of the preordering device by approximately half. A solution is proposed to allow preordering when the model is underdetermined. It employs pseudo-orthogonal rotations to downdate the QR decomposition. The strategies are illustrated by example. Experimental results confirm the computational efficiency of the proposed algorithms. Supplemental materials (R package and formal proofs) are available online
ISSN: 1061-8600 (print)
1537-2715 (online)
DOI: 10.1198/jcgs.2009.07091
Rights: © 2010 American Statistical Association.
Type: Article
Appears in Collections:Άρθρα/Articles

Show full item record


checked on Apr 28, 2018

Citations 50

checked on Jul 30, 2019

Page view(s) 50

Last Week
Last month
checked on Aug 23, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.