SIGNAL INPAINTING ON GRAPHS VIA TOTAL VARIATION MINIMIZATION

We propose a novel recovery algorithm for signals with com-plex, irregular structure that is commonly represented by graphs. Our approach is a generalization of the signal inpaint-ing technique from classical signal processing. We formulate corresponding minimization problems and demonstrate that in many cases they have closed-form solutions. We discuss a relation of the proposed approach to regression, provide an upper bound on the error for our algorithm and compare the proposed technique with other existing algorithms on real-world datasets. Index Terms — Signal processing on graphs, signal in-painting, total variation, semi-supervised learning. 1