Transcription of The Levenberg-Marquardt Algorithm
1 TheLevenberg-MarquardtAlgorithmAnanthRan ganathan8thJune20041 IntroductionTheLevenberg-Marquardt(LM) rstshowntobea , anotherperspective onthealgorithmis providedbyconsideringit asa solutionis calledNonlinearLeastSquaresMinimization. Thisimpliesthatthefunctiontobeminimizedi s ofthefollowingspecialform:f x 12m j 1r2j x wherex x1 x2 xn is a vector, andeachrjis a functionfrom nto . Therjarereferredtoasaresidualsandit is assumedthatm make matterseasier,fis representedasaresidualvectorr: n mde nedbyr x r1 x r2 x rm x Now,fcanberewrittenasf x 12 r x 2. nedasJ x rj xi, 1 j m, 1 i rstconsiderthelinearcasewhereeveryrifunc tionislinear. Here,theJacobianisconstantandwecanrepres entrasa hyperplanethroughspace,sothatfis givenbythequadraticf x 12 Jx r 0 2. We alsoget f x JT Jx r and 2f x JTJ. Solvingforthemin-imumbysetting f x 0 , weobtainxmin JTJ 1 JTr, whichis ,non-linearcase,wehave f x m j 1rj x rj x J x Tr x (1) 2f x J x TJ x m j 1rj x 2rj x (2)Thedistinctive propertyofleast-squaresproblemsisthatgiv entheJacobianmatrixJ, wecanessentiallygettheHessian( 2f x ) forfreeifit ispossibletoapproximatetherjs bylinearfunctions( 2rj x aresmall)ortheresiduals(rj x ) 2f x J x TJ x (3)whichis oneofnear-linearityoftheris nearthesolutionsothat 2rj x is alsoimportanttonotethat(3)is onlyvalidif ,andconsequently,theperformanceofthealgo rithmspresentedinthisdocumentis blendofGradientdescentandGauss-Newtonite ra-tionVanillagradientdescentisthesimple st,mostintuitive techniqueto ndminimaina performedbyaddingthenegative ofthescaledgradientat eachstep, 1 xi l f(4)
2 , wewouldliketotake largestepsdownthegradientatlocationswher ethegradientis small(theslopeis gentle)andconversely, take smallstepswhenthegradientis large, updaterule, ,if thereis a longandnarrowvalley intheerrorsurface,thecomponentofthegradi entinthedirectionthatpointsalongthebaseo fthevalley is verysmallwhilethecomponentalongthevalley wallsis tomove a longdistancealongthebaseanda , dothisis touseNewton's methodto solve theequation f x Taylorseriesaroundthecurrentstatex0, weget f x f x0 x x0 T 2f x0 higherordertermsof x x0 (5)Ifweneglectthehigherorderterms(assumi ngftobequadraticaroundx0), andsolve fortheminimumxbysettingthelefthandsideof (5)to0, wegettheupdateruleforNewton's method-xi 1 xi 2f xi ! 1 f xi (6)2wherex0hasbeenreplacedbyxiandxbyxi 's methodimplicitlyusesa quadraticassumptiononf(arisingfromtheneg lectofhigherordertermsin a Taylorseriesexpansionoff) , (3) , therateofconvergenceis sensitive tothestartinglocation(ormoreprecisely,th elinearityaroundthestartinglocation).
3 It canbeseenthatsimplegradientdescentandGau ss-Newtoniterationarecomplementaryinthea dvantagesthey proposedanalgorithmbasedonthisobservatio n,whoseupdateruleis a blendoftheabove mentionedalgorithmsandis givenasxi 1 xi H lI 1 f xi (7)whereHistheHessianmatrixevaluatedatxi . Thisupdateruleis ,it impliesthatourquadraticassumptiononf x is workingandwereducel(usuallybya factorof10)toreducethein ,if theerrorgoesup,wewouldlike tofollow thegradientmoreandsolis increasedbythesamefactor. TheLevenberg algorithmis thenew theerrorhasincreasedasa resulttheupdate,thenretractthestep( )andincreaselbya factorof10orsomesuchsigni cantfactor. Thengoto(1) theerrorhasdecreasedasa resultoftheupdate,thenacceptthestep( theirnew values)anddecreaselbya algorithmhasthedisadvantagethatif thevalueoflislarge,thecalculatedHessianm atrixis notusedat canderive someadvantageoutofthesecondderivative errorvalley problemdoesnotoccurany (7) 1 xi H ldiag"H#$ 1 f xi (8)SincetheHessianis proportionaltothecurvatureoff, (8)impliesa largestepinthedirectionwithlow curvature( ,analmost atterrain)anda bigstepinthedirectionwithhighcurvature( ,asteepincline).
4 It is tobenotedthatwhiletheLMmethodis innowayoptimalbutis justa heuristic,it worksextremelywellin aw is usuallyimplementedusingcleverpseudo-inve rsemethodssuchassingularvaluedecompositi on,thecostoftheupdatebecomesprohibitive afterthemodelsizeincreasestoa few (ofa few hundredparameters)however,thismethodismu chfasterthansay, trust-regionalgorithmHistorically, theLMalgorithmwaspresentedbyMarquardtasg ivenintheprevioussectionwheretheparamete r,l, wasmanipulateddirectlyto , a fundamentallydifferentmannerthanthosepre sentedintheprevioussection, linesearchmethod,wedecideonadirectioninw hichtodescendthegradientandarethenconcer nedaboutthestepsize, thedirectionofdescent,andakthestepsize,t henourstepis givenbyx%k 1& x%k& akp%k&andthestepsizeis obtainedbysolvingthesub-problemminf'x%k& akp%k&)(+*ak,0 Bycontrast,ina trust-regionalgorithmwebuilda modelm%k&thatapproximatesthefunctionfina niteregionnearx%k&.
5 Thisregion,D, wherethemodelis a goodapproximationoff, is at mostoftena quadraticobtainedbya Taylorseriesexpansionoffaroundx%k&, f'x%k&)( f'x%k&)(.-p 12pTH p(9)whereHis theHessian(oranapproximationoftheHessian ) ndthesteptotake duringtheiterationismin/p/10Df'x%k&( f'x%k&(-p 12pTH p(10)andtheiterationstepitselfisx%k 1& x%k& p. A trust-regionalgorithmcanthusbeconceivedo fasa sequenceofiterations,ineachofwhichwemode lthefunctionfbya (10)is givenbya theoremwhichis asfollows-p2is a globalsolutionofmin/p/43Df'x%k&( f'x%k&(-p 12pTH piff p2 Dandthereis a : H lI p2 g(11)l D p2 5 0(12)and H lI is positive semi-de nitewhereg f6 canbeseenthat(11)is thesameas(7).(12)basicallystatesthatif p2 87 Dthenlis 0 ,wereachthesameparameterupdateequationfo rtheLMalgorithmusingatrust-regionframewo rkasweobtainedusingtheline-searchmethodT heheuristictoupdatethesizeofthetrust-reg ionusuallydependsontheratiooftheexpected changeinftothepredictedchange, f'w%k&( f'w%k& p2(f w%k&!))))))
6 M%k& p2 (13)If thereis a goodagreementbetweenpredictedandactualva lues(rk91),thenDis increased;iftheagreementis poor(rkis small),thenrkis smallerthana thresholdvalue(:10 4), thestepis rejectedandthevalueofwkis retainedbutDis ,thealgorithmis similartotheoneinSection3 butthevaluethatis [Levenberg44] , Amethodforthesolutionofcertainproblemsin leastsquares, , 1944, , 168.[Marquardt63] , Analgorithmforleast-squaresestimationofn onlinearparameters, SIAMJ. , 1963, , 441.[Nocedal99]J. , NumericalOptimization, Springer, New York.
