Smooth graph signal processing: recovery and sampling schemes

Abstract

The amounts of data collected by automated software and hardware in various domains, such as social networks, bioinformatics and wireless sensor networks, are exploding. Beside the sheer volume of these data-sets also the high velocity (rate of generation) and their variety (data composed of mixture of audio video text, only partially labeled) pose big challenges on their processing. A particular useful methodology to cope with big data is provided by graph signal processing (GSP), which models data-sets as signals defined over large graphs (complex networks). The usage of graph models within GSP entails efficient distributed message passing algorithms that are well suited to deal with large volumes of high-speed data. Moreover, graphs allow to organize heterogeneous data by exploiting application specific notions of similarity, thereby addressing the variety of big data. A key problem studied in GSP is the recovery of a graph signal from its noisy samples at few selected nodes. This problem is relevant, e.g., for semi-supervised learning over graphs, where only few training examples (represented by graph nodes) are labeled and most examples are unlabeled. The problem of determining the labels for the unlabeled data is precisely a graph signal recovery problem. The recovery is feasible for the graph signals which are smooth with respect to the graph. In this work, we investigate the problem of recovering a graph signal from the noisy samples observed at a small number of randomly selected nodes. The signal recovery is formulated as a convex optimization problem. Our approaches exploit the smoothness of typical graph signals occurring in many applications, such as wireless sensor networks or social network analysis. The graph signals are smooth in the sense that the neighboring nodes have similar signal values. In particular, we propose various graph signal recovery methods, which are shown to be particularly well suited for smooth graph signal recovery. Besides, in this dissertation we present a novel and flexible sampling method for signals that are supported on either directed or undirected graphs. The proposed sampling algorithm selects the optimal sampling set from the set of arbitrary weighted graph signal, for any predefined sampling rate, such that the reconstruction (recovery) quality is as high as possible. The algorithm is able to be adaptively adjusted based on the structure of the underlying graph and signal model such as nodes degree and smoothness. The effectiveness of the proposed recovery and sampling methods is verified by numerical experiments on various random graphs along with a real-world data-set. Numerical evaluations show that the proposed algorithms render a highly efficient performance compared to the state-of-the-art methods.