Low-complexity Sampling Set Selection for Bandlimited Graph Signals

김윤학,Kim, Yoon Hak The Korea Institute of Information and Commucation 2020 한국정보통신학회논문지 Vol.24 No.12

대역폭 제한 그래프신호의 신호복원을 위해서 최대의 정보를 제공하기 위한 그래프 상의 노드를 선택하는 샘플링 집합 선택 알고리즘에 대해 연구한다. 저 복잡도 선택알고리즘을 구현하기 위해 직접적인 비용함수인 신호 복원오차를 최소화 하는 대신, 신호 복원오차의 최대값을 최소화하는 방법에 대해 집중한다, 이를 위해, 추가적인 복잡도 개선을 위해 유용한 근사화공식을 적용하여 성능손실을 최소화하면서 복잡도를 개선한 저 복잡도 탐욕알고리즘을 제안한다. 다양한 그래프신호에 대한 폭넓은 실험을 통해, 기존 저 복잡도 방식과 신호복원성능 및 복잡도를 평가 비교하여 기존방식대비 신호복원 및 복잡도면에서 모두 성능 개선이 있음을 보였으며, 이는 실시간 응용분야에서 실용적인 해결방식으로써 경쟁력 있는 대안을 제시한다. We study the problem of sampling a subset of nodes of graphs for bandlimited graph signals such that the signal values on the sampled nodes provide the most information in order to reconstruct the original graph signal. Instead of directly minimizing the reconstruction error, we focus on minimizing the upper bound of the reconstruction error to reduce the complexity of the selection process. We further simplify the upper bound by applying useful approximations to propose a low-weight greedy selection process that is iteratively conducted to find a suboptimal sampling set. Through the extensive experiments for various graphs, we inspect the performance of the proposed algorithm by comparing with different sampling set selection methods and show that the proposed technique runs fast while preserving a competitive reconstruction performance, yielding a practical solution to real-time applications.

상호동료교수법을 활용한 교대해부실습이 해부실습 시험 성적에 미치는 영향

김윤학(Yun Hak Kim),홍창완(Changwan Hong),오세옥(Sae-Ock Oh),윤식(Sik Yoon),김민정(Min Jeong Kim),주성일(Sungil Ju),윤소정(So Jung Yune),백선용(Sunyong Baek) 대한체질인류학회 2018 해부·생물인류학 (Anat Biol Anthropol) Vol.31 No.3

의학교육과정의 개편으로 해부학 강의 시간이 감소하면서 학생들이 참여하는 해부실습 시간을 보다 효율적 활용할 수 있는 교수 전략에 대한 관심이 높아지고 있다. 본 연구의 목적은 상호동료교수법을 활용한 교대해부실습(alternating dissection)이 실습시험 성적에 미치는 영향을 분석하는 것이다. 의과대학 의학과 1학년 학생을 가나다 순서로 각 실습대에 8~9명씩을 배정하였다. 각 조원을 다시 A조와 B조로 나누어 해부조와 관찰조로 분류하여 번갈아 가면서 해부실습을 진행하였다. 해부를 하지 않는 관찰조는 팀바탕학습을 기반으로 하는 자기주도학습을 실시하고, 당일의 해부를 마치면 해부조는 관찰조에게 동료가르침을 하였다. 새로운 실습방법과 전통적 실습방법에 따른 실습시험 성적은 유의한 차이를 보이지 않았으며, 교대해부실습에서 A조와 B조 사이의 실습시험 성적도 유의한 차이를 보이지 않았다. 그러나 부위에 따른 문항 분석에서 직접 해부한 부위에 해당하는 문항의 정답률이 관찰한 부위에 해당하는 문항의 정답률에 비해 유의하게 높았다. 정답률에서 유의한 차이를 보이는 문항은 전체 86개 문항 중에서 9개 문항이었다. 결론적으로, 의과대학 1학년 학생의 해부실습에서 상호동료교수법을 활용한 교대해부실습의 효용성을 확인하였다. The reformation of medical curriculum induced the reduction of anatomy course schedule especially in contact hours in anatomy laboratory. It has led to the use of more efficient teaching approaches in anatomy laboratory. The purpose of this work provide a detailed analysis of alternating dissections with reciprocal peer teaching in anatomy laboratory. Students were assigned alphabetically, in teams of eight or nine, to each dissecting table. The team was subdivided into two groups, A and B, each group dissected every other session. Students excused from dissection spent their time with team-based learning and self-directed learning. Dissected peer-teaching groups presented structures from the dissection to groups absent during dissection. Practical exam scores of the alternating dissection indicated no significant difference with those of classical dissection of previous year. Subgroup analysis of practical exam scores in alternating dissection was also no significant difference between group A and B. Assessment of question types showed that correction rates of questions in the dissected region was significantly higher on dissection group assignment. There were 9 questions (out of 86) in which there was a significant difference in correction rates between A and B groups. In conclusion, the laboratory paradigm of alternating dissection with reciprocal peer teaching demonstrated an effective method of learning gross anatomy laboratory for first year medical students.

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

김윤학(Yoon-Hak Kim) 한국전자통신학회 2020 한국전자통신학회 논문지 Vol.15 No.6

