가중치를 갖는 그래프신호를 위한 샘플링 집합 선택 알고리즘

Sampling Set Selection Algorithm for Weighted Graph Signals

그래프신호가 각각의 가중치를 갖고 발생하는 경우 그래프상의 최적의 샘플링 노드집합을 선택하는 탐욕알고리즘에 대해 연구한다. 이를 위해 가중치를 반영한 복원오차를 비용함수로 사용하고 여기에 QR 분해를 적용하여 단순한 형태로 전개한다. 이렇게 도출된 가중치 복원오차를 최소화하기 위해 다양한 수학적 증명을 통해 반복적으로 노드를 선택할 수 있는 수학적 결과식을 유도한다. 이러한 결과식에 기반하여, 노드를 선택하는 샘플링 집합 선택알고리즘을 제안한다. 성능평가를 위해 다양한 그래프에서 발생하는 가중치를 갖는 그래프신호에 적용하여 기존 샘플링 선택 기술대비, 복잡도를 유지하면서 가중치 신호의 복원성능이 우수함을 보인다.

A greedy algorithm is proposed to select a subset of nodes of a graph for bandlimited graph signals in which each signal value is generated with its weight. Since graph signals are weighted, we seek to minimize the weighted reconstruction error which is formulated by using the QR factorization and derive an analytic result to find iteratively the node minimizing the weighted reconstruction error, leading to a simplified iterative selection process. Experiments show that the proposed method achieves a significant performance gain for graph signals with weights on various graphs as compared with the previous novel selection techniques.