Abstract-Vi tar itu med problemet med att identifiera strukturen på en oriktad graf från observation av signaler som definieras på dess noder. I grund och botten kodar den okända grafen direkta relationer mellan signalelement, som vi strävar efter att återhämta oss från observerbara indirekta relationer som genereras av en diffusionsprocess på grafen. Det fräscha utseende som förespråkas här utnyttjar begrepp från konvex optimering och stationaritet av grafsignaler, för att identifiera grafskiftaren (en matris representation av grafen) med endast dess eigenvectors. Dessa spektralmallar kan erhållas, t.ex. från provets kovarians av oberoende grafsignaler som sprids på det sökta nätverket. Den nya idén är att hitta en graf förskjutning som, samtidigt som den överensstämmer med den medföljande spektralinformationen, ger nätverket med vissa önskade egenskaper såsom gleshet. I detta syfte utvecklar vi effektiva inferensalgoritmer som härrör från bevisligen trånga konvexa avslappningar av naturliga nonconvex-kriterier, särskilt resultaten för två skift: adjacensmatrisen och den normaliserade Laplacian. Algoritmer och teoretiska återhämtningsförhållanden utvecklas inte bara när mallarna är fullständigt kända, utan också när eigenvektorerna är högljudda eller när endast en delmängd av dem ges. Numeriska tester visar hur effektiva de föreslagna algoritmerna är när det gäller att återvinna syntetiska och verkliga nätverk.
Problemet med att uppskatta en topologi från signalobservationer som leder till särskilda graf skift operatörer studeras i REF.
Network Topology Inference from Spectral Templates
{'venue': 'IEEE Transactions on Signal and Information Processing over Networks', 'journal': 'IEEE Transactions on Signal and Information Processing over Networks', 'mag_field_of_study': ['Computer Science', 'Physics']}