Spectrum-blind signal recovery on graphs

We consider the problem of recovering a graph signal, sparse in the graph spectral domain from a few number of samples. In contrast to most previous work on the sampling of graph signals, the setting is “spectrum-blind” where we are unaware of the graph d support of the signal. We propose a class of spectrum-blind graph signals and study two recovery strategies based on random and experimentally designed sampling inspired by the compressed sensing paradigm. We further show sampling bounds for graphs, including Erdös-Rényi random graphs. We show that experimentally designed sampling significantly outperforms random sampling for some irregular graph families.

I. Introduction

With the explosive growth of information and communication, signals are generated at an unprecedented rate from various sources, including social, citation, biological, and physical infrastructure [1], [2], among others.