IDEAS home Printed from https://ideas.repec.org/a/eee/csdana/v99y2016icp148-170.html
   My bibliography  Save this article

A practical approximation algorithm for the LTS estimator

Author

Listed:
  • Mount, David M.
  • Netanyahu, Nathan S.
  • Piatko, Christine D.
  • Wu, Angela Y.
  • Silverman, Ruth

Abstract

The linear least trimmed squares (LTS) estimator is a statistical technique for fitting a linear model to a set of points. It was proposed by Rousseeuw as a robust alternative to the classical least squares estimator. Given a set of n points in Rd, the objective is to minimize the sum of the smallest 50% squared residuals (or more generally any given fraction). There exist practical heuristics for computing the linear LTS estimator, but they provide no guarantees on the accuracy of the final result. Two results are presented. First, a measure of the numerical condition of a set of points is introduced. Based on this measure, a probabilistic analysis of the accuracy of the best LTS fit resulting from a set of random elemental fits is presented. This analysis shows that as the condition of the point set improves, the accuracy of the resulting fit also increases. Second, a new approximation algorithm for LTS, called Adaptive-LTS, is described. Given bounds on the minimum and maximum slope coefficients, this algorithm returns an approximation to the optimal LTS fit whose slope coefficients lie within the given bounds. Empirical evidence of this algorithm’s efficiency and effectiveness is provided for a variety of data sets.

Suggested Citation

  • Mount, David M. & Netanyahu, Nathan S. & Piatko, Christine D. & Wu, Angela Y. & Silverman, Ruth, 2016. "A practical approximation algorithm for the LTS estimator," Computational Statistics & Data Analysis, Elsevier, vol. 99(C), pages 148-170.
    • Handle: RePEc:eee:csdana:v:99:y:2016:i:c:p:148-170
    DOI: 10.1016/j.csda.2016.01.016
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0167947316300020
    Download Restriction: Full text for ScienceDirect subscribers only.
    File URL: https://libkey.io/10.1016/j.csda.2016.01.016?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Hawkins, Douglas M., 1994. "The feasible solution algorithm for least trimmed squares regression," Computational Statistics & Data Analysis, Elsevier, vol. 17(2), pages 185-196, February.
    2. Torti, Francesca & Perrotta, Domenico & Atkinson, Anthony C. & Riani, Marco, 2012. "Benchmark testing of algorithms for very robust regression: FS, LMS and LTS," Computational Statistics & Data Analysis, Elsevier, vol. 56(8), pages 2501-2512.
    3. Mount, David M. & Netanyahu, Nathan S. & Romanik, Kathleen & Silverman, Ruth & Wu, Angela Y., 2007. "A practical approximation algorithm for the LMS line estimator," Computational Statistics & Data Analysis, Elsevier, vol. 51(5), pages 2461-2486, February.
    4. Hofmann, Marc & Kontoghiorghes, Erricos John, 2010. "Matrix strategies for computing the least trimmed squares estimation of the general linear and SUR models," Computational Statistics & Data Analysis, Elsevier, vol. 54(12), pages 3392-3403, December.
    5. Rousseeuw, Peter J., 1991. "A diagnostic plot for regression outliers and leverage points," Computational Statistics & Data Analysis, Elsevier, vol. 11(1), pages 127-129, January.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Flores, Salvador, 2015. "SOCP relaxation bounds for the optimal subset selection problem applied to robust linear regression," European Journal of Operational Research, Elsevier, vol. 246(1), pages 44-50.
    2. Klouda, Karel, 2015. "An exact polynomial time algorithm for computing the least trimmed squares estimate," Computational Statistics & Data Analysis, Elsevier, vol. 84(C), pages 27-40.
    3. Maria Teresa Alonso & Carlo Ferigato & Deimos Ibanez Segura & Domenico Perrotta & Adria Rovira-Garcia & Emmanuele Sordini, 2021. "Analysis of ‘Pre-Fit’ Datasets of gLAB by Robust Statistical Techniques," Stats, MDPI, vol. 4(2), pages 1-19, May.
    4. Arismendi, Juan C. & Broda, Simon, 2017. "Multivariate elliptical truncated moments," Journal of Multivariate Analysis, Elsevier, vol. 157(C), pages 29-44.
    5. Selin Ahipaşaoğlu, 2015. "Fast algorithms for the minimum volume estimator," Journal of Global Optimization, Springer, vol. 62(2), pages 351-370, June.
    6. G. Zioutas & L. Pitsoulis & A. Avramidis, 2009. "Quadratic mixed integer programming and support vectors for deleting outliers in robust regression," Annals of Operations Research, Springer, vol. 166(1), pages 339-353, February.
    7. Roozbeh, Mahdi, 2016. "Robust ridge estimator in restricted semiparametric regression models," Journal of Multivariate Analysis, Elsevier, vol. 147(C), pages 127-144.
    8. Eugster, Manuel J.A. & Leisch, Friedrich & Strobl, Carolin, 2014. "(Psycho-)analysis of benchmark experiments: A formal framework for investigating the relationship between data sets and learning algorithms," Computational Statistics & Data Analysis, Elsevier, vol. 71(C), pages 986-1000.
    9. Baishuai Zuo & Chuancun Yin & Jing Yao, 2023. "Multivariate range Value-at-Risk and covariance risk measures for elliptical and log-elliptical distributions," Papers 2305.09097, arXiv.org.
    10. Baishuai Zuo & Chuancun Yin, 2022. "Multivariate doubly truncated moments for generalized skew-elliptical distributions with application to multivariate tail conditional risk measures," Papers 2203.00839, arXiv.org.
    11. Sven Jäger & Anita Schöbel, 2020. "The blockwise coordinate descent method for integer programs," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 91(2), pages 357-381, April.
    12. Marco Cattaneo & Andrea Wiencierz, 2014. "On the implementation of LIR: the case of simple linear regression with interval data," Computational Statistics, Springer, vol. 29(3), pages 743-767, June.
    13. Greco, Luca & Pacillo, Simona & Maresca, Piera, 2023. "An impartial trimming algorithm for robust circle fitting," Computational Statistics & Data Analysis, Elsevier, vol. 181(C).
    14. Annalivia Polselli, 2023. "Influence Analysis with Panel Data," Papers 2312.05700, arXiv.org.
    15. Hawkins, Douglas M. & Olive, David, 1999. "Applications and algorithms for least trimmed sum of absolute deviations regression," Computational Statistics & Data Analysis, Elsevier, vol. 32(2), pages 119-134, December.
    16. Hawkins, Douglas M., 1995. "Convergence of the feasible solution algorithm for least median of squares regression," Computational Statistics & Data Analysis, Elsevier, vol. 19(5), pages 519-538, May.
    17. Atkinson, A. C. & Cheng, Tsung-Chi, 2000. "On robust linear regression with incomplete data," Computational Statistics & Data Analysis, Elsevier, vol. 33(4), pages 361-380, June.
    18. Jung, Kang-Mo, 2005. "Multivariate least-trimmed squares regression estimator," Computational Statistics & Data Analysis, Elsevier, vol. 48(2), pages 307-316, February.
    19. Christian Garciga & Randal J. Verbrugge, 2020. "A New Tool for Robust Estimation and Identification of Unusual Data Points," Working Papers 20-08, Federal Reserve Bank of Cleveland.
    20. Garciga, Christian & Verbrugge, Randal, 2021. "Robust covariance matrix estimation and identification of unusual data points: New tools," Research in Economics, Elsevier, vol. 75(2), pages 176-202.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:csdana:v:99:y:2016:i:c:p:148-170. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/csda .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.