임계값 적용에 기반한 저 복잡도 그래프 신호 샘플링 알고리즘

• 영문명: Low-Complexity Graph Sampling Algorithm Based on Thresholding
• 발행기관: 한국전자통신학회
• 저자명: 김윤학
• 간행물 정보: 『한국전자통신학회 논문지』제18권 제5호, 895~900쪽, 전체 6쪽
• 주제분류: 공학 > 전자/정보통신공학
• 파일형태: PDF
• 발행일자: 2023.10.31

국문 초록

그래프에서 전체 노드중 일부 노드를 선택하고 선택된 노드에서 발생하는 신호로부터 원 신호를 복원하는 저 복잡도를 갖는 샘플링 기술에 대해 연구한다. 이를 위해, 매 단계에서 한 개의 노드를 선택하는 탐욕 알고리즘을 기반으로, 기존의 방식인 최소 비용값을 갖는 노드를 찾기 위해 전체노드를 탐색 및 계산하는 방식을 취하지 않고 임계값을 설정하여 임계값 이하의 값을 갖는 노드를 선택하도록 하여 탐색 및 비용함수 계산비용을 줄이는 방식을 제안한다. 복원성능 저하를 막기 위해 정확한 임계값 설정이 요구되며, 이를 위해 임계값을 구하기 위한 매 단계에서 샘플링 집합 크기와의 관계식을 정립한다. 다양한 그래프상에서 복원성능 및 복잡도 (실행시간) 평가를 수행하여, 기존 방식 대비 복원성능을 유지하면서 평균 1.3배 이상 빠른 실행시간이 보임을 확인했다.

영문 초록

We study low-complexity graph sampling which selects a subset of nodes from graph nodes so as to reconstruct the original signal from the sampled one. To achieve complexity reduction, we propose a graph sampling algorithm with thresholding which selects a node with a cost lower than a given threshold at each step without fully searching all of the remaining nodes to find one with the minimum cost. Since it is important to find the threshold as close to a minimum cost as possible to avoid degradation of the reconstruction performance, we present a mathematical expression to compute the threshold at each step. We investigate the performance of the different sampling methods for various graphs, showing that the proposed algorithm runs 1.3 times faster than the previous method while maintaining the reconstruction performance.

목차

Ⅰ. 서론

Ⅱ. 문제정립

Ⅲ. 저 복잡도 샘플링 알고리즘

Ⅳ. 실험 및 분석

Ⅴ. 결론

References

키워드

그래프 신호 처리 그래프 샘플링 탐욕 알고리즘 임계값 적용 Graph Signal Processing Graph Sampling Greedy Algorithm Thresholding