Scholarlink

<p>Graph signal processing (GSP) is a powerful tool for handling data located on graph nodes. The primary challenge in GSP is graph signal sampling, which entails selecting the optimal subset of vertices to recover missing values at other graph points from noisy samples. Among existing methods, the binary search with Gershgorin Disc Alignment (GDA) sampling algorithm, which employs graph Laplacian regularization (GLR) and operates without eigendecomposition (ED), is computationally efficient and significantly faster than other schemes. However, it is only practical for small graphs. In this paper, we propose an extended GDA (EGDA) to enhance the performance of the GDA sampling scheme for large graphs by applying partitioning and sparsification techniques to these graphs. First, we convert the original large graph into small connected induced subgraphs in the partitioning step. Second, we make each induced subgraph sparse in the sparsification step while maintaining the graph connectivity. By applying the GDA algorithm to the sparsified graph and independently to the connected induced subgraphs for each partition, we demonstrate that the EGDA method surpasses the GDA algorithm, achieving higher reconstruction accuracy and lower computational complexity.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Enhancing graph signal sampling through gershgorin disk alignment: A heuristic approach

  • 期刊论文

  • 发表日期：

    2025年9月22日

查看全文
  • Mahdieh Sadeghian,
  • Mohammadreza Fattahi,
  • Hamid Saeedi-Sourck

摘要

Graph signal processing (GSP) is a powerful tool for handling data located on graph nodes. The primary challenge in GSP is graph signal sampling, which entails selecting the optimal subset of vertices to recover missing values at other graph points from noisy samples. Among existing methods, the binary search with Gershgorin Disc Alignment (GDA) sampling algorithm, which employs graph Laplacian regularization (GLR) and operates without eigendecomposition (ED), is computationally efficient and significantly faster than other schemes. However, it is only practical for small graphs. In this paper, we propose an extended GDA (EGDA) to enhance the performance of the GDA sampling scheme for large graphs by applying partitioning and sparsification techniques to these graphs. First, we convert the original large graph into small connected induced subgraphs in the partitioning step. Second, we make each induced subgraph sparse in the sparsification step while maintaining the graph connectivity. By applying the GDA algorithm to the sparsified graph and independently to the connected induced subgraphs for each partition, we demonstrate that the EGDA method surpasses the GDA algorithm, achieving higher reconstruction accuracy and lower computational complexity.