Adaptive filtering algorithms and data-selective strategies for graph signal estimation

Abstract

Considering the potential of graph signal processing (GSP), a recent research field that extends classical signal processing to signals defined over graph structures, this dissertation explores and proposes new algorithms to a GSP problem that has been lately recast within the adaptive filtering framework. After presenting an overview of both adaptive filtering and GSP, this work highlights the merging of these areas when algorithms based on the least-mean-square (LMS) and recursive least-squares (RLS) methods are used for the online estimation of bandlimited graph signals (GS) using a reduced number of noisy measurements. Extending this idea, this dissertation proposes a normalized least-mean-square (NLMS) algorithm for the same GSP context. As in the classical adaptive filtering framework, the resulting NLMS GS estimation technique is faster than the LMS algorithm while being less complex than the RLS algorithm. Detailed steady-state mean-squared error and deviation analyses are provided for the proposed NLMS algorithm, and are also employed to complement previous results on the LMS and RLS algorithms. Additionally, two different data-selective (DS) strategies are pro- posed to reduce the overall computational complexity by only performing updates when the input signal brings enough innovation. Proper definitions of constraint pa- rameters are given based on the analysis of these DS strategies, and closed formulas are derived for an estimate of the update probability when using different adaptive algorithms. At last, this work presents many numerical simulations corroborating, with high accuracy, the theoretical results predicted.