Cooperative and Graph Signal Processing Cooperative and Graph Signal Processing Principles and Applications Edited by Petar M. Djuric´ Cédric Richard AcademicPressisanimprintofElsevier 125LondonWall,LondonEC2Y5AS,UnitedKingdom 525BStreet,Suite1650,SanDiego,CA92101,UnitedStates 50HampshireStreet,5thFloor,Cambridge,MA02139,UnitedStates TheBoulevard,LangfordLane,Kidlington,OxfordOX51GB,UnitedKingdom Copyright©2018ElsevierInc.Allrightsreserved. Nopartofthispublicationmaybereproducedortransmittedinanyformorbyanymeans,electronicor mechanical,includingphotocopying,recording,oranyinformationstorageandretrievalsystem,without permissioninwritingfromthepublisher.Detailsonhowtoseekpermission,furtherinformationaboutthe Publisher’spermissionspoliciesandourarrangementswithorganizationssuchastheCopyrightClearance CenterandtheCopyrightLicensingAgency,canbefoundatourwebsite:www.elsevier.com/permissions. ThisbookandtheindividualcontributionscontainedinitareprotectedundercopyrightbythePublisher(other thanasmaybenotedherein). Notices Knowledgeandbestpracticeinthisfieldareconstantlychanging.Asnewresearchandexperiencebroadenour understanding,changesinresearchmethods,professionalpractices,ormedicaltreatmentmaybecomenecessary. Practitionersandresearchersmustalwaysrelyontheirownexperienceandknowledgeinevaluatingandusing anyinformation,methods,compounds,orexperimentsdescribedherein.Inusingsuchinformationormethods theyshouldbemindfuloftheirownsafetyandthesafetyofothers,includingpartiesforwhomtheyhavea professionalresponsibility. Tothefullestextentofthelaw,neitherthePublishernortheauthors,contributors,oreditors,assumeanyliability foranyinjuryand/ordamagetopersonsorpropertyasamatterofproductsliability,negligenceorotherwise,or fromanyuseoroperationofanymethods,products,instructions,orideascontainedinthematerialherein. LibraryofCongressCataloging-in-PublicationData AcatalogrecordforthisbookisavailablefromtheLibraryofCongress BritishLibraryCataloguing-in-PublicationData AcataloguerecordforthisbookisavailablefromtheBritishLibrary ISBN978-0-12-813677-5 ForinformationonallAcademicPresspublicationsvisitour websiteathttps://www.elsevier.com/books-and-journals Publisher:MaraConner AcquisitionEditor:TimPitts EditorialProjectManager:PeterJardim ProductionProjectManager:SruthiSatheesh Designer:ChristianBilbow TypesetbySPiGlobal,India Contributors SelinAviyente DepartmentofElectricalandComputerEngineering,MichiganStateUniversity, EastLansing,MI,UnitedStates PaoloBanelli DepartmentofEngineering,UniversityofPerugia,Perugia,Italy SergioBarbarossa DepartmentofInformationEngineering,Electronics,andTelecommunications,Sapienza UniversityofRome,Rome,Italy PierreBorgnat ENSdeLyon,UnivLyon1,CNRS,LaboratoiredePhysique&IXXI,UnivLyon, Lyon,France ElenaCeci DepartmentofInformationEngineering,Electronics,andTelecommunications,Sapienza UniversityofRome,Rome,Italy Shih-FuChang DepartmentofElectricalEngineeringandDepartmentofComputerScience, ColumbiaUniversity,NewYork,NY,UnitedStates ChaoCheng Dartmouth-HitchcockMedicalCenter,Lebanon,NH,UnitedStates JieChen CenterofIntelligentAcousticsandImmersiveCommunications,SchoolofMarine ScienceandTechnology,NorthwesternPolytechnicalUniversity,Xi’an,China SundeepPrabhakarChepuri DelftUniversityofTechnology,Delft,TheNetherlands LucaCorinzia CMLA,ENSCachan,CNRS,UniversityofParis-Saclay,Cachan,France;ETHZurich, Zurich,Switzerland KamilDedecius DepartmentofAdaptiveSystems,InstituteofInformationTheoryandAutomation, TheCzechAcademyofSciences,Prague,CzechRepublic PetarM.Djuric´ DepartmentofElectricalandComputerEngineering,StonyBrookUniversity, StonyBrook,NY,UnitedStates CeyhunEksin DepartmentofIndustrialandSystemsEngineering,TexasA&MUniversity,CollegeStation, TX,UnitedStates AndreyGarnaev WirelessInformationNetworkLaboratory(WINLAB),Rutgers,TheStateUniversity ofNewJersey,NorthBrunswick,NJ,UnitedStates xxi xxii Contributors DavidGesbert CommunicationSystemsDepartment,EURECOM,Biot,France GeorgiosB.Giannakis DepartmentofElectricalandComputerEngineering,UniversityofMinnesota,Minneapolis, MN,UnitedStates PauloGonçalves ENSdeLyon,UnivLyon1,CNRS,Inria,LIP&IXXI,UnivLyon,Lyon,France AlfredHero EECSDepartment,UniversityofMichigan,AnnArbor,MI,UnitedStates FranzHlawatsch InstituteofTelecommunications,TUWien,Vienna,Austria WilliamHoiles Biosymetrics,NewYork,NY,UnitedStates HazerInaltekin DepartmentofElectricalandElectronicEngineering,TheUniversityofMelbourne, Parkville,VIC,Australia Kwang-SungJun WisconsinInstituteforDiscovery,Madison,WI,UnitedStates BhavyaKailkhura CenterforAppliedScientificComputing,LawrenceLivermoreNationalLaboratory, Livermore,CA,UnitedStates ArgyrisKalogeratos CMLA,ENSCachan,CNRS,UniversityofParis-Saclay,Cachan,France SithanKanna DepartmentofElectricalandElectronicEngineering,ImperialCollegeLondon,London, UnitedKingdom SoummyaKar DepartmentofElectricalandComputerEngineering,CarnegieMellonUniversity, Pittsburgh,PA,UnitedStates PauldeKerret CommunicationSystemsDepartment,EURECOM,Biot,France VikramKrishnamurthy SchoolofElectricalandComputerEngineering,CornellTech,CornellUniversity,NewYork, NY,UnitedStates AmirLeshem FacultyofEngineering,Bar-IlanUniversity,RamatGan,Israel GeertLeus DelftUniversityofTechnology,Delft,TheNetherlands ZhenguoLi HuaweiNoah’sArkLab,Shatin,HongKongSpecialAdministrativeRegion Contributors xxiii SijiaLiu EECSDepartment,UniversityofMichigan,AnnArbor,MI,UnitedStates YingLiu WirelessInformationNetworkLaboratory(WINLAB),Rutgers,TheStateUniversity ofNewJersey,NorthBrunswick,NJ,UnitedStates PaoloDiLorenzo DepartmentofInformationEngineering,Electronics,andTelecommunications, SapienzaUniversityofRome,Rome,Italy DaniloP.Mandic DepartmentofElectricalandElectronicEngineering,ImperialCollegeLondon, London,UnitedKingdom MortezaMardani DepartmentofElectricalEngineering,StanfordUniversity,Stanford,CA,UnitedStates AntonioG.Marques DepartmentofSignalTheoryandCommunications,KingJuanCarlosUniversity,Madrid,Spain GonzaloMateos DepartmentofElectricalandComputerEngineering,UniversityofRochester,Rochester, NY,UnitedStates VincenzoMatta DepartmentofInformationEngineering,ElectricalEngineeringandAppliedMathematics, DIEM,UniversityofSalerno,Fisciano,Italy MattiaMerluzzi DepartmentofInformationEngineering,Electronics,andTelecommunications,Sapienza UniversityofRome,Rome,Italy JoséM.F.Moura DepartmentofElectricalandComputerEngineering,CarnegieMellonUniversity, Pittsburgh,PA,UnitedStates EricMoulines CMAP,EcolePolytechnique,Palaiseau,France RobertNowak DepartmentofElectricalandComputerEngineering,UniversityofWisconsin-Madison, Madison,WI,UnitedStates BrandonOselio EECSDepartment,UniversityofMichigan,AnnArbor,MI,UnitedStates KonstantinosPlataniotis ElectricalandComputerEngineering,UniversityofToronto,Toronto,ON,Canada H.VincentPoor DepartmentofElectricalEngineering,PrincetonUniversity,Princeton,NJ,UnitedStates MichaelG.Rabbat McGillUniversityandFacebookAIResearch,Montreal,QC,Canada xxiv Contributors AlejandroRibeiro DepartmentofElectricalandSystemsEngineering,UniversityofPennsylvania, Philadelphia,PA,UnitedStates CédricRichard LaboratoireLagrange,UniversitéCôted’Azur,CNRS,OCA,Nice,France StefaniaSardellitti DepartmentofInformationEngineering,Electronics,andTelecommunications,SapienzaUniversity ofRome,Rome,Italy AliH.Sayed SchoolofEngineering,ÉcolePolytechniqueFédéraledeLausanne(EPFL),Lausanne,Switzerland AnnaScaglione SchoolofElectrical,ComputerandEnergyEngineering,ArizonaStateUniversity, Tempe,AZ,UnitedStates KevinScaman CMLA,ENSCachan,CNRS,UniversityofParis-Saclay,Cachan,France;MSR,InriaJoint Center,Palaiseau,France MihaelavanderSchaar ElectricalEngineeringDepartment,UniversityofCalifornia,LosAngeles,LosAngeles, CA,UnitedStates SantiagoSegarra InstituteforData,Systems,andSociety;MassachusettsInstituteofTechnology, Cambridge,MA,UnitedStates PetrosSpachos SchoolofEngineering,UniversityofGuelph,Guelph,ON,Canada AlexSprintson DepartmentofElectricalandComputerEngineering,TexasA&MUniversity, CollegeStation,TX,UnitedStates BrianSwenson DepartmentofElectricalandComputerEngineering,CarnegieMellonUniversity, Pittsburgh,PA,UnitedStates CemTekin ElectricalandElectronicsEngineeringDepartment,BilkentUniversity,Ankara,Turkey ShangKeeTing DSONationalLaboratories,Singapore,Singapore WadeTrappe WirelessInformationNetworkLaboratory(WINLAB),Rutgers,TheStateUniversityof NewJersey,NorthBrunswick,NJ,UnitedStates NicolasTremblay CNRS,GIPSA-lab,Univ.GrenobleAlpes,Grenoble,France Contributors xxv PramodK.Varshney DepartmentofEECS,SyracuseUniversity,Syracuse,NY,UnitedStates NicolasVayatis CMLA,ENSCachan,CNRS,UniversityofParis-Saclay,Cachan,France AdityaVempaty IBMThomasJ.WatsonResearchCenter,YorktownHeights,NY,UnitedStates MariselVillafañe-Delgado DepartmentofElectricalandComputerEngineering,MichiganStateUniversity, EastLansing,MI,UnitedStates Hoi-ToWai SchoolofElectrical,ComputerandEnergyEngineering,ArizonaStateUniversity, Tempe,AZ,UnitedStates DaifengWang DepartmentofBiomedicalInformatics,StonyBrookUniversity,StonyBrook,NY,UnitedStates Xiao-MingWu DepartmentofComputing,TheHongKongPolytechnicUniversity,Kowloon, HongKongSpecialAdministrativeRegion YiliXia SchoolofInformationScienceandEngineering,SoutheastUniversity,Nanjing,PRChina JieXu ElectricalandComputerEngineeringDepartment,UniversityofMiami,CoralGables, FL,UnitedStates SimpsonZhang EconomicsDepartment,UniversityofCalifornia,LosAngeles,LosAngeles,CA, UnitedStates XiaochuanZhao UniversityofCaliforniaatLosAngeles,UCLA,LosAngeles,CA,UnitedStates Preface Cooperative and graph signal processing are areas that have seen significant growth in recent years, a trend that without a doubt will continue for many years to come. These areas are well within the scope of network science, which deals with complex systems described by interconnected elements and/oragents.Thenetworkscanbeofmanytypesincludingphysical,engineered,information,social, biological,andeconomicnetworks.Withintheframeworkofcooperativeandgraphsignalprocessing one aims at discovering principles of various tasks including distributed detection and estimation, adaptation and learning over networks, distributed decision making, optimization and control over networks, and modeling and identification. The range of possible applications is vast and includes robotics, smart grids, communications, economic networks, life sciences, ecology, social networks, wirelesshealth,andtransportationnetworks. With this book we want to provide in a single volume the basics of cooperative and graph signal processingandtoaddressanumberofareaswheretheyareapplied.Thechaptersaregroupedinfive parts. In Part 1, the fundamentals of inference over networks are addressed, Part 2 is on graph signal processing,Part3focusesoncommunications,networking,andsensing,Part4studiessocialnetworks, and Part 5 describes applications that range from genomics and system biology to big data and brain networks.Allthechaptersarewrittenbyexpertsandleadersinthefield. The contents of Part 1 include the fundamentals of inference, learning, and optimization over networks in synchronous and asynchronous settings (Chapter 1); estimation and detection where the emphasis is on studying agents that track drifts in models and examining performance limits under bothestimationanddetection(Chapter2);learninginnetworkswheretheagentsmakeinferenceabout parameters of both, common and local interest (Chapter 3), collaborative inference of agents within theBayesianframework(Chapter4);multiagentdistributedoptimization,wheretheaimofallagents istoagreeontheminimizer(Chapter5);sequentialfilteringusingstate-spacemodelsbyKalmanand particlefiltering(Chapter6);andgame-theoreticlearningwheretheobjectiveofthedecision-makers inthenetworkdependsonboththeactionsofotheragentsandthestateoftheenvironment(Chapter7). Part2startswiththebasicsofgraphsignalprocessing(Chapter8);thenitcontinueswithareview ofrecentadvancesinsamplingandrecoveryofsignalsdefinedovergraphs(Chapter9);activelearning innetworkswhereonehasthefreedomofchoosingnodesforqueryingandwantstoselectintelligently informative nodes to minimize prediction errors (Chapter 10); design of graph filters and filter banks (Chapter11);extensionofthenotionofstationaritytorandomgraphsignals(Chapter12);estimatinga graphtopologyfromgraphsignals(Chapter13);andaunifyingframeworkforlearningongraphsand basedonpartiallyabsorbingrandomwalks(Chapter14). Part 3, with its theme on communications, networking, and sensing, addresses projection-based algorithmsandprojection-freedecentralizedoptimizationalgorithmsforperformingbigdataanalytics (Chapter 15); optimal joint allocation of communication, computation, and caching resources in 5G communication networks (Chapter 16); analysis of a network’s structural vulnerability to attacks (Chapter 17); team methods for cooperation in device-centric setups (Chapter 18); cooperative data exchange so that clients can decode missing messages while minimizing the total number of transmissions (Chapter 19); and Byzantine attacks and defense for collaborative spectrum-sensing in cognitiveradionetworks(Chapter20). xxvii