임의의 그래프신호를 위한 고속 샘플링 집합 선택 알고리즘

• 영문명: Fast Sampling Set Selection Algorithm for Arbitrary Graph Signals
• 발행기관: 한국전자통신학회
• 저자명: 김윤학(Yoon-Hak Kim)
• 간행물 정보: 『한국전자통신학회 논문지』제15권 제6호, 1023~1029쪽, 전체 7쪽
• 주제분류: 공학 > 전자/정보통신공학
• 파일형태: PDF
• 발행일자: 2020.12.30

국문 초록

임의의 그래프 신호를 복원하기 위해 그래프상의 일부 노드로 구성된 샘플링 집합내의 노드들의 신호값만을 사용하게 되는 경우, 이를 위한 최적의 샘플링 집합 선택 문제에 대해 연구한다. 고도의 계산량을 요구하는 고유값 분해 (eigen decomposition)를 사용하지 않고, 노드를 선택하는 과정에서의 신호 변화값의 차이를 비용함수로 제시한다. 구체적으로, 기존 방식의 비용함수인 신호 복원오차를 최소화하는 대신에 본 연구에서는 신호 변화값의 차이를 비용함수로 채택하여 이를 최소화하는 간단하고 고속의 탐욕 (greedy) 샘플링 집합 선택 알고리즘을 제안한다. 기존의 고속알고리즘과 성능평가 비교를 위해 다양한 그래프 신호에 대한 폭넓은 실험을 진행하여, 기존 방식 대비 신호복원 성능감소를 약 7% 이내로 유지하면서 실행시간을 10배이상으로 단축하였음을 보인다.

영문 초록

We address the sampling set selection problem for arbitrary graph signals such that the original graph signal is reconstructed from the signal values on the nodes in the sampling set. We introduce a variation difference as a new indirect metric that measures the error of signal variations caused by sampling process without resorting to the eigen-decomposition which requires a huge computational cost. Instead of directly minimizing the reconstruction error, we propose a simple and fast greedy selection algorithm that minimizes the variation difference at each iteration and justify the proposed reasoning by showing that the principle used in the proposed process is similar to that in the previous novel technique. We run experiments to show that the proposed method yields a competitive reconstruction performance with a substantially reduced complexity for various graphs as compared with the previous selection methods.

목차

Ⅰ. Introduction

Ⅱ. Problem Formulation

Ⅲ. Fast sampling set selection

Ⅳ. Discussion of Proposed principle

Ⅴ. Simulation results

Ⅵ. Conclusion

References

키워드

그래프 신호 처리 샘플링 집합 선택 탐욕 알고리즘 신호 변화 신호 복원 Graph Signal Processing Sampling Set Selection Greedy Algorithm Signal Variation Signal Reconstruction