학술논문
On the Optimal Recovery of Graph Signals
Document Type
Conference
Author
Source
2023 International Conference on Sampling Theory and Applications (SampTA) Sampling Theory and Applications (SampTA), 2023 International Conference on. :1-5 Jul, 2023
Subject
Language
ISSN
2694-0108
Abstract
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.