Signal Recovery on Graphs: Variation Minimization
This work addresses signal recovery for data with complex graph structures, applicable to domains like classification and recommendation systems, but it appears incremental as it extends existing methods to graph contexts.
The paper tackles the problem of recovering smooth graph signals from noisy or incomplete measurements by proposing a graph signal model and formulating it as an optimization problem, with results validated on real-world datasets including blog classification and bridge condition identification.
We consider the problem of signal recovery on graphs as graphs model data with complex structure as signals on a graph. Graph signal recovery implies recovery of one or multiple smooth graph signals from noisy, corrupted, or incomplete measurements. We propose a graph signal model and formulate signal recovery as a corresponding optimization problem. We provide a general solution by using the alternating direction methods of multipliers. We next show how signal inpainting, matrix completion, robust principal component analysis, and anomaly detection all relate to graph signal recovery, and provide corresponding specific solutions and theoretical analysis. Finally, we validate the proposed methods on real-world recovery problems, including online blog classification, bridge condition identification, temperature estimation, recommender system, and expert opinion combination of online blog classification.