ESTIMATION_PSD - Estimation of the power spectrum density

Description

Authors: Nathanael Perraudin and Pierre Vandergheynst

Date: January 2016

Paper: Stationary signal processing on graphs

Abstract of the paper

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.

This experiment

Figure 1 shows the results of our PSD-estimation algorithm on a \(10\)-nearest neighbors graph of \(20'000\) nodes (sensor type) and only \(1\) signal. We compare the estimation using frames of \(10\), \(20\), \(30\), \(100\) Gaussian filters. \(\sigma\) and \(\tau\) are adapted to the number of filters. For this experiment \(K_2\) is set to \(10\) and the Chebysheff polynomial order is \(30\) (Except for \(M=100\) where we took \(100\)). The estimated curves are smoothed versions of the PSD. Since the original PSD is smooth, the estimation is sufficient to construct approximate Wiener filters. Note that with \(100\) filters, the windows are very concentrated in the spectral domain and broad in the vertex domain. Thus, we loose the averaging effect of the algorithm resulting in a PSD looking like the Fourier transform of the original signal.

Results

PSD estimation on a graph of \(20'000\) nodes with \(1\) measurements. Our algorithm is able to successively estimate the PSD of a signal.

This code produces the following output:

[Warning: MATLAB cannot use OpenGL for printing when started with the '-nodisplay' option.]
[> In inputcheck (line 143)
  In print (line 153)
  In gsp_plotfig (line 86)
  In plotexec (line 154)]