Rice_CAAM_TR13-06_LBreg_decentralized_BP

ALinearizedBregmanAlgorithmforDecentralized

BasisPursuit

KunYuan,QingLing,WotaoYin,AlejandroRibeiro

Abstract—Inthispaperwesolveadecentralizedbasispursuitprobleminamultiagentsystemwhereeachagentholdspartofthelinearobservationsonacommonsparsevector.Theagentscollaboratetorecoverthesparsevectorthroughlimitedneigh-boringcommunication.TheproposeddecentralizedlinearizedBregmanalgorithmsolvestheLagrangedualofanaugmented 1modelthatisequivalenttobasispursuit.Thefactthatthisdualproblemisunconstrainedanddifferentiableenablesalightweightyetef cientdecentralizedgradientalgorithm.Weprovenearlylinearconvergenceofthedualandprimalvariablestotheiroptima.Numericalexperimentsdemonstratetheeffectivenessoftheproposedalgorithm.

IndexTerms—Basispursuit,linearizedBregman,decentralizedcomputation

I.INTRODUCTION

Consideramultiagentsystemofndistributedagentswhocollaborativelyrecoverasparsesignalx∈Rpfromthelinearmeasurementsthattheyindividuallycollect.Agenticollectsmeasurementsbi=Aix,wherebi∈RqiandAi∈Rqi×p .Let

b bA 1—1— ... ∈Rq,A ... ∈Rq×p,bwhereq= n—An—

n

i=1qi.Weproposeadecentralizedalgorithmfor

theagentstocollaborativelysolvethebasispursuitproblem[1]:

minx||x||1s.t.Ax=b.(1)Accordingtothecompressivesensingtheory[2],[3],ifA

satis escertainpropertiesandxissuf cientlysparse,model(1)exactlyrecoversx.Ifbiscontaminatedbynoiseorxisonlyapproximatelysparse,stablerecoverycanbeguaranteedifonereplacestheconstraintsAx=bby Ax b ≤ ,where · isthe 2-normand istheestimatednoiselevel,orstopsouralgorithmwhen Ax b ≈ .

Distributedbasispursuitisappliedincollaborativespectrumsensing[4],[5],[6],[7],wherethegoalistorecoverawidebandspectrumsignalx,whichissparse.Agentitakesitsmeasurementbi=AixwithsensingmatrixAi,andallagentscollaboratetorecoverxthroughsolvingmodel(1).

K.YuanandQ.LingarewithDept.ofAutomation,UniversityofScienceandTechnologyofChina,Hefei,Anhui,China230026.W.YiniswithDept.ofComputationalandAppliedMathematics,RiceUniversity,Houston,TX,USA77005.A.RibeiroiswithDept.ofElectricalandSystemsEngineer-ing,UniversityofPennsylvania,Philadelphia,PA,USA19104.Q.LingissupportedbyNSFCgrant61004137.W.YinissupportedbyARLandAROgrantW911NF-09-1-0383,NSFgrantsDMS-0748839andECCS-1028790.A.RibeiroissupportedbyNSFCAREERCCF-0952867,NSFCCF-1017454,andAFOSRMURIFA9550-10-1-0567.

Decentralizedoptimizationhasseveraladvantagesformulti-agentsystems.Incentralizedcomputation,theagentsneedtotransmitalltheirdata,Aiandbiinourcase,toafusioncenterviamulti-hopcommunicationandthefusioncentersolves(1)andbroadcaststhesolutionstotheagents.Thisapproachisenergy-consumingandvulnerabletonetworkandfusioncenterfailures.Indecentralizedcomputation,eachagentonlyexchangesalimitedamountofinformationwithitsone-hopneighborsandkeepsitsdata(e.g.,Aiandbi)private.Theoptimizationiscompletedwithoutafusioncenter[8],[9].ConsiderthedecentralizedbasispursuitproblemwherethesensingmatrixAispartitionedbyrows.Theoptimizationvariableiscommontoallagentsandeachagentholdspartoftheobjectivefunctionandpartoftheconstraint.Forthiskindofproblem,existingdecentralizedalgorithmsincludedistributedsubgradientdescent[10],distributedstochasticsubgradientprojection[11],andalternatingdirectionalgorithmofmultipliers(ADMM)[8],[12],[13].Inthesealgorithms,eachagentholdsalocalsolution;ateachiteration,agentsexchangethelocalsolutionswiththeirone-hopneighbors.Fordistributedsubgradientdescent,eachagent rstcom-putesanewsolutionthroughcombininglocalsolutionsofitselfanditsone-hopneighborswithweightedaverage,andthendescendsalongitslocalnegativesubgradientdirection[10].Distributedstochasticsubgradientprojectionissimilartodistributedsubgradientdescentbutincludesanextraprojectionoperationtoacommonconstraintset[11].Thougheasytoimplementandsuitforasynchronousnetworks,thesetwoalgorithmsarenotcompetitiveinsolvingthedecentralizedbasispursuitproblemsincetheydonothandletheconstraintsAx=bef cientlyandsubgradientdescentdoesnottakeadvantageofthestructureof x 1.

TheADMMapproachfor(1)explicitlyintroducescon-sensusconstraints.Solvingthisconsensus-constrainedprob-lemwithskillfulvariablesplittingleadstodecentralizedalgorithms.ADMM-baseddecentralizedalgorithmsconvergegloballyforconvexproblems,andhavelinearconvergencewheneachlocalobjectivefunctionisdifferentiable,stronglyconvexandhavingLipschitzcontinuousgradient[14].For(1),theADMM-basedapproachrequireseachagenttosolvealeastabsoluteshrinkageandselectionoperator(LASSO)subproblemwithpunknownateachiteration,requiringarathersigni cantamountofcomputationoneachagent[5],[7].[6]elegantlysimpli esthesubproblemforeachagentbutitsalgorithmrequiresmuchmoreiterationstoconverge.

ThispaperproposesadecentralizedlinearizedBregmanalgorithmforsolving(1).Theproposedalgorithmisveryeasytoimplement,convergesfastatanearlylinearrate,

Word文档免费下载Word文档免费下载:Rice_CAAM_TR13-06_LBreg_decentralized_BP (共5页,当前第1页)

Rice_CAAM_TR13 06_LBreg_decentralized_BP相关文档

最新文档

返回顶部