How to learn a graph from smooth signals

01/11/2016
by   Vassilis Kalofolias, et al.
0

We propose a framework that learns the graph structure underlying a set of smooth signals. Given X∈R^m× n whose rows reside on the vertices of an unknown graph, we learn the edge weights w∈R_+^m(m-1)/2 under the smoothness assumption that trX^ LX is small. We show that the problem is a weighted ℓ-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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset