How to learn a graph from smooth signals

We propose a framework that learns the graph structure underlying a set of smooth signals. Given a real m by n matrix X whose rows reside on the vertices of an unknown graph, we learn the edge weights w under the smoothness assumption that trace(X^TLX) is small. We show that the problem is a weighted l-1 minimization that leads to naturally sparse solutions. We point out how known graph learning or construction techniques fall within our framework and propose a new model that performs better than the state of the art in many settings. We present efficient, scalable primal-dual based algorithms for both our model and the previous state of the art, and evaluate their performance on artificial and real data.


Published in:
Journal of Machine Learning Research (JMLR)
Presented at:
The 19th International Conference on Artificial Intelligence and Statistics (AISTATS 2016), Cadiz, Spain, May 9-11, 2016
Year:
2016
Keywords:
Laboratories:




 Record created 2016-01-11, last modified 2018-11-14

Preprint:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)