[논문]Support 검출을 통한 reweighted L1-최소화 알고리즘

이혁; 권석법; 심병효

Support 검출을 통한 reweighted L1-최소화 알고리즘
Reweighted L1-Minimization via Support Detection 원문보기

電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. SP, 신호처리, v.48 no.2 = no.338, 2011년, pp.134 - 140

이혁 (고려대학교 컴퓨터.전파통신공학과) , 권석법 (고려대학교 컴퓨터.전파통신공학과) , 심병효 (고려대학교 컴퓨터.전파통신공학과)

초록
AI-Helper

압축 센싱 (Compressed Sensing) 기술을 통해 $M{\times}N$ 측정 행렬의 원소들이 특정의 독립적인 확률 분포에서 뽑혀 identically 분포의 성질을 가지고 있을 때 $M{\ll}N$의 경우에도 스파스 (sparse) 신호를 높은 확률로 정확하게 복원할 수 있다. $L_1$-최소화 알고리즘이 불완전한 측정에 대해서도 스파스 (sparse) 신호를 복원할 수 있다는 것은 잘 알려진 사실이다. 본 논문에서는 OMP를 변형시킨 support 검출과 가중치 기법을 이용한 $L_1$-최소화 방법을 통하여 스파스 (sparse) 신호의 복원 성능을 향상시키는 알고리즘을 제안하고자 한다.

Abstract ▼ AI-Helper

Recent work in compressed sensing theory shows that $M{\times}N$ independent and identically distributed sensing matrix whose entries are drawn independently from certain probability distributions guarantee exact recovery of a sparse signal with high probability even if $M{\ll}N$. In particular, it is well understood that the $L_1$-minimization algorithm is able to recover sparse signals from incomplete measurements. In this paper, we propose a novel sparse signal reconstruction method that is based on the reweighted $L_1$-minimization via support detection.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 압축 센싱 기술을 통해 스파스 신호를 복원하는 reweighted L₁-최소화 알고리즘을 제안하였다. 벡터의 L₀-norm과 L₁-norm은 원소의 절대값이 커질수록 차이가 커지며, 이 사실로부터 support에 해당하는 인덱스에 작은 가중치를 주는 방식인 reweighted L₁-norm 통하여 L₀-norm과의 차이를 줄일 수 있었다.
실험의 목적은 스파스 신호를 복원하기 위해 필요한 측정값의 개수를 제안된 알고리즘을 통해 줄일 수 있음을 보여주는 것이다. 본 실험에서는 제안하는 기법과 기존에 알려진 matching pursuit (MP), unweighted L₁-최소화, OMP, L1MAGIC 알고리즘간의 성능을 비교하였다.

가설 설정

복원 하고자 하는 원 신호 x의 원소 중 영 아닌 값의 개수가 K이고 나머지 (N - K)개의 값이 영이라고 가정하자. 이 경우 측정 벡터 y는 Φ의 K개의 열들의 선형 조합으로 표현 될 수 있다.

제안 방법