임의의 그래프 신호를 복원하기 위해 그래프상의 일부 노드로 구성된 샘플링 집합내의 노드들의 신호값만을 사용하게 되는 경우, 이를 위한 최적의 샘플링 집합 선택 문제에 대해 연구한다. 고도의 계산량을 요구하는 고유값 분해 (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.

저 복잡도를 갖는 효율적인 그래프 신호의 샘플링 알고리즘

김윤학(Yoon Hak Kim) 한국전자통신학회 2022 한국전자통신학회 논문지 Vol.17 No.2

그래프 노드상에서 발생하는 그래프 신호의 일부를 선택해서 만든 샘플링 신호로부터 원신호를 복원하기 위해, 복원오차를 최소화하기 위한 최적의 샘플링 집합을 선택하는 알고리즘에 관해 연구한다. 복잡도 개선을 위해 복원오차를 직접적으로 최소화하는 대신에, 복원오차의 상한값을 비용함수로 사용하고, QR분해 적용을 통해 발생하는 상삼각행렬의 대각선상에 위치하는 값으로 샘플링을 결정할 수 있게 하는, 저 복잡도를 갖는 반복적 탐욕알고리즘을 제안한다. 기존의 샘플링 선택 방법과 비교하여, 제안 알고리즘이 복원 성능 저하를 평균 5%미만으로 유지하면서, 약 3.5배 빠른 실행시간을 보임을 다양한 그래프 상황에서 실험을 통해 확인한다. A sampling set selection algorithm is proposed to reconstruct original graph signals from the sampled signals generated on the nodes in the sampling set. Instead of directly minimizing the reconstruction error, we focus on minimizing the upper bound on the reconstruction error to reduce the algorithm complexity. The metric is manipulated by using QR factorization to produce the upper triangular matrix and the analytic result is presented to enable a greedy selection of the next nodes at iterations by using the diagonal entries of the upper triangular matrix, leading to an efficient sampling process with reduced complexity. We run experiments for various graphs to demonstrate a competitive reconstruction performance of the proposed algorithm while offering the execution time about 3.5 times faster than one of the previous selection methods.

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

김윤학(Yoon-Hak Kim) 한국전자통신학회 2023 한국전자통신학회 논문지 Vol.18 No.5

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

시퀀스 기반 위치추정 시스템을 위한 효율적 노드배치 알고리즘

박현홍,김윤학,Park, Hyun Hong,Kim, Yoon Hak 한국전기전자학회 2018 전기전자학회논문지 Vol.22 No.3

본 논문에서는 실내 위치 추정시스템에 주로 사용되는 시퀀스 기반 위치추정(Sequence-Based Localization, SBL) 알고리즘의 성능향상을 위한 노드배치 알고리즘에 대해 연구한다. 기존의 노드선택 또는 배치알고리즘은 다수의 타겟이 위치하는 공간의 중심값에 노드들을 위치시켜 성능향상을 이루는 반면, SBL에서는 위치추적 알고리즘 특성상 타겟을 에워싸는 공간에서의 노드배치가 효율적일 수 있음에 주목한다. 이를 실현하기 위해 K-means clustering 알고리즘을 통한 노드배치 가능 공간을 선정하고, 그 선정된 공간상의 효율적 노드위치를 찾기 위해 2분법을 활용하여, 설계 복잡도가 낮은 노드배치 알고리즘을 제시한다. 제안된 노드배치알고리즘은 다양한 모의실험을 통해 무작위 노드배치 알고리즘 대비 뛰어난 위치추정성능을 보여주며, 노드위치를 위한 전역탐색 (full search)과 비교하여, 상당히 낮은 설계복잡도를 유지하면서도 만족할 만한 성능을 보인다. In this paper, we consider node deployment algorithms for the sequence-based localization (SBL) which is recently employed for in-door positioning systems, Whereas previous node selection or deployment algorithms seek to place nodes at centrold of the region where more targets are likely to be found, we observe that the boundaries dividing such regions can be good locations for the nodes in SBL systems. Motivated by this observation, we propose an efficient node deployment algorithm that determines the boundaries by using the well-known K-means algorithm and find the potential node locations based on the bi-section method for low-complexity design. We demonstrate through experiments that the proposed algorithm achieves significant localization performance over random node allocation with a substantially reduced complexity as compared with a full search.

시퀀스 기반 위치추정 시스템을 위한 효율적인 양자기 설계 알고리즘

박현홍(Hyun Hong Park),김윤학(Yoon Hak Kim) 한국전기전자학회 2020 전기전자학회논문지 Vol.24 No.1

본 논문에서는 실내 위치 추정 시스템에서 우수한 성능을 보이는 시퀀스 기반 위치추정(Sequence-Based Localization, SBL) 시스템을 위한 효율적인 양자기 설계 알고리즘에 대해 연구한다. SBL 시스템에서는 목표물 위치공간을 다수개의 영역으로 나누고, 각각의 영역에 고유 시퀀스 번호를 할당해서 위치추정이 수행이 되며, 본 연구에서는 이러한 시스템의 위치추정 방식의 특성을 고려하여 노드와 각 고유 시퀀스간의 거리를 양자기 설계를 위한 샘플로 활용하는 방식을 제안하고 이를 통해 기존기술대비, 복잡도를 혁신적으로 개선됨을 보인다, 또한 성능향상을 위해 SBL 시스템에 특화된 새로운 비용함수를 제시하고 이를 최소화하기 위한 최적의 양자화영역 및 코드워드 검색을 통해 기존 양자기 비해 월등한 성능향상을 이룰 수 있음을 다양한 실험조건을 통해 입증한다. In this paper, we consider an efficient design of quantizers at sensor nodes for sequence-based localization (SBL) systems which recently show a competitive performance for in-door positioning, Since SBL systems locate targets by partitioning the sensor field into subregions, each with an unique sequence number, we use the distance samples between sensors and the sequences for quantizer design in order to propose a low weight design process. Furthermore, we present a new cost function devised to assign the number of samples and the number of unique sequences uniformly into each of quantization partitions and design quantizers by searching the quantization partitions and codewords that minimize the cost function. We finally conduct experiments to demonstrate that the proposed algorithm offers an outstanding localization performance over typical designs while maintaining a substantial reduction of design complexity.