Estimation in Gaussian Graphical Models using Trac

1EstimationinGaussianGraphicalModelsusingTractableSubgraphs:AWalk-SumAnalysisVenkatChandrasekaran∗,JasonK.Johnson,AlanS.WillskyJanuary17,2007AbstractGraphicalmodelsprovideapowerfulformalismforstatisticalsignalprocessing.Duetotheirsophis-ticatedmodelingcapabilities,theyhavefoundapplicationsinavarietyoffieldssuchascomputervision,imageprocessing,anddistributedsensornetworks.Inthispaper,wepresentageneralclassofalgorithmsforestimationinGaussiangraphicalmodelswitharbitrarystructure.Thesealgorithmsinvolveasequenceofinferenceproblemsontractablesubgraphsoversubsetsofvariables.ThisframeworkincludesparalleliterationssuchasEmbeddedTrees,serialiterationssuchasblockGauss-Seidel,andhybridversionsoftheseiterations.Wealsodiscussamethodthatuseslocalmemoryateachnodetoovercometemporarycommunicationfailuresthatmayariseindistributedsensornetworkapplications.Weanalyzethesealgorithmsbasedontherecentlydevelopedwalk-suminterpretationofGaussianinference.Wedescribethewalks“computed”bythealgorithmsusingwalk-sumdiagrams,andshowthatarbitrarynon-stationaryiterations(i.e.,basedonanysequenceofsubgraphs)ofthealgorithmsconvergeinwalk-summablemodels.Sincesubgraphscanbeusedinanyorder,wearefreetochoosespanningtreesandsubsetsofvariablesadaptivelyateachiteration.Thisleadstoefficientmethodsforoptimizingthenextiterationsteptoachievemaximumreductioninerror.Simulationresultsdemonstratethatthesenon-stationaryalgorithmsprovideasignificantspeedupinconvergenceovertraditionalone-treeandtwo-treeiterations.IndexTermsGraphicalmodels,Gauss-MarkovRandomFields,walk-sums,distributedestimation,walk-sumdia-grams,subgraphpreconditioners,maximumwalk-sumtree.∗Correspondingauthor:VenkatChandrasekaran.TheauthorsarewiththeLaboratoryforInformationandDecisionSystems,DepartmentofElectricalEngineeringandComputerScience,MassachusettsInstituteofTechnology,Cambridge,MA02139USA.Email:{venkatc,jasonj,willsky}@mit.edu.Fax:[phone].ThisworkwassupportedbytheArmyResearchOfficegrantW911NF–05–1–0207andtheAirForceOfficeofScientificResearchgrantFA9550–04–1–0351.2I.INTRODUCTIONGraphicalmodelsofferaconvenientrepresentationforjointprobabilitydistributionsandconveytheMarkovstructureinalargenumberofrandomvariablescompactly.Agraphicalmodel[1,2]isacollectionofvariablesdefinedwithrespecttoagraph;eachvertexofthegraphisassociatedwitharandomvariableandtheedgestructurespecifiestheconditionalindependence(Markov)propertiesamongthevariables.Duetotheirsophisticatedmodelingcapabilities,graphicalmodels(alsoknownasMarkovrandomfieldsorMRFs)havefoundapplicationsinavarietyofsignalprocessingtasksinvolvingdistributedsensornetworks[3],images[4,5],andcomputervision[6].OurfocusinthispaperisontheimportantclassofGaussiangraphicalmodels,alsoknownasGauss-Markovrandomfields(GMRFs),whichhavebeenwidelyusedtomodelnaturalphenomenainmanylarge-scaleestimationproblems[7,8].Inestimationproblemsinwhichthepriorandobservationmodelshavenormallydistributedrandomcomponents,computingtheBayesleast-squaresestimateisequivalenttosolvingalinearsystemofequationsspecifiedintermsoftheinformation-formparametersoftheconditionaldistribution.Duetoitscubiccomputationalcomplexityinthenumberofvariables,directmatrixinversiontosolvetheGaussianestimationproblemisintractableinmanyapplicationsinwhichthenumberofvariablesisverylarge(e.g.,inoceanographyproblems[8]thenumberofvariablesmaybeontheorderof106).Fortree-structuredMRFs(i.e.,graphswithnocycles),BeliefPropagation(BP)[9]providesanefficientlinearcomplexityalgorithmtocomputeexactestimates.However,tree-structuredGaussianprocessespossesslimitedmodelingcapabilities[10].Inordertomodelaricherclassofstatisticaldependenciesamongvariables,oneoftenrequiresloopygraphicalmodels.Asestimationongraphswithcyclesissubstantiallymorecomplex,considerableefforthasbeenandstillisbeingputintodevelopingmethodsthatovercomethiscomputationalbarrier,includingavarietyofmethodsthatemploytheideaofperforminginferencecomputationsontractablesubgraphs[11,12].TherecentlyproposedEmbeddedTrees(ET)iteration[10,13]isonesuchapproachthatsolvesasequenceofinferenceproblemsontreesor,moregenerally,tractablesubgraphs.IfETconverges,ityieldsthecorrectconditionalestimates,thusprovidinganeffectiveinferencealgorithmforgraphswithessentiallyarbitrarystructure.ForthecaseofstationaryETiterations—inwhichthesametreeortractablesubgraphisusedateachiteration—necessaryandsufficientconditionsforconvergenceareprovidedin[10,13].However,experimentalresultsin[13]providecompellingevidencethatmuchfasterconvergencecanoftenbeobtainedbychangingtheembeddedsubgraphthatisusedfromoneiterationtothenext.Theworkin[13]providedverylimitedanalysisforsuchnon-stationaryiterations,thusleavingopentheproblemof3providingeasilycomputablebroadlyapplicableconditionsthatguaranteeconvergence.Inrelatedworkthatbuildson[10],Delouilleetal.[14]describeastationaryblockGauss-JacobiiterationforsolvingtheGaussianestimationproblemwiththeaddedconstraintthatmessagesbetweenvariablesconnectedbyanedgeinthegraphmayoccasionallybe“dropped”.Thelocalblocks(subgraphs)areassumedtobesmallinsize.Suchaframeworkprovidesasimplemo