본 논문에서는 영 아닌 원소의 인덱스 집합 (이하 support로 표현) 검출을 통하여 사전에 절대값의 크기가 큰 원소에 작은 가중치를 주어 L₀-최소화 알고리즘과 유사한 복원 성능을 얻을 수 있는 알고리즘 (이하 reweighted L₁-최소화)을 제안한다. 또한 절대값의 크기가 클 것으로 예상되는 원소 위치를 추정하기 위하여 개선된 orthogonal matching pursuit (OMP) 알고리즘을 이용한다.
실험의 목적은 스파스 신호를 복원하기 위해 필요한 측정값의 개수를 제안된 알고리즘을 통해 줄일 수 있음을 보여주는 것이다. 본 실험에서는 제안하는 기법과 기존에 알려진 matching pursuit (MP), unweighted L₁-최소화, OMP, L1MAGIC 알고리즘간의 성능을 비교하였다. 성능 척도로는 최소 제곱 오차를 사용하였으며, 성긴 정도 (sparsity)의 변화에 따라 성능을 확인해 보았다.
본 연구에서 수행한 모든 시뮬레이션은 Microsoft Windows XP 기반의 PC (Intel Core 2 Duo CPU 2.3 GHz, RAM 3 GB)에서 수행되었으며, MATLAB 프로그램으로 구현되었다.
본 연구에서는 support 검출 성능을 높이기 위하여 사전 인덱스 정보를 이용하도록 OMP 알고리즘을 변형한다. 표 1의 Step 5에 나타나는 최소 제곱 (least squares) 문제를 풀기 위해서 측정 행렬 Φ 중에 사전 인덱스 정보와 반복 과정에서 새롭게 선택된 support에 해당하는 열을 함께 사용하며, 다음의 최소 제곱 문제를 통하여 신호를 추정할 수 있다.
두말 할 나위없이 본 방식의 효과를 보장하기 위해서는 정확한 support 정보가 필수적이다. 본 연구에서는 support 검출의 정확도를 높이기 위하여 현재 추정되는 support와 사전에 선택된 상관성이 높은 열(column)의 위치를 함께 이용하는 방식으로 OMP를 변형하였다.
본 실험에서는 제안하는 기법과 기존에 알려진 matching pursuit (MP), unweighted L₁-최소화, OMP, L1MAGIC 알고리즘간의 성능을 비교하였다. 성능 척도로는 최소 제곱 오차를 사용하였으며, 성긴 정도 (sparsity)의 변화에 따라 성능을 확인해 보았다. 복원하려는 원 신호 x의 크기는 256이고 K-스파스 벡터를 사용하였으며 K개의 위치는 랜덤하게 선택하였다.
즉, x₀만이 유일한 해가 된다. 이러한 점에 착안하여 제안하는 기법에서는 기존의 reweighted L₁-최소화 알고리즘에서 support 검출된 원소 위치에 작은 초기 가중치를, support가 아닌 원소 위치에 큰 값의 초기 가중치를 할당하는 방법을 제안한다. 두말 할 나위없이 본 방식의 효과를 보장하기 위해서는 정확한 support 정보가 필수적이다.

이론/모형

또한 절대값의 크기가 클 것으로 예상되는 원소 위치를 추정하기 위하여 개선된 orthogonal matching pursuit (OMP) 알고리즘을 이용한다. 구체적으로는 support 검출 성능을 높이기 위하여 사전에 측정 벡터 y와 상관성이 높은 열들을 최소 제곱 문제 (least squares problem) 단계에 활용한다. 컴퓨터 모의실험을 통하여 제안하는 기법의 복원 성능이 기존에 알려진 스파스 신호 복원 기법에 비해 최소 제곱 오차 (mean square error : MSE) 관점에서 우수한 성능을 보이는 것을 확인할 수 있었다.
-최소화)을 제안한다. 또한 절대값의 크기가 클 것으로 예상되는 원소 위치를 추정하기 위하여 개선된 orthogonal matching pursuit (OMP) 알고리즘을 이용한다. 구체적으로는 support 검출 성능을 높이기 위하여 사전에 측정 벡터 y와 상관성이 높은 열들을 최소 제곱 문제 (least squares problem) 단계에 활용한다.

성능/효과

