Least Absolute Deviations, 1983
Theory, Applications and Algorithms
Progress in Probability Series, Vol. 6

Least squares is probably the best known method for fitting linear models and by far the most widely used. Surprisingly, the discrete L 1 analogue, least absolute deviations (LAD) seems to have been considered first. Possibly the LAD criterion was forced into the background because of the com­ putational difficulties associated with it. Recently there has been a resurgence of interest in LAD. It was spurred on by work that has resulted in efficient al­ gorithms for obtaining LAD fits. Another stimulus came from robust statistics. LAD estimates resist undue effects from a feyv, large errors. Therefore. in addition to being robust, they also make good starting points for other iterative, robust procedures. The LAD criterion has great utility. LAD fits are optimal for linear regressions where the errors are double exponential. However they also have excellent properties well outside this narrow context. In addition they are useful in other linear situations such as time series and multivariate data analysis. Finally, LAD fitting embodies a set of ideas that is important in linear optimization theory and numerical analysis. viii PREFACE In this monograph we will present a unified treatment of the role of LAD techniques in several domains. Some of the material has appeared in recent journal papers and some of it is new. This presentation is organized in the following way. There are three parts, one for Theory, one for Applicatior.s and one for Algorithms.

1. Generalities.- 1.1 Introduction.- 1.2 Historical Background.- 1.3 Some Mathematical Background.- 1.4 Notes.- 2. LAD in Linear Regression.- 2.1 Introduction.- 2.2 Some Statistical Properties of LAD Estimators.- 2.3 Robustness of LAD: Breakdown and Influence.- 2.4 LAD in M and R-Estimation.- 2.5 Sampling Behavior of LAD.- 2.6 Notes.- 3. LAD in Autoregression.- 3.1 Introduction.- 3.2 Behavior of LAD in Autoregressions.- 3.3 Sampling Behavior of LAD.- 3.4 Notes.- 4. LAD in Multi-Way Tables.- 4.1 One-way layout.- 4.2 Two-way layout.- 4.3 Properties of LAD estimates.- 4.4 LAD and Median Polish.- 4.5 Nonuniqueness of “row-pius-column” fits.- 4.6 Notes.- 5. LAD Spline Fitting.- 5.1 Spline Functions.- 5.2 Conditional and Local Quantiles.- 5.3 Quantile Splines.- 5.4 Examples.- 5.5 Notes.- 6. LAD and Linear Programming.- 6.1 Introduction and Background.- 6.2 LP is LAD is LP.- 6.3 Some Complexity Questions.- 6.4 Dense LP Problems as LAD Fits.- 6.5 Notes.- 7. Algorithms for LAD.- 7.1 Introduction and Background.- 7.2 Three Special Purpose LAD Algorithms.- 7.2.1 The Barrodale-Roberts Algorithm.- 7.2.2 The Bartels-Conn-Sinclair Algorithm.- 7.2.3 The Bloomfield-Steiger Algorithm.- 7.2.4 Summary.- 7.3 The Three Algorithms Compared.- 7.4 Slightly Overdetermined Equation Systems.- 7.5 Other Methods.- 7.6 Notes.- 8. Appendix.- Index of Names.- Index of Subjects.