.png){kind=icon}
.png){kind=icon}
Return
Parallel Graph Signal Processing: Sampling and Reconstruction
.png){kind=icon}
PRE
AI
DOI：10.1109/TSIPN.2023.3261504.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Graph signal processing (GSP) extends classical signal processing methods to analyzing signals supported over irregular grids represented by graphs. Within the scope of GSP, sampling and reconstruction represent fundamental tools that have received considerable attention. For very large graphs, however, many of the current methods struggle with the computational and memory requirements. Vertex domain and randomized sampling strategies somewhat ameliorate the computational requirements, but these algorithms perform poorly at preserving signal fidelity for graphs with hundreds of thousands of vertices. To address these shortcomings, this article introduces a new and scalable approach that can be easily parallelized. This new approach uses existing graph partitioning algorithms in concert with vertex-domain blue-noise sampling and reconstruction, performed independently across partitions. In the reconstruction, some degree of overlapping is added to the partitions to induce trans-partition smoothness in the recovered signal. We also propose two sampling schemes based on the spatial characteristic of the graph that minimizes the recovery error. The first combines graph partitioning with the Void-and-Cluster algorithm, while the second approach uses Error Diffusion. We conclude this article with experiments on synthetic and real data that show the effectiveness of these new approaches on very large graphs.
Keywords:
Partitioning algorithms
Approximation algorithms
Signal processing algorithms
Signal processing
Laplace equations
Information processing
Parallel processing
Graph signal reconstruction
blue-noise
graph signal sampling
graph signal processing
Journal
IF:
4.9
Papers:
726
Citations:
1.9K