벡터의 L₀-norm과 L₁-norm은 원소의 절대값이 커질수록 차이가 커지며, 이 사실로부터 support에 해당하는 인덱스에 작은 가중치를 주는 방식인 reweighted L₁-norm 통하여 L₀-norm과의 차이를 줄일 수 있었다. 그리고 support 검출을 위해서 변형된 OMP를 제안하였는데 여기서는 상관도가 높은 열들을 최소 제곱(least squares) 문제에서 사전에 이용함으로써 해당 열의 기여도를 정확하게 추정할 수 있었다.
모의실험을 통해서 matching pursuit (MP), unweighted L₁-최소화, OMP, L1MAGIC 알고리즘과 성능 비교를 한 결과 실험한 대부분의 구간에서 우수한 MSE 성능을 보이는 것을 확인할 수 있었다.
-최소화 알고리즘을 제안하였다. 벡터의 L₀-norm과 L₁-norm은 원소의 절대값이 커질수록 차이가 커지며, 이 사실로부터 support에 해당하는 인덱스에 작은 가중치를 주는 방식인 reweighted L₁-norm 통하여 L₀-norm과의 차이를 줄일 수 있었다. 그리고 support 검출을 위해서 변형된 OMP를 제안하였는데 여기서는 상관도가 높은 열들을 최소 제곱(least squares) 문제에서 사전에 이용함으로써 해당 열의 기여도를 정확하게 추정할 수 있었다.
그림 2는 제안된 알고리즘의 성긴 정도에 따른 신호 복원 성능을 나타낸다. 제안된 알고리즘은 모의실험한 모든 구간에서 가장 우수한 MSE 성능을 보여주고 있다. 특히 성긴 정도가 증가할수록 성능 개선이 더욱 커지는 것을 파악할 수 있다.
제안하는 기법의 특징은 reweighted L₁-최소화 알고리즘에서 초기 가중치를 주어 스파스한 신호의 복원 성능을 향상 시킨다는 점이다. 기존 방식은 반복 과정이 시작될 때 모든 원소에 대해 동일한 초기치 (w_i= 1)를 할당하는데 비해 제안하는 알고리즘은 support 검출을 통해 의미있는 초기 가중치를 할당한다.
구체적으로는 support 검출 성능을 높이기 위하여 사전에 측정 벡터 y와 상관성이 높은 열들을 최소 제곱 문제 (least squares problem) 단계에 활용한다. 컴퓨터 모의실험을 통하여 제안하는 기법의 복원 성능이 기존에 알려진 스파스 신호 복원 기법에 비해 최소 제곱 오차 (mean square error : MSE) 관점에서 우수한 성능을 보이는 것을 확인할 수 있었다.

질의응답

핵심어	질문	논문에서 추출한 답변
	나이퀴스트 샘플링 이론의 단점은?	나이퀴스트 샘플링 이론에 의하면 원 신호를 완벽하게 복원하기 위해서는 아날로그 신호 주파수 대역폭의 두 배 이상의 주파수로 샘플링을 해야 한다. 나이퀴스트 샘플링 이론은 명쾌하고 간단하지만, 신호를 완전 무결하게 복원하기 위한 필요충분조건이 아닌, 단순한 충분조건이기에 신호의 특성이 고려되지 않는 단점이 있다. 근래 3차원 영상이나 MRI 등의 바이오 신호 등의 예에서 볼 수 있듯이 샘플링 해야 하는 데이터의 양이 방대해짐에 짐에 따라 이 이론의 효율성에 대한 근본적인 의문이 꾸준이 제기되어 왔다.
	현재 사용 되고 있는 대부분의 디지털 장치는 아날로그 신호를 획득하는데 어떤 방식을 이용하는가?	현재 사용 되고 있는 대부분의 디지털 장치는 아날로그 신호를 획득하는데 있어 나이퀴스트 샘플링(Nyquist Sampling) 이론에 기반한 방식을 사용하고 있다. 나이퀴스트 샘플링 이론에 의하면 원 신호를 완벽하게 복원하기 위해서는 아날로그 신호 주파수 대역폭의 두 배 이상의 주파수로 샘플링을 해야 한다.
	Nyquist Sampling의 장점은?	나이퀴스트 샘플링 이론에 의하면 원 신호를 완벽하게 복원하기 위해서는 아날로그 신호 주파수 대역폭의 두 배 이상의 주파수로 샘플링을 해야 한다. 나이퀴스트 샘플링 이론은 명쾌하고 간단하지만, 신호를 완전 무결하게 복원하기 위한 필요충분조건이 아닌, 단순한 충분조건이기에 신호의 특성이 고려되지 않는 단점이 있다. 근래 3차원 영상이나 MRI 등의 바이오 신호 등의 예에서 볼 수 있듯이 샘플링 해야 하는 데이터의 양이 방대해짐에 짐에 따라 이 이론의 효율성에 대한 근본적인 의문이 꾸준이 제기되어 왔다.

