News & Events

Deconvolution and Inverse Problems on Graphs with Applications to Source Localization

Chang Ye

Supervised by Gonzalo Mateos

523 Computer Studies Building

Zoom:
https://rochester.zoom.us/j/7718850098?pwd=c0NkMmZ2WUVmbzZWRkduZzFZYTVaUT09

We study a blind deconvolution problem on graphs, which arises in the con- text of localizing a few sources that diffuse over networks. While the observations are bilinear functions of the unknown graph filter coefficients and sparse input signals, a requirement on invertibility of the diffusion filter enables an efficient convex relaxation leading to a linear programming formulation that can be tackled with off-the-shelf solvers. Fundamentally, results in this thesis extend classical blind deconvolution theory and algorithms from temporal and spatial domains to irregular graph structures.

Under a Bernoulli-Gaussian input model, we establish sufficient conditions for exact recovery in the noise-free case and provide stability guarantees ensuring bounded estimation error under small noise perturbations. Numerical experiments on synthetic and real-world networks demonstrate the algorithm’s robustness, highlighting its resilience to noise and the benefits of leveraging multiple signals for blind source localization.

To overcome limitations in prior work requiring perfect knowledge of the graph eigenbasis, we derive stable recovery guarantees under small graphperturbations. Additionally, we introduce a robust, provably convergent algorithm that alternates between blind graph signal deconvolution and eigen- basis denoising within the Stiefel manifold. Numerical tests validate the algorithm’s robustness across various eigenbasis perturbation models.

We further propose a novel, model-based deep learning solution for the inverse problem of network source localization. Rooted in graph signal processing (GSP) principles, the problem reduces to joint (blind) estimation of the forward diffusion filter and sparse input signals encoding source locations. Despite the bilinear nature of observations, requiring filter invertibility enables a convex formulation solvable using the alternating-direction method of multipliers (ADMM). By unrolling and truncating the ADMM iterations, we design a parameterized neural network—SLoG-Net (Source Localization on Graphs)—trained end-to-end on labeled data. This approach combines the interpretability, parameter efficiency, and model-guided bias of GSP with the flexibility of deep learning. Numerical results show that SLoG-Net matches the performance of iterative ADMM but achieves faster inference without manual tuning of step-size or penalty parameters.

Lastly, we develop an online source localization algorithm to process streaming graph signals. By leveraging the bilinear structure of the observations and enforcing filter invertibility, we derive a time-separable convex formulation solved via an online ADMM. Unlike batch algorithms, the proposed lightweight iterations scale efficiently in both computation and memory, regardless of the number of temporal samples. Simulated tests confirm the effectiveness of this online framework for real-time network source localization.