搜索
AdaptiveGreedyApproximations1Geo reyDavisMathematicsDepartment,DartmouthCollegeHanover,NH03755gdavis@cs.dartmouth.eduSt ephaneMallat,MarcoAvellanedaCourantInstitute,NewYorkUniversity251MercerStreet,NewYork,NY10012mallat@cs.nyu.edu,avellane@nyu.eduAbstractTheproblemofoptimallyapproximatingafunctionwithalinearexpansionoveraredundantdictionaryofwaveformsisNP-hard.Thegreedymatchingpursuitalgorithmanditsorthog-onalizedvariantproducesub-optimalfunctionexpansionsbyiterativelychoosingdictionarywaveformsthatbestmatchthefunction’sstructures.Amatchingpursuitprovidesameansofquicklycomputingcompact,adaptivefunctionapproximations.Numericalexperimentsshowthattheapproximationerrorsfrommatchingpursuitsinitiallydecreaserapidly,buttheasymptoticdecayrateoftheerrorsisslow.Weexplainthisbehaviorbyshowingthatmatchingpursuitsarechaotic,ergodicmaps.Thestatisticalpropertiesoftheapproximationerrorsofapursuitcanbeobtainedfromtheinvariantmeasureofthepursuit.Wecharacterizethesemeasuresusinggroupsymmetriesofdictionariesandbyconstructingastochasticdi erentialequationmodel.Wederiveanotionofthecoherenceofasignalwithrespecttoadictionaryfromourcharacterizationoftheapproximationerrorsofapursuit.Thedictionaryelementsselectedduringtheinitialiterationsofapursuitcorrespondtoafunction’scoherentstructures.Thetailoftheexpansion,ontheotherhand,correspondstoanoisewhichischaracterizedbytheinvariantmeasureofthepursuitmap.Whenusingasuitabledictionary,theexpansionofafunctionintoitscoherentstructuresyieldsacompactapproximation.Wedemonstrateadenoisingalgorithmbasedoncoherentfunctionexpansions.1IntroductionFordatacompressionapplicationsandfastnumericalmethodsitisimportanttoaccuratelyapproximatefunctionsfromaHilbertspaceHusingasmallnumberofvectorsfromagiven1ThisworkwassupportedbyanONRgraduatefellowship,theAFOSRgrantF49620-93-1-0102,ONRgrantN00014-91-J-1967,andtheAlfredSloanFoundation1familyfg g 2 .ForanyM0,wewanttominimizetheapproximationerror (M)=kf X 2IM g kwhereIM isanindexsetofcardinalityM.Ifthefamilyfg g 2 isanorthonormalbasis,thenbecause (M)=X 2 IMjg ;fj2;theerrorisminimizedbytakingIMtocorrespondtotheMvectorswhichhavethelargestinnerproducts(jf;g j) 2IM.DependinguponthebasisandthespaceH,itispossibletoestimatethedecayrateoftheminimalapproximationerror 0(M)=infIM (M)asMincreases.Forexample,whenfg g 2 isawaveletbasistherateofdecayof 0(M)canbeestimatedforfunctionsthatbelongtoaparticularclassofBesovspaces[9].Conversely,therateofdecayof 0(M)canbeusedtodeterminetowhichBesovspaceinthisclassfbelongs.Wecangreatlyimprovetheseapproximationstofbyenlargingthecollectionfg g 2 beyondabasis.Thisenlarged,redundantfamilyofvectorswecalladictionary.Theadvantageofredundancyinobtainingcompactrepresentationscanbeseenbyconsideringtheproblemofrepresentingatwo-dimensionalsurfacegivenbyf(x;y)onasubsetoftheplane,I I.AnadaptivesquaremeshrepresentationoffintheBesovspaceB q(Lq(I)),where1q= +12,canbeobtainedusingawaveletbasis.Thiswaveletrepresentationcanbeshowntobeasymptoticallynearoptimalinthesensethatthedecayrateoftheerror (M)isequaltothelargestdecayattainablebyageneralclassofnon-lineartransform-basedapproximationschemes[10].Eventhesenear-optimalrepresentationsareconstrainedbythefactthatthedecomposi-tionsareoverabasis.Theregulargridstructureofthewaveletbasispreventsthecompactrepresentationofmanyfunctions.Forexample,whenfisequaltoabasiswaveletatthelargestscale,itcanberepresentedexactlybyaexpansionconsistingofasingleelement.However,ifwetranslatethisfbyasmallamount,thenanaccurateapproximationcanrequiremanyelements.Onewaytoimproveourapproximationsistoaddtothesetfg g 2 thecollectionofalltranslatesofthewavelets.Theclassoffunctionswhichcanbecompactlyrepresentedwillthenbetranslationinvariant.Wecanobtainevenbettercompactapproximationsbyexpandingthedictionarytocontaintheextremelyredundantsetofallpiecewisepolynomialfunctionsonarbitrarytriangles.Whenthedictionaryisredundant, ndingafamilyofMvectorsthatapproximatesfwithanerrorclosetotheminimum 0(M)isclearlynotachievedbyselectingthevectorsthathavemaximalinnerproductswithf.Insection2weprovethatforgeneraldictionariestheproblemof ndingM-elementoptimalapproximationsbelongstoaclassofcomputationallyintractableproblems,thesetofNP-hardproblems.Itiswidelybelieved(butunproven)thatthenumberofoperationsrequiredtosolveanNP-hardproblemgrowsfasterthananypolynomialintheinputsize[13].Becauseofthedi cultyofcomputingoptimalexpansions,weturntosuboptimalalgorithms.Insection3wereviewtheperformanceofgreedyalgorithms,calledmatchingpursuits,that2wereintroducedin[24][7].Wedescribeafastimplementationofthesealgorithms,andwegivenumericalexamplesforadictionarycomposedofwaveformsthatarewell-localizedintimeandfrequency.Suchdictionariesareparticularlyimportantforaudiosignalprocessing.Inournumericalexperimentswe ndthattherateofdecayofthegreedyapproximationerror (M)decreasesasMbecomeslarge.Theseobservationsareexplainedbyshowingthatamatchingpursuitisachaoticmapwhichhasanergodicinvariantmeasure.Theproofofchaosinsection5isgivenforaparticulardictionaryinalow-dimensionalspace,andwes