Reconstruction of graph signals: Percolation from a single seeding node

Schemes to reconstruct signals defined in the nodes of a graph are proposed. Our focus is on reconstructing bandlimited graph signals, which are signals that admit a sparse representation in a frequency domain related to the structure of the graph. The schemes, which are designed within the framework of linear shift-invariant graph filters, consider that the signal is injected at a single seeding node. After several sequential applications of the graph-shift operator - which computes linear combinations of the information available at neighboring nodes - the seeding signal percolates across the graph. We show that if the node is allowed to change the seeding signal with each application of the shift operator, the original bandlimited signal can be recovered. Conditions under which such a recovery is feasible are identified for two different reconstruction schemes. We illustrate both reconstruction schemes in synthetic graph signals and we analyze their performance in noisy real-world scenarios.