The gaussian hare and the laplacian tortoise: Computability of squared-error versus absolute-error estimators

Stephen Portnoy, Roger Koenker

Research output: Contribution to journalArticlepeer-review

Abstract

Since the time of Gauss, it has been generally accepted that ℓ2-methods of combining observations by minimizing sums of squared errors have significant computational advantages over earlier ℓ1-methods based on minimization of absolute errors advocated by Boscovich, Laplace and others. However, ℓ1-methods are known to have signifi- cant robustness advantages over ℓ2-methods in many applications, and related quantile regression methods provide a useful, complementary approach to classical least-squares estimation of statistical models. Combining recent advances in interior point methods for solving linear programs with a new statistical preprocessing approach for ℓ1-type problems, we obtain a 10- to 100-fold improvement in computational speeds over current (simplex-based) ℓ1-algorithms in large problems, demonstrating that ℓ1-methods can be made competitive with ℓ2-methods in terms of computational speed throughout the entire range of problem sizes. Formal complexity results suggest that ℓ1-regression can be made faster than least-squares regression for n sufficiently large and p modest.

Original languageEnglish (US)
Pages (from-to)279-296
Number of pages18
JournalStatistical Science
Volume12
Issue number4
DOIs
StatePublished - 1997

Keywords

  • Interior point
  • L
  • Least absolute deviations
  • Linear programming
  • Median
  • Regression quantiles
  • Simplex method
  • Simultaneous confidence bands
  • Statistical preprocessing

ASJC Scopus subject areas

  • Statistics and Probability
  • Mathematics(all)
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'The gaussian hare and the laplacian tortoise: Computability of squared-error versus absolute-error estimators'. Together they form a unique fingerprint.

Cite this