# Adaptive Graph Signal Processing: Algorithms and Optimal Sampling Strategies

arXiv: https://arxiv.org/abs/1709.03726 · HTML: https://mlsanity.com/paper/1709.03726/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2017.

## Built on by (most cited first, 9 of 9)

- [Sparse Graph Learning from Spatiotemporal Time Series](https://mlsanity.com/paper/2205.13492/) (2022)
- [GSP-KalmanNet: Tracking Graph Signals via Neural-Aided Kalman Filtering](https://mlsanity.com/paper/2311.16602/) (2023)
- [Graph Normalized-LMP Algorithm for Signal Estimation Under Impulsive Noise](https://mlsanity.com/paper/2203.00320/) (2022)
- [Topological Adaptive Least Mean Squares Algorithms over Simplicial Complexes](https://mlsanity.com/paper/2505.23160/) (2025)
- [Learning Graph ARMA Processes from Time-Vertex Spectra](https://mlsanity.com/paper/2302.06887/) (2023)
- [Forecasting Graph Signals with Recursive MIMO Graph Filters](https://mlsanity.com/paper/2210.15258/) (2022)
- [Adaptive Spatio-temporal Estimation on the Graph Edges via Line Graph Transformation](https://mlsanity.com/paper/2311.00656/) (2023)
- [Adaptive Least Mean pth Power Graph Neural Networks](https://mlsanity.com/paper/2405.04111/) (2024)
- [Sheaf-theoretic Signal Processing on Graphs: Spectral Theory, Filtering, and Sampling](https://mlsanity.com/paper/2608.01318/) (2026)

## Abstract (arXiv)

The goal of this paper is to propose novel strategies for adaptive learning of signals defined over graphs, which are observed over a (randomly time-varying) subset of vertices. We recast two classical adaptive algorithms in the graph signal processing framework, namely, the least mean squares (LMS) and the recursive least squares (RLS) adaptive estimation strategies. For both methods, a detailed mean-square analysis illustrates the effect of random sampling on the adaptive reconstruction capability and the steady-state performance. Then, several probabilistic sampling strategies are proposed to design the sampling probability at each node in the graph, with the aim of optimizing the tradeoff between steady-state performance, graph sampling rate, and convergence rate of the adaptive algorithms. Finally, a distributed RLS strategy is derived and is shown to be convergent to its centralized counterpart. Numerical simulations carried out over both synthetic and real data illustrate the good performance of the proposed sampling and reconstruction strategies for (possibly distributed) adaptive learning of signals defined over graphs.