Efficient Recovery of Sparse Graph Signals From Graph Filter Outputs
- 11 November 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 72 (1053587X) , 5550-5566
Abstract
This paper investigates the recovery of a node-domain sparse graph signal from the output of a graph filter. This problem, which is often referred to as the identification of the source of a diffused sparse graph signal, is seminal in the field of graph signal processing (GSP). Sparse graph signals can be used in the modeling of a variety of real-world applications in networks, such as social, biological, and power systems, and enable various GSP tasks, such as graph signal reconstruction, blind deconvolution, and sampling. In this paper, we assume double sparsity of both the graph signal and the graph topology, as well as a low-order graph filter. We propose three algorithms to reconstruct the support set of the input sparse graph signal from the graph filter output samples, leveraging these assumptions and the generalized information criterion (GIC). First, we describe the graph multiple GIC (GM-GIC) method, which is based on partitioning the dictionary elements (graph filter matrix columns) that capture information on the signal into smaller subsets. Then, the local GICs are computed for each subset and aggregated to make a global decision. Second, inspired by the well-known branch and bound (BNB) approach, we develop the graph-based branch and bound GIC (graph-BNBGIC), and incorporate a new tractable heuristic bound tailored to the graph and graph filter characteristics. In addition, we propose the graph-based first order correction (GFOC) method, which improves existing sparse recovery methods by iteratively examining potential improvements to the GIC cost function by replacing elements from the estimated support set with elements from their one-hop neighborhood. Simulations on stochastic block model (SBM) graphs demonstrate that the proposed sparse recovery methods outperform existing techniques in terms of support set recovery and mean-squared-error (MSE), without significant computational overhead. In addition, we investigate the application of our graph-based sparse recovery methods in blind deconvolution scenarios where the graph filter is unknown. Simulations using real-world data from brain networks and pandemic diffusion analysis further demonstrate the superiority of our approach compared to graph blind deconvolution techniques.Keywords
All Related Versions
Funding Information
- Israel Science Foundation (1148/22)
- Jabotinsky Scholarship from the Israel Ministry of Technology and Science
- Israel Ministry of National Infrastructure and Energy
This publication has 73 references indexed in Scilit:
- Multiple-hypothesis testing rules for high-dimensional model selection and sparse-parameter estimationSignal Processing, 2023
- Graph-signal Reconstruction and Blind Deconvolution for Structured InputsSignal Processing, 2021
- A review of stochastic block models and extensions for graph clusteringApplied Network Science, 2019
- Diffusion archeology for diffusion progression history reconstructionKnowledge and Information Systems, 2015
- Projection Matrices2011
- Sparse and Redundant Representations2010
- A systematic analysis of performance measures for classification tasksInformation Processing & Management, 2009
- Emergent network topology at seizure onset in humansEpilepsy Research, 2008
- Using decomposition in large-scale highway network design with a quasi-optimization heuristicTransportation Research Part B: Methodological, 1998
- Exact and approximate algorithms for optimal network designNetworks, 1979