On the Optimal Recovery of Graph Signals
This work addresses hyperparameter selection in graph-based machine learning, providing incremental improvements for researchers in graph signal processing.
The paper tackles the problem of learning smooth graph signals from partial observations by computing optimal or near-optimal regularization parameters within the optimal recovery framework, offering new interpretations for classical techniques and insights for hyperparameter selection.
Learning a smooth graph signal from partially observed data is a well-studied task in graph-based machine learning. We consider this task from the perspective of optimal recovery, a mathematical framework for learning a function from observational data that adopts a worst-case perspective tied to model assumptions on the function to be learned. Earlier work in the optimal recovery literature has shown that minimizing a regularized objective produces optimal solutions for a general class of problems, but did not fully identify the regularization parameter. Our main contribution provides a way to compute regularization parameters that are optimal or near-optimal (depending on the setting), specifically for graph signal processing problems. Our results offer a new interpretation for classical optimization techniques in graph-based learning and also come with new insights for hyperparameter selection. We illustrate the potential of our methods in numerical experiments on several semi-synthetic graph signal processing datasets.