`ScottC.Douglasy
`DepartmentofElectricalEngineering
`UniversityofUtah
`SaltLakeCity,Utah
`Abstract{Inthisletter,aderivationofthenormalizedLMSalgorithmisgeneralized,
`resultinginafamilyofprojection-likealgorithmsbaseduponanLp-minimized(cid:12)lter
`coe(cid:14)cientchange.Theresultingalgorithmsincludethesimpli(cid:12)edNLMSalgorithmof
`NagumoandNodaandanevensimplersingle-coe(cid:14)cientupdatealgorithmbasedupon
`themaximumabsolutevaluedatumoftheinputdatavector.Acompletederivationof
`thealgorithmfamilyisgiven,andsimulationsareperformedtoshowtheconvergence
`behaviorsofthealgorithms.
`IEEESIGNALPROCESSINGLETTERS
`vol.SPL- ,no. ,pp. - ,March .
`EDICSCategoryNo.SPL..
`(cid:3)ThisresearchwassupportedinpartbySRIInternational.
`yPleaseaddresscorrespondenceto:ScottC.Douglas,DepartmentofElectricalEngineering,MerrillEngi-
`neeringBuilding,UniversityofUtah,SaltLakeCity,UT .( ) -.FAX:( ) - .Electronic
`mailaddress:douglas@ee.utah.edu.
` PermissionoftheIEEEtopublishthisabstractseparatelyisgranted.
`
`Petitioner Apple Inc.
`Ex. 1008, Cover
`
`
`
` Summary
`Thenormalizedleast-mean-square(NLMS)algorithm,alsoknownastheprojectionalgorithm
`[ ],isausefulmethodforadaptingthecoe(cid:14)cientsofa(cid:12)nite-impulse-response(FIR)(cid:12)lterfora
`numberofsignalprocessingandcontrolapplications.TheNLMSupdateisgivenby
`Wk+ =Wk+(cid:22)ekXk
`LXm= xm;k;
`( )
`whereWk=[w ;k(cid:1)(cid:1)(cid:1)wL;k]Tarethecoe(cid:14)cientsoftheadaptive(cid:12)lterattimek,Xk=[x ;k(cid:1)(cid:1)(cid:1)xL;k]T
`aretheLsamplesoftheinputdatain(cid:12)ltermemoryattimek,ek=dk(cid:0)WTkXkistheerrorbetween
`theadaptive(cid:12)lteroutputandthedesiredsignaldk,and(cid:22)isauser-speci(cid:12)edconvergenceparam-
`eter.Thisalgorithmhastwodistinctadvantagesovertheleast-mean-square(LMS)algorithm: )
`potentially-fasterconvergencespeedsforbothcorrelatedandwhitenedinputdata[, ,],and
`)stablebehaviorforaknownrangeofparametervalues( <(cid:22)<),independentoftheinput
`datacorrelationstatistics[ ,].TheNLMSalgorithmrequiresaminimumofoneadditionalmul-
`tiply,divideandadditionovertheLMSalgorithmtoimplementforshift-inputdata.Evenso,the
`multipliesrequiredforthealgorithmupdatemaystillbeprohibitiveincertainhigh-data-rateappli-
`cations.Inthesesituations,itisusefultodeterminemodi(cid:12)edversionsoftheNLMSalgorithmthat
`retainthefastconvergencepropertiesofthealgorithmwhilereducingtheamountofcomputation
`periteration.Onesuchmodi(cid:12)edalgorithm,(cid:12)rstsuggestedbyNagumoandNoda[],is
`Wk+ =Wk+(cid:22)eksgn(Xk)
`LXm= jxm;kj:
`()
`Thisupdateissimilartothatin( )butallowsnonlinearmodi(cid:12)cationofthedatavectorelements.
`Inthisletter,wederiveageneralizedclassofnormalizedLMSalgorithmsoftheform
`( )
`Wk+ =Wk+(cid:22)ekFq(Xk)
`[Fq(Xk)]i=>>>>><>>>>>:jxi;kjq(cid:0) sgn(xi;k)
`if (cid:20)q<
`LXm= jxm;kjq
`()
` xn;k(cid:14)i(cid:0)n
`ifq= ,
`where[Fq((cid:1))]idenotestheithelementofthevector-valuedfunctionFq((cid:1)),(cid:14)jistheKronnecker
`deltafunction,andnisanyoneintegerforwhichjxn;kj=max (cid:20)j(cid:20)Ljxj;kj.Forq=,thisupdate
`
`
`Petitioner Apple Inc.
`Ex. 1008, p. 1
`
`
`
`reducestothatoftheNLMSalgorithmin( ),andforq= ,thisupdatereducestothealgorithm
`ofNagumoandNodagivenin().Weprovideatheoreticalderivationofthesealgorithsshowing
`thatfor(cid:22)= ,thealgorithmin( ){()foranyvalidqisthesolutiontothefollowingoptimization
`problem:
`minimize
`()
`jjWk+ (cid:0)Wkjjp
`dk(cid:0)WTk+ Xk= ;
`subjectto
`()
`wherejj(cid:1)jjpdenotestheLpnormandpisdeterminedfromtheequation =p+ =q= .Thus,
`theadaptivealgorithmupdatein( ){()providestheminimumchangeinanLp-normsenseofthe
`weightstoexactlysatisfythe(cid:12)lteringrelationshipbetweentheinputdataandthedesiredresponse
`attimek,similartoaprojectionintheL-normcase.
`Examiningthealgorithmin( ){()forq= ,wediscoverasimplebutpowerfuladaptation
`algorithmgivenby
`wi;k+ =<:wi;k+(cid:22)ekxi;k;
`
`ifjxi;kj=max (cid:20)j(cid:20)Ljxj;kj
`()
`otherwise.
`wi;k;
`Inthisexpressionoftheupdate,themaximumabsolutedatavaluejxi;kj=max (cid:20)j(cid:20)Ljxj;kjisas-
`sumedtobeunique;ifnot,asingle(cid:12)ltercoe(cid:14)cientfromthesetfwi;k:jxi;kj=max (cid:20)j(cid:20)Ljxj;kjg
`ischosenrandomlyforupdating.Thus,theonly(cid:12)ltercoe(cid:14)cientupdatedattimekisacoe(cid:14)cient
`associatedwithaninputsamplewhichhasthelargestabsolutevalueofallinputdatasamples
`currentlyin(cid:12)ltermemory.Thisalgorithmrequiresasearchthroughtheinputdatavectorele-
`mentsbutonlyrequiresonemultiply,onedivide,andoneadditionperiteration,simplifyingits
`implementationinhardware.E(cid:14)cientmethodsformaintainingthemaximumdataelementacross
`ashift-inputdatawindowexist[],andadivide-and-conquerstrategyrequiresatmostlogLcom-
`paresateachiteration.Thus,thenewalgorithmmayproveusefulinsituationswhereexcessive
`(cid:12)lterlengthsprecludeupdatingeveryweightateachiteration.
`Derivation
`WenowshowthatthefamilyofNLMSalgorithmsdescribedby( ){()solvestheoptimization
`problemin(){().Ourderivationfollowsasimilarderivationpresentedin[]fortheNagumoand
`Nodaalgorithmandusesthefollowingtheorem.
`
`Petitioner Apple Inc.
`Ex. 1008, p. 2
`
`
`
`Theorem:LetAbeanonzerovectorcontainedinthevectorspaceRL,andletbbeascalar
`quantity.Then,theminimumLp-normsolutionvectorZtoaconsistentlinearequationATZ=b
`isgivenby
`()
`Z=bFq(A);
`wherethevectorfunctionFq((cid:1))isgivenby().
`Proof:LetaiandzidenotetheithelementsofthevectorsAandZ,respectively.Then,
`jbj=(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)LXi= aizi(cid:12)(cid:12)(cid:12)(cid:12)(cid:12)
`( )
`( )
`(cid:20)jjZjjpjjAjjq
`where( )followsfrom( )fromtheH(cid:127)olderinequalitywith =p+ =q= .Thus,forthenonzero
`vectorA,wehave
`jbj
`( )
`jjAjjq:
`jjZjjp(cid:21)
`Consequently,thefollowinginequalityholds:
`jbj
`minATZ=bjjZjjp(cid:21)
`( )
`jjAjjq:
`LetZbeasolutionvectortotheequationATZ=b.NotethatZisnotunique,butthatit
`satis(cid:12)es
`jjZjjp(cid:21)
`minATZ=bjjZjjp
`( )
`forallZinRL.Now,let
`Z=bFq(A):
`( )
`Itcanbeseenthat,for (cid:20)q< ,
`! =p
`jjZjjp=jbj PLi= jaijp(q(cid:0) )
`( )
`jjAjjpqq
`! =p:
`jjAjjq PLi= jaijp(q(cid:0) )
`jbj
`=
`( )
`jjAjjp(q(cid:0) )
`q
`
`
`Petitioner Apple Inc.
`Ex. 1008, p. 3
`
`
`
`Usingtherelationshipp=q=(q(cid:0) ),theterminsidetheparenthesesof( )canbeshowntobe
`equaltoone.Thus,from( )and( ),wehave
`( )
`jjZjjp=
`minATZ=bjjZjjp:
`Consideringthecase(p= ;q= ),we(cid:12)ndfrom( )and( )that
`b
`jjZjj =
`( )
`jjAjj =minATZ=bjjZjj :
`Therefore,()follows..
`Toseehowthetheoremenablesthesolutiontotheproblemposedin(){(),assignZ=
`Wk+ (cid:0)Wk,A=Xk,andb=ek.Then,fromthede(cid:12)nitionoftheerrorek,wehave
`ek=dk(cid:0)XTkWk
`( )
`=(dk(cid:0)XTkWk+ )+XTk(Wk+ (cid:0)Wk):
`( )
`Iftheconstraintin()issatis(cid:12)ed,thenfromourassignmentsofZ,A,andb,
`XTk(Wk+ (cid:0)Wk)=ek!ATZ=b;
`( )
`andthustheoptimizationproblemin(){()isthesameastheminimizationofjjZjjpsubjectto
`ATZ=b.Therefore,from( ),theoptimumupdateforWkisgivenby( ){().
` Simulations
`Wenowpresentsimulationsofthesimpli(cid:12)edupdatealgorithmtocompareitsperformancewith
`thestandardNLMSandNagumoandNodaalgorithmsforasix-coe(cid:14)cientFIRsystemidenti(cid:12)cation
`task.Theinputdataforthissystemwasgeneratedas
`xi;k=sin(cid:18)(cid:25)(k(cid:0)i+ )
`(cid:19)+vk(cid:0)i+ ;
`()
`
`wherevkisawhiteGaussiandatasequencewithvariance(cid:27)v= : .Theoutputofthesystem
`tobeidenti(cid:12)edwasgeneratedby(cid:12)lteringthisinputusingasix-tap(cid:12)lterwithunitycoe(cid:14)cients
`andaddingwhiteGaussiannoisewithvariance(cid:27)n= : toeachsample.Stepsizesforthethree
`algorithmswerechosenbytrial-and-errorsuchthateachalgorithmproducedthesameaverage
`excessmean-squareerroratconvergence.Theinitialcoe(cid:14)cientsW werefoundbyperturbing
`
`
`Petitioner Apple Inc.
`Ex. 1008, p. 4
`
`
`
`eachoftheidealcoe(cid:14)cientsbyauniformly-distributedrandomvariate.Onehundredtrialswere
`averagedtoproduceeachconvergencecurve.
`Figure showstheconvergenceoftheexcessmean-squareerrorforeachalgorithminthistask.
`Ascanbeseen,thesimpli(cid:12)edupdatealgorithmactuallyconvergesfasterthaneithertheNLMS
`algorithmortheNagumoandNodaalgorithmforthisdataset.Sinceallthealgorithmsconvergeto
`thesame(cid:12)nalexcesserror,thesimpli(cid:12)edalgorithmoutperformstheotheralgorithmsforthisdata
`set.Itshouldbenotedthatforotherdatasetssuchasindependentinputdata,theperformanceof
`thesimpli(cid:12)edupdatealgorithmisworsethantheNLMSorNagumoandNodaalgorithms,andthe
`statisticalbehaviorofanyadaptivealgorithmishighlydependentupontheinputdatastatistics.
`Evenso,thesimpli(cid:12)edupdatealgorithmmayproveusefulinsituationswherecomputationisata
`premium,asitrequiresonlyonecoe(cid:14)cienttobeupdatedateveryiteration.
`Conclusions
`WehavepresentedaderivationofafamilyofadaptivealgorithmsthatincludestheNLMS
`algorithmandthesimpli(cid:12)edalgorithmofNagumoandNodaasspecialcases.
`Inaddition,we
`haveidenti(cid:12)edanewadaptivealgorithmthatupdatesonlyone(cid:12)ltercoe(cid:14)cientateachiteration
`accordingtothestatisticsoftheinputdata.Furtherworkshallfocusuponarigorousanalysisof
`theseadaptivealgorithmsandaninvestigationintotheirrobustnessproperties.
`References
`[ ]G.C.GoodwinandK.S.Sin,AdaptiveFiltering,Prediction,andControl(EnglewoodCli(cid:11)s,
`NJ:Prentice-Hall, ).
`[]J.NagumoandA.Noda,\Alearningmethodforsystemidenti(cid:12)cation,"IEEETrans.Automat.
`Contr.,vol.AC- ,no. ,pp.-,June .
`[ ]M.TarrabandA.Feuer,\ConvergenceandperformanceanalysisofthenormalizedLMS
`algorithmwithuncorrelatedGaussiandata,"IEEETrans.Inform.Theory,vol. ,no.,pp.
` - ,July .
`[]S.C.DouglasandT.H.-Y.Meng,\NormalizeddatanonlinearitiesforLMSadaptation,"IEEE
`Trans.Acoust.,Speech,SignalProcessing,vol.SP-,no.,June ,toappear.
`[]I.Pitas,\Fastalgorithmsforrunningorderingandmax/mincalculation,"IEEETrans.Cir-
`cuitsSystems,vol. ,no.,pp. - ,June .
`[]S.H.Cho,Y.S.Kim,andJ.A.Cadzow,\AdaptiveFIR(cid:12)lteringbasedonminimumL -norm,"
`IEEEPaci(cid:12)cRimConf.onCommunications,ComputersandSignalProcessing,Victoria,
`B.C.,Canada,vol.,pp. -,May .
`
`Petitioner Apple Inc.
`Ex. 1008, p. 5
`
`
`
`1000
`
`2000
`
`5000
`4000
`3000
`number of iterations
`
`6000
`
`7000
`
`8000
`
`Petitioner Apple Inc.
`Ex. 1008, p. 6
`
`100
`
`10-1
`
`10-2
`
`Excess MSE
`
`10-3
`
`0
`
`Nagumo and Noda
`
`NLMS
`
`Simplified
`
`Figure :ConvergenceofexcessMSE:NLMS,NagumoandNoda,andsingle-coe(cid:14)cientupdate
`algorithms,L=,(cid:22)NLMS= : ,(cid:22)Nagumo= : ,(cid:22)simplified= : .
`
`
`