Graph-based representations play a key role in machine learning. The fundamental step in these representations is the association of a graph structure to a dataset. In this paper, we propose a method that finds a block sparse representation of the data by associating a graph, whose Laplacian matrix admits the sparsifying dictionary as its eigenvectors. The main idea is to associate a graph topology to the data in order to make the observed signals band-limited over the inferred graph. The proposed strategy is composed of the following two optimization steps: first, learning an orthonormal sparsifying transform from the data; and second, recovering the Laplacian matrix, and then topology, from the transform. The first step is achieved through an iterative algorithm whose alternating intermediate solutions are expressed in closed form. The second step recovers the Laplacian matrix from the sparsifying transform through a convex optimization method. Numerical results corroborate the effectiveness of the proposed methods over both synthetic and real data. Specifically, we consider two real-world applications of our methods: the inference of the brain functional activity map from electrocorticography signals taken from patients affected by epilepsy, and the reconstruction of the radio environment map from sparse measurements of the electromagnetic field in an urban area.

Graph topology inference based on sparsifying transform learning / Sardellitti, Stefania; Barbarossa, Sergio; Di Lorenzo, Paolo. - In: IEEE TRANSACTIONS ON SIGNAL PROCESSING. - ISSN 1053-587X. - 67:7(2019), pp. 1712-1727. [10.1109/TSP.2019.2896229]

Graph topology inference based on sparsifying transform learning

Sardellitti, Stefania;Barbarossa, Sergio;Di Lorenzo, Paolo
2019

Abstract

Graph-based representations play a key role in machine learning. The fundamental step in these representations is the association of a graph structure to a dataset. In this paper, we propose a method that finds a block sparse representation of the data by associating a graph, whose Laplacian matrix admits the sparsifying dictionary as its eigenvectors. The main idea is to associate a graph topology to the data in order to make the observed signals band-limited over the inferred graph. The proposed strategy is composed of the following two optimization steps: first, learning an orthonormal sparsifying transform from the data; and second, recovering the Laplacian matrix, and then topology, from the transform. The first step is achieved through an iterative algorithm whose alternating intermediate solutions are expressed in closed form. The second step recovers the Laplacian matrix from the sparsifying transform through a convex optimization method. Numerical results corroborate the effectiveness of the proposed methods over both synthetic and real data. Specifically, we consider two real-world applications of our methods: the inference of the brain functional activity map from electrocorticography signals taken from patients affected by epilepsy, and the reconstruction of the radio environment map from sparse measurements of the electromagnetic field in an urban area.
File allegati a questo prodotto
File Dimensione Formato  
Sardellitti_Graph-topology_2019.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.79 MB
Formato Adobe PDF
1.79 MB 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/1250686
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 29
  • ???jsp.display-item.citation.isi??? 26
social impact