The association of a graph representation to large datasets is one of key steps in graph-based learning methods. The aim of this paper is to propose an efficient strategy for learning the graph topology from signals defined over the vertices of a graph, under a signal band-limited (either exactly or only approximately so) assumption, which corresponds to signals having clustering properties. The proposed method is composed of two optimization steps. The first step consists in learning, jointly, the sparsifying orthonormal transform and the graph signal from the observed data. The solution of this joint problem is achieved through an iterative algorithm whose alternating intermediate solutions are expressed in closed form. The second step recovers the Laplacian matrix, and then the topology, from the knowledge of the sparsifying transform, through a convex optimization strategy which admits an efficient solution.

Graph topology inference based on transform learning / Sardellitti, Stefania; Barbarossa, Sergio; Di Lorenzo, Paolo. - ELETTRONICO. - 2016(2016), pp. 356-360. ((Intervento presentato al convegno 2016 IEEE Global Conference on Signal and Information Processing (GlobalSIP) tenutosi a Washington; United States [10.1109/GlobalSIP.2016.7905863].

Graph topology inference based on transform learning

SARDELLITTI, Stefania;BARBAROSSA, Sergio;Di Lorenzo, Paolo
2016

Abstract

The association of a graph representation to large datasets is one of key steps in graph-based learning methods. The aim of this paper is to propose an efficient strategy for learning the graph topology from signals defined over the vertices of a graph, under a signal band-limited (either exactly or only approximately so) assumption, which corresponds to signals having clustering properties. The proposed method is composed of two optimization steps. The first step consists in learning, jointly, the sparsifying orthonormal transform and the graph signal from the observed data. The solution of this joint problem is achieved through an iterative algorithm whose alternating intermediate solutions are expressed in closed form. The second step recovers the Laplacian matrix, and then the topology, from the knowledge of the sparsifying transform, through a convex optimization strategy which admits an efficient solution.
978-1-5090-4545-7
File allegati a questo prodotto
File Dimensione Formato  
Sardellitti_Graph-topology_2016.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 163.6 kB
Formato Adobe PDF
163.6 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11573/958745
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? ND
social impact