A Low-Dimensionality Method for Data-Driven Graph Learning

In many graph signal processing applications, finding the topology of a graph is part of the overall data processing problem rather than a priori knowledge. Most of the approaches to graph topology learning are based on the assumption of graph Laplacian sparsity, with various additional constraints, followed by variations of the edge weights in the graph domain or the eigenvalues in the graph spectral domain. These domains are high-dimensional, since their dimension is at least equal to the order of the number of vertices. In this paper, we propose a numerically efficient method for estimating of the normalized Laplacian through its eigenvalues estimation and by promoting its sparsity. The minimization problem is solved in quite a low-dimensional space, related to the polynomial order of the underlying system on a graph corresponding to the the observed data. The accuracy of the results is tested on numerical example.