RRP - Stationary signal processing on graphs

Abstract

Graphs are a central tool in machine learning and information processing as they allow to conveniently capture the structure of complex datasets. In this context, it is of high importance to develop flexible models of signals defined over graphs or networks. In this paper, we generalize the traditional concept of wide sense stationarity to signals defined over the vertices of arbitrary weighted undirected graphs. We show that stationarity is intimately linked to statistical invariance under a localization operator reminiscent of translation. We prove that stationary signals are characterized by a well-defined Power Spectral Density that can be efficiently estimated even for large graphs. We leverage this new concept to derive Wiener-type estimation procedures of noisy and partially observed signals and illustrate the performance of this new model for denoising and regression.

Authors: Nathanael Perraudin and Pierre Vandergheynst

Date: January 2016

Contents

Figures of the paper

• estimation_psd - Estimation of the power spectrum density
• estimation_psd_scalability - Study the scalability of the PSD estimation method
• demo_generate_samples - Generation of USPS digit
• synthetic_wiener_deconvolution - Wiener deconvolution experiment on a synthetic dataset
• synthetic_wiener_inpainting - Wiener inpainting experiment on a synthetic dataset
• experiment_molene_humidity - In-painting on the Molene humidity dataset
• experiment_molene_temperature - In-painting on the Molene temperature dataset
• experiment_usps_inpainting - In-painting on the USPS dataset
• experiment_orl_inpainting - In-painting on the USPS dataset

Functions

• gsp_experimental_psd - Experimental power density function
• gsp_design_translates - Create a filterbank by uniformly translating a window
• gsp_stationarity_cov - Covariance matrix from graph stationary data
• gsp_stationarity_ratio - Assert the stationarity level of some data
• gsp_psd_estimation - Estimation of the Power spectrum density
• gsp_wiener_optimization - Solve wiener optimization problem
• gsp_wiener_l2 - Solve wiener optimization problem with l2 fidelity term
• gsp_wiener_inpainting - Solve wiener in-painting problem

For help, bug reports, suggestions etc. please send email to nathanael (dot) perraudin (at) epfl (dot) ch