Sampling of graph signals via randomized local aggregations
Sampling of signals defined over the nodes of a graph is one of the crucial problems in graph signal processing, whereas in classical signal processing, sampling is a well-defined operation; when we consider a graph signal, many new challenges arise and defining an efficient sampling strategy is not straightforward. Recently, several works have addressed this problem. The most common techniques select a subset of nodes to reconstruct the entire signal. However, such methods often require the knowledge of the signal support and the computation of the sparsity basis before sampling. Instead, in this paper, we propose a new approach to this issue. We introduce a novel technique that combines localized sampling with compressed sensing. We first choose a subset of nodes and then, for each node of the subset, we compute random linear combinations of signal coefficients localized at the node itself and its neighborhood. The proposed method provides theoretical guarantees in terms of reconstruction and stability to noise for any graph and any orthonormal basis, even when the support is not known.
Code available at https://github.com/diegovalsesia/randomized-local-aggregations
Sampling Graph Signals
- Representing a graph signal with few measurements
- Regularity/Low-dimensionality priors enable reconstruction (e.g. sparse support in a transform domain)
- Locality of the sampling operation is important
- Pointwise sampling: observing the signal value at certain nodes
- Aggregation sampling: observing an aggregate of the signal values over a neighborhood
Randomized Local Aggregations
We know from Compressed Sensing that random projections can be used to acquire a compressed representation of a signal. Measurements acquired using Gaussian random projections enable reconstruction of signals sparse in an orthonormal basis. Reconstruction guarantees are provable if the sampling matrix satisfies the Restricted Isometry Property (RIP).
Issue: this sampling method is not localized if there is an underlying graph. It would require global communications throughout the graph.
Solution: randomized local aggregations.
- Define a sampling set R
- Aggregate the signal values in each neighborhood taking a linear combination with random weights
- This is equivalent to having a sparse random sampling matrix with the same sparsity pattern as the adjacency matrix of the graph
How to choose the sampling set? A sufficient condition…
- Choose R to be a superset of a dominating set of the graph
- If the dominating set is larger than the desired number of measurements: use multi-hop aggregations instead of a single-hop
- If the dominating set is smaller than the desired number of measurements:
- either draw a new set of random coefficients to compute a new measurement for some nodes of the domination set
- or select some more nodes not previously chosen
- RIP ensures reconstruction with unknown support and stability to noise (provided enough measurements)
- Good performance without complex optimization of the node sampling set as in some pointwise sampling algorithms. Reconstruction with known signal support with noise:
- It can also deal with unknown signal support:
Sampling graph signals with randomized local aggregations:
- localized aggregation sampling method for graph signals;
- theoretical guarantees of perfect reconstruction with known and unknown support;
- stable in presence of noise
- does not require transform basis (e.g. GFT) at sampling time