SpringerBriefs in Statistics For furthervolumes: http://www.springer.com/series/8921 Richard William Farebrother L -Norm and 1 L -Norm Estimation ? An Introduction to the Least Absolute Residuals, the Minimax Absolute Residual and Related Fitting Procedures 123 Richard William Farebrother The Universityof Manchester Manchester UK ISSN 2191-544X ISSN 2191-5458 (electronic) ISBN 978-3-642-36299-6 ISBN 978-3-642-36300-9 (eBook) DOI 10.1007/978-3-642-36300-9 SpringerHeidelbergNewYorkDordrechtLondon LibraryofCongressControlNumber:2013933582 (cid:2)TheAuthor(s)2013 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionor informationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purposeofbeingenteredandexecutedonacomputersystem,forexclusiveusebythepurchaserofthe work. Duplication of this publication or parts thereof is permitted only under the provisions of theCopyright Law of the Publisher’s location, in its current version, and permission for use must always be obtained from Springer. Permissions for use may be obtained through RightsLink at the CopyrightClearanceCenter.ViolationsareliabletoprosecutionundertherespectiveCopyrightLaw. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexempt fromtherelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Point Fitting Problems in One and Two Dimensions . . . . . . . . . . . 5 2.1 Point Fitting Problems in One Dimension. . . . . . . . . . . . . . . . . 5 2.2 Point Fitting Problems in Two Dimensions. . . . . . . . . . . . . . . . 7 2.3 Truncated Point Fitting Problems in Two Dimensions . . . . . . . . 8 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 The Hyperplane Fitting Problem in Two or More Dimensions. . . . 11 3.1 Line Fitting Problems in Two Dimensions . . . . . . . . . . . . . . . . 11 3.2 Hyperplane Fitting Problems in Higher Dimensions. . . . . . . . . . 12 3.3 Matrix Representation of the Problem . . . . . . . . . . . . . . . . . . . 13 3.4 The Weighted L -Norm and L -Norm Fitting Problems . . . . . . 14 1 1 3.5 Relation to the L -Norm Fitting Problem . . . . . . . . . . . . . . . . . 18 2 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4 Linear Programming Computations . . . . . . . . . . . . . . . . . . . . . . . 21 4.1 Regular and Projective Geometry Solutions of the L -Norm Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1 4.2 Projective Geometry Solution of the L -Norm Problem. . . . . . . 23 ? 4.3 Linear Programming Computations . . . . . . . . . . . . . . . . . . . . . 23 4.4 A Hypothetical General Procedure. . . . . . . . . . . . . . . . . . . . . . 24 4.5 Non-Uniqueness of the Solution . . . . . . . . . . . . . . . . . . . . . . . 25 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5 Statistical Theory. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.1 Linear Statistical Model. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.2 Maximum Likelihood Estimation. . . . . . . . . . . . . . . . . . . . . . . 32 5.3 Asymptotic Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 v vi Contents 5.4 Pseudo-Unbiased Weighted L -Norm Procedures. . . . . . . . . . . . 34 1 5.5 Pseudo-Unbiased Weighted L -Norm Procedures. . . . . . . . . . . 35 ? References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6 The Least Median of Squared Residuals Procedure. . . . . . . . . . . . 37 6.1 Robustness to Outliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.2 Gauss’s Optimality Conditions . . . . . . . . . . . . . . . . . . . . . . . . 38 6.3 Least Median of Squares Computations . . . . . . . . . . . . . . . . . . 38 6.4 Minimum Volume Ellipsoid . . . . . . . . . . . . . . . . . . . . . . . . . . 39 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 7 Mechanical Representations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 7.2 Fitting a Point to a Set of Points in the Plane of Observations: Fermat’s Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 7.3 Fitting a Line to a Set of Points in the Plane of Observations: Boscovich’s Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 7.4 Fitting a Point to a Set of Lines in the Plane of Parameters: L -Norm Variants of Donkin’s Problem. . . . . . . . . . . . . . . . . . 48 1 7.5 Fitting a Point to a Set of Lines in the Plane of Observations: Oja’s Bivariate Median . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 7.6 L -Norm Mechanical Models . . . . . . . . . . . . . . . . . . . . . . . . . 52 2 7.7 L -Norm and LMS Mechanical Models. . . . . . . . . . . . . . . . . . 54 ? References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Chapter 1 Introduction Abstract Thismonographprovidesanintroductiontoaclassoflinearfittingpro- cedures that employ the sum of the absolute residuals (or L -norm), the minimax 1 absoluteresidual(orL∞-norm)andthemediansquaredresidualasoptimalitycrite- riainthecontextofthestandardlinearstatisticalmodel.Theleastabsoluteresiduals procedurewasproposedbyBoscovichin1757andagainin1760anddiscussedby Laplace, Gauss and Edgeworth; the least squares procedure was probably used by Gaussin1794or1795butfirstproposedinprintbyLegendrein1805beforebeing discussedbyGauss,Laplaceandmanyotherleadingscientists;finally,theminimax absoluteresidualprocedurewasproposedbyLaplacein1786,1793and1799before being discussed by Cauchy, Fourier, Chebyshev and others. The least squares and leastabsoluteresidualsproceduresarewidelyusedinstatisticalapplicationsbutthe minimaxprocedure hadreceived littlesupportinthisareauntilavariant,theleast medianofsquaresprocedure,wasproposedbyRousseeuwin1984.Almostbydef- inition, this last procedure is more robust to the presence of outlying observations thanaretheothertwofittingprocedures. · Keywords Rogerius Josephus Boscovich (1711–1787) Carl Friedrich Gauss · (1777–1855) Pierre-SimonLaplace(1749–1827) Theyears2010and2011respectivelymarkthe250thanniversaryofBoscovich’s constrained variant of the least sum of absolute residuals or L -norm line fitting 1 procedureandthe225thanniversaryofLaplace’sunconstrainedminimaxabsolute residualorL∞-normlinefittingprocedure.Itthereforeseemsappropriatetocelebrate thisdoubleanniversarybytakingtheopportunityofdrawingthecloserelationship betweenthesetwofittingprocedurestotheattentionofawideraudience. Some practitioners might argue that, whilst the L -norm fitting procedure may 1 have a peripheral role in statistics, the use of the L∞-norm criterion (sometimes named for Chebyshev) is properly restricted to the fields of approximation theory andgametheory.Butthisisnotthecase,as,inChap.6,weshalldefineavariantof theL∞-normprocedure,knownastheLeastMedianofSquaresorLMSprocedure, whichincorporatesthehigh-breakdownfeatureoftheL -normprocedureandplays 1 R.W.Farebrother,L1-NormandL∞-NormEstimation, 1 SpringerBriefsinStatistics,DOI:10.1007/978-3-642-36300-9_1, ©TheAuthor(s)2013 2 1 Introduction anincreasinglysignificantroleinthefieldofrobuststatisticalanalysis.Forfurther details of this and other robust fitting procedures, see the relevant articles in the volumeseditedbyDodge(1987,1992,1997,2002). Theauthorhaspublishedthreebooks,twoofwhichrelatetoaspectsofthesubject coveredbythisbrief.Inhisfirstbook,Farebrother(1988a)wasconcernedwithcom- putationalaspectsoftheleastsumofsquaredresidualsorL -normfittingprocedure 2 andisthusoflittleimmediateinteresttoreadersofthepresentbrief. Inhissecondbook,Farebrother1999givesadetailedaccountofthehistory(to 1930)oftheL1-norm,L2-normandL∞-normfittingprocedures.Weshalltherefore not address this topic in this brief but shall refer interested readers to the relevant chaptersofFarebrother(1999)ortothealternativetextspublishedbyHald(1998)and Stigler(1986)formoredetailedaccountsofthisfacetofthehistoryofthecalculus ofobservations.ReadersmayalsoliketoconsultHeydeandSeneta(2001)forbrief accountsofthelivesofBoscovich,Chebychev,Edgeworth,GaussandLaplaceand Stigler(1999)forrelatedmaterial. Similarly, in his third book, Farebrother (2002) has given a fairly detailed accountofthevariousgeometricalandmechanicalmodelsoftheL -norm,L -norm, 1 2 L∞-normandLMSfittingprocedures.OuraccountofmechanicalmodelsinChap.7 of this brief is therefore restricted to a summary of models of four variants of the L -norm fitting procedure supplemented by brief notes on two variants of the 1 L2 -normand L∞-normfittingprocedures. Finally, we note that, in a conventional textbook, algebraic expressions of the typediscussedinthisbriefareusuallyillustratedbymeansofgraphicalfiguresor diagrams but, unfortunately, the author has been blind for some twenty years and isthusnotabletousetherelevantgraphicalsoftware,so,perforce,readerswillbe obligedtofollowLaplace’sprescriptionbyabstainingfromtheuseofdiagramswhen studyingthesefittingprocedures.Alternatively,theymayprefertoreadthepresent briefinconjunctionwiththerelevantillustrationsfromFarebrother(2002). References Dodge, Y. (Ed.). (1987). Statisticaldata analysis based on the L1-Norm and RelatedMethods. Amsterdam:North-HollandPublishingCompany. Dodge,Y.(Ed.).(1992).L1-Statisticalanalysisandrelatedmethods.Amsterdam:North-Holland PublishingCompany. Dodge,Y.(Ed.).(1997).L1-Statisticalproceduresandrelatedtopics.Hayward:InstituteofMath- ematicalStatistics. Dodge, Y. (Ed.). (2002). Statisticaldata analysis based on the L1-Norm and RelatedMethods. Basel:BirkhäuserPublishing. Farebrother,R.W.(1988a).Linearleastsquarescomputations.NewYork:MarcelDekker. Farebrother,R.W.(1999).Fittinglinearrelationships:Ahistoryofthecalculusofobservations 1750–1900.NewYork:Springer. Farebrother,R.W.(2002).Visualizingstatisticalmodelsandconcepts.NewYork:MarcelDekker. AvailableonlinefromTaylorandFrancis.com. Hald,A.(1998).Ahistoryofmathematicalstatistics1750–1930.NewYork:Wiley. References 3 Heyde, C. C., & Seneta, E. (Eds.). (2001). Statisticians of the centuries. Springer: New York. ReprintedbyStatProb.comin2010. Stigler, S. M. (1986). The history of statistics: The measurement of uncertainty before 1900. Cambridge:HarvardUniversityPress. Stigler, S. M. (1999). Statistics on the table: The history of statistical concepts and methods. Cambridge:HarvardUniversityPress. Chapter 2 Point Fitting Problems in One and Two Dimensions Abstract We begin our analysis by considering the fitting of a single point to a number of point observations in one-dimensional space. Using the L -norm as t optimality criterion with t = 1, t = 2 or t = ∞, we obtain the median, mean and midrange of a set of observations respectively. Similarly, applying the same three optimality criteria in the two-dimensional case, we obtain the mediancentre or centre of population, the centroid or centre of gravity and the unnamed centre ofthecircleofsmallestradiusrespectively.Moreover,ifweomitsomeofthemore extremeobservationsthenweobtaintruncatedvariantsoftheseprocedures.Asnoted inChap.7,themidrangeanditsgeneralisationsmaybeassociatedwithasetofmore or less familiar geometrical instruments: The univariate midrange with a pair of callipers,thebivariatemidrangewithapairofcompassesandtheminimaxfittedline ofChap.3withapairofparallelrules. · · · · Keywords Centre of gravity Centre of population Centroid L -norm · · · · · 1 · L2-norm L∞·-norm Linear progra·mming Mean Median Midrange Mediancentre Oja’sbivariatemedian Truncatedmidrange 2.1 PointFittingProblemsinOneDimension Lety , y , ..., y representasetofnobservationsonasinglevariableY,thenthese 1 2 n nobservationsmayberepresentedbythenpointsat y = y , y = y , ..., y = y 1 2 n onthe y-axisofaCartesiandiagram.Moreover,wemayidentifyapointofbestfit tothesenpointsbychoosingavalueforainsuchawaythatthesumofthesquared distances (cid:2)n (y −a)2 i i=1 isminimised. R.W.Farebrother,L1-NormandL∞-NormEstimation, 5 SpringerBriefsinStatistics,DOI:10.1007/978-3-642-36300-9_2, ©TheAuthor(s)2013