참고문헌 (23)

B. K. Natarajan, "Sparse approximate solutions to linear systems," SIAM J. Comput, 24(2), pp. 227-234, 1995.

상세보기
E. Candes and T. Tao, "Decoding by linear programming," IEEE Trans. on Information Theory, 51(12), pp. 4203-4215, Dec. 2005.
E. Candes, J. Romberg, and T. Tao, "Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information," IEEE Trans. on Information Theory, 52(2), pp. 489-509, Feb. 2006.

상세보기
E. Candes and T. Tao, "Near optimal signal recovery from random projections: Universal encoding strategies," IEEE Trans. on Information Theory, 52(12), pp. 5406-5425, Dec. 2006.

상세보기
K. Lange, "Optimization," Springer Texts in Statistics. Springer-Verlag, New York, 2004.
E. Candes and J. Romberg, "Sparsity and incoherence in compressive sampling," Inverse Problems, 23(3), pp. 969-985, 2007.

상세보기
D. L. Donoho and P. B. Stark, "Uncertainty prindiples and signal recovery," SIAM J. Appl. Math. 49, no. 3, pp. 906-931, 1989.

상세보기
D. L. Donoho and B. F. Logan, "Signal recovery and the large sieve," SIAM J. Appl. Math. 52, no. 2, pp. 557-591, 1992.
R. Tibshirani, "Regression shrinkage and selection via the lasso," J. Roy. Statist. Soc. Ser. B 58, no. 1, pp. 267-288, 1996.
S. S. Chen, D. L. Donoho, and M. A. Saunders, "Atomic decomposition by basis pursuit," SIAM J. Sci. Comput. 1, pp. 33-61, 1998.
M. S. O''Brien, A. N. Sinclair, and S. M. Kramer, "Recovery of sparse spike time series by 1 norm deconvolution," IEEE Trans. Signal Processing, vol. 42, pp. 3353-3365, 1994.
E. J. Candes, M. B. Wakin, and S. Boyd, "Enhancing Sparsity by Reweighted L1-minimization," Journal of Fourier Analysis and Applications., 14(5), pp. 877-905, Dec. 2008.

상세보기
R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, "A Simple Proof of the Restricted Isometry Property for Random Matrices," 2008.
J. A. Tropp and A. C. Gilbery, "Signal recovery from random measurements via orthogonal matching pursuit," 2006.
D. Needell and R. Vershynin, "Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit," 2007.
D. L. Donoho, Y. Tsaig, and Jean-Luc Starck, "Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit," 2006.
W. Dai and O. Milenkovic, "Subspace Pusuit for Compressive Sensing: Closing the Gap Between Performance and Complexity," 2008.
W. Xu, M. A. Khajehnejad, A. S. Avestimehr, and B. Hassibi, "Breaking through the Thresholds: an Analysis for Iterative Reweighted 1-minimization via the Grassmann Angle Framework,"ICASSP 2010.
A. K. Fletcher, S. Rangan, and V. K. Goyal, "Necessary and Sufficient conditions on Sarsity Pattern recovery," arXiv:0804.1839v1[cs.IT]., Jan. 2009.

상세보기
D. Malioutov, M. Cetin, and A. Willsky, "A sparse signal reconstruction perspective for source localization with sensor arrays," IEEE Trans. Signal Process., 53(8), pp. 3010-3022, Aug.2005.

상세보기
D. Model and M. Zibulevsky, "Signal reconstruction in sensor arrays using sparse representations," IEEE Trans. Signal Process., 86(3), pp. 624-638, Mar. 2006.
D. Baron, M. B. Wakin, M. F. Duarte, S. Sarvotham, and R. G. Baraniuk, "Distributed compressed sensing," 2005.
E. Candes, M. Rudelson, and T. Tao, "Error correction via linear programming," IEEE Computer Society, 2005.

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증