Adaptive Graph Signal Processing: Algorithms and Optimal Sampling Strategies
arXiv:1709.03726 · doi:10.1109/TSP.2018.2835384
Abstract
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.
arXiv commentSubmitted to IEEE Transactions on Signal Processing, September 2017
References in corpus (17)
- The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
- Discrete Signal Processing on Graphs
- Discrete Signal Processing on Graphs: Sampling Theory
- Perfect Reconstruction Two-Channel Wavelet Filter-Banks for Graph Structured Data
- Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
- Signals on Graphs: Uncertainty Principle and Sampling
- Parallel and Distributed Methods for Nonconvex Optimization--Part II: Applications
- Sampling of graph signals with successive local aggregations
- Autoregressive Moving Average Graph Filtering
- Compact Support Biorthogonal Wavelet Filterbanks for Arbitrary Undirected Graphs
- Kernel-based Reconstruction of Graph Signals
- Local-set-based Graph Signal Reconstruction
- Greedy Sampling of Graph Signals
- On the Graph Fourier Transform for Directed Graphs
- Adaptive Least Mean Squares Estimation of Graph Signals
- A Distributed Tracking Algorithm for Reconstruction of Graph Signals
- Distributed Adaptive Learning of Graph Signals
Cited by in corpus (15)
- Forecasting Time Series with VARMA Recursions on Graphs
- Low-complexity Graph Sampling with Noise and Signal Reconstruction via Neumann Series
- Online Graph-Adaptive Learning with Scalability and Privacy
- Distributed Training of Graph Convolutional Networks
- Controllability of Bandlimited Graph Processes Over Random Time Varying Graphs
- Graph-signal Reconstruction and Blind Deconvolution for Structured Inputs
- Observing and Tracking Bandlimited Graph Processes
- Graph Normalized-LMP Algorithm for Signal Estimation Under Impulsive Noise
- Node-Adaptive Regularization for Graph Signal Reconstruction
- A Provably Communication-Efficient Asynchronous Distributed Inference Method for Convex and Nonconvex Problems
- Subset Random Sampling and Reconstruction of Finite Time-Vertex Graph Signals
- Online Distributed Learning over Graphs with Multitask Graph-Filter Models
- Methods of Adaptive Signal Processing on Graphs Using Vertex-Time Autoregressive Models
- Bayesian Design of Sampling Set for Bandlimited Graph Signals
- Sampling Policy Design for Tracking Time-Varying Graph Signals with Adaptive Budget Allocation