Graph Topology Inference Based on Sparsifying Transform Learning

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...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on signal processing 2019-04, Vol.67 (7), p.1712-1727
Main Authors: Sardellitti, Stefania, Barbarossa, Sergio, Lorenzo, Paolo Di
Format: Article
Language:English
Subjects:
Brain
Computational geometry
Convexity
Covariance matrices
Dictionaries
Eigenvectors
Electromagnetic fields
Epilepsy
Graph learning
graph signal processing
Graphical representations
Inference
Iterative algorithms
Iterative methods
Laplace equations
Machine learning
Optimization
Sparse matrices
sparsifying transform
Symmetric matrices
Topology
Transforms
Urban areas
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1053-587X
1941-0476
DOI:10.1109/TSP.2019.2896229