Generalized Laplacian precision matrix estimation for graph signal processing

Graph signal processing models high dimensional data as functions on the vertices of a graph. This theory is constructed upon the interpretation of the eigenvectors of the Laplacian matrix as the Fourier transform for graph signals. We formulate the graph learning problem as a precision matrix estimation with generalized Laplacian constraints, and we propose a new optimization algorithm. Our formulation takes a covariance matrix as input and at each iteration updates one row/column of the precision matrix by solving a non-negative quadratic program. Experiments using synthetic data with generalized Laplacian precision matrix show that our method detects the nonzero entries and it estimates its values more precisely than the graphical Lasso. For texture images we obtain graphs whose edges follow the orientation. We show our graphs are more sparse than the ones obtained using other graph learning methods.

1. Introduction

Graph signal processing (GSP) is a novel framework for analyzing high dimensional data. It models signals as functions on the vertices of a weighted graph, and extends classic signal processing techniques by interpreting the eigenvalues of the graph Laplacian as graph frequencies and the eigenvectors as a Graph Fourier Transform (GFT). Graph structures arise naturally in several domains such as sensor networks [1], brain networks [2], image de-noising [3], and image and video coding [4], [5], [6]. A major challenge in this new field is that of learning the graph structure from data. The learned graph must have a meaningful interpretation and be useful for analysis. Also, the learning algorithm must be efficient and scale nicely as dimensions increase.