2024/05/17 by Gal Morgenstern, Tirza Routtenberg, Morgenstern, Gal +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Social Sciences · #Advanced Computing and Algorithms #Advanced Graph Neural Networks #FOS: Electrical engineering #FOS: Mathematics #Gene expression and cancer classification #Optimization and Control (math.OC) #Signal Processing (eess.SP) #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2405.10649
openalex publication_date 2024/05/17 · openalex created_date 2024/05/21 · openalex updated_date 2026/07/28
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-BNB-GIC), 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. In addition, we investigate the application of our graph-based sparse recovery methods in blind deconvolution scenarios where the graph filter is unknown.