Low-rank Updates in Slowly Time-varying Graphs for Spatial-Temporal Signal Interpolation

In many spatial-temporal applications, such as traffic monitoring or environmental sensing, the underlying graph representing node relationships evolves over time. Standard graph signal processing (GSP) methods often rely on static graphs, which fail to capture these temporal dynamics. This paper addresses the challenge of interpolating missing signal values when both the signal and the underlying graph structure are changing simultaneously.

The authors model the evolution of the graph by assuming that the difference between consecutive adjacency matrices is a low-rank matrix. This allows them to represent complex temporal changes as a sparse combination of outer products of the initial graph's eigenvectors. The joint problem of interpolating the signal and updating the graph is solved through an alternating optimization scheme:

1. Signal Interpolation: With the graph fixed, the signal is estimated by solving a linear system using a graph Laplacian regularizer.
2. Graph Update: With the signal fixed, the adjacency matrix is updated using proximal gradient descent. To ensure computational efficiency, the authors use a fast Orthogonal Matching Pursuit (OMP) algorithm to approximate the low-rank update in linear time, avoiding expensive full eigen-decompositions.

Finally, the authors unroll the iterations of this alternating algorithm into a lightweight neural network, allowing for data-driven tuning of parameters and improved performance in data-starved scenarios.

This approach provides a computationally efficient way to perform signal interpolation on dynamic graphs without requiring the massive datasets typically needed for deep learning models. By explicitly modeling the low-rank nature of graph updates, the method remains interpretable and effective even when observations are sparse, making it highly suitable for real-world applications like predicting farmland valuations or monitoring sensor networks where data collection is limited.