본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

일반화된 직교 매칭 퍼슛 알고리듬
Generalized Orthogonal Matching Pursuit

권석법    (고려대학교 컴퓨터.전파통신공학과   ); 심병효    (고려대학교 컴퓨터.전파통신공학과  );
  • 초록

    Compressive sensing 분야에서 orthogonal matching pursuit (OMP) 알고리듬은 underdetermined 시스템의 스파스 (sparse) 신호를 복구하는 대표적인 greedy 알고리듬으로 많은 관심을 받고 있다. 본 논문에서는 OMP 알고리듬의 반복과정에서 하나 이상의 support들을 선택할 수 있도록 하는 OMP 알고리듬의 일반화된 형태의 generalized orthogonal matching pursuit (gOMP)기법을 제안한다. gOMP가 완벽한 신호 복원을 보장하기 위해 restricted isometry property (RIP)를 이용한 충분조건, ${\delta}_{NK}$ $\frac{\sqrt{N}}{\sqrt{K}+2\sqrt{N}}$ 을 제시한다. 실험을 통해 gOMP는 매 반복과정에서 하나 이상의 support들를 선택함으로써 높은 복원 성능과 낮은 복잡도를 가짐을 확인하였다.


    As a greedy algorithm reconstructing the sparse signal from underdetermined system, orthogonal matching pursuit (OMP) algorithm has received much attention in recent years. In this paper, we present an extension of OMP for pursuing efficiency of the index selection. Our approach, referred to as generalized OMP (gOMP), is literally a generalization of the OMP in the sense that multiple (N) columns are identified per step. Using the restricted isometry property (RIP), we derive the condition for gOMP to recover the sparse signal exactly. The gOMP guarantees to reconstruct sparse signal when the sensing matrix satisfies the RIP constant ${\delta}_{NK}$ $\frac{\sqrt{N}}{\sqrt{K}+2\sqrt{N}}$ . In addition, we show recovery performance and the reduced number of iteration required to recover the sparse signal.


  • 주제어

    orthogonal matching pursuit (OMP) .   compressive sensing (CS) .   restricted isometry property (RIP).  

  • 참고문헌 (13)

    1. D. L. Donoho and P. B. Stark, "Uncertainty principles and signal recovery," SIAM Journal on Applied Mathematics, Vol. 49, no. 3, pp. 906-931, 1989. 
    2. R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, "A simple proof of the restricted isometry property for random matrices," Constructive Approximation, Vol. 28, no. 3, pp. 253-263, Dec. 2008. 
    3. E. Candes, J. Romberg, and T. Tao, "Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information," IEEE Trans. on Information Theory, Vol. 52, no. 2, pp. 489-509, Feb. 2006. 
    4. E. Candes and T. Tao, "Decoding by linear programming," IEEE Trans. on Information Theory, Vol. 51, no. 12, pp. 4203-4215, Dec. 2005. 
    5. R. Giryes and M. Elad, "RIP-Based Near-Oracle Performance Guarantees for SP, CoSaMP, and IHT," IEEE Trans. on Signal Processing, Vol. PP, no. 99, Nov. 2011. 
    6. J. A. Tropp and A. C. Gilbery, "Signal recovery from random measurements via orthogonal matching pursuit," IEEE Trans. on Information Theory, Vol. 53, no. 12, pp. 4655-4666, Dec. 2007. 
    7. D. Needell and J. A. Tropp, "CoSaMP: Iterative signal recovery from incomplete and inaccurate samples," Applied and Computational Harmonic Analysis, Vol. 26, no. 3, pp. 301-321, Mar. 2009. 
    8. W. Dai and O. Milenkovic, "Subspace pursuit for compressive sensing signal reconstruction," IEEE Trans. on Information Theory, Vol. 55, no. 5, pp. 2230-2249, May. 2009. 
    9. D. Needell and R. Vershynin, "Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit," IEEE J. Sel. Topics Signal Processing, Vol. 4, no. 2, pp. 310-316, Apr. 2010. 
    10. D. L. Donoho and I. Drori and Y. Tsaig and J. L. Starck,, "Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit," Mar. 2006. 
    11. M. A. Davenport and M. B. Wakin, "Analysis of Orthogonal Matching Pursuit using the restricted isometry property," IEEE Trans. on Information Theory, Vol. 56, no. 9, pp. 4395-4401, Sep. 2010. 
    12. E. J. Candes, "The restricted isometry property and its implications for compressed sensing," Comptes Rendus Mathematique, Vol. 346, no. 9-10, pp. 589-592, May. 2008. 
    13. J. A. Tropp, "Greed is good: Algorithmic results for sparse approximation," IEEE Trans. on Information Theory, Vol. 50, no. 10, pp. 2231-2242, Oct. 2004. 
  • 이 논문을 인용한 문헌 (3)

    1. Kim, Seehyun 2013. "Probabilistic Exclusion Based Orthogonal Matching Pursuit Algorithm for Sparse Signal Reconstruction" 전기전자학회논문지 = Journal of IKEEE, 17(3): 339~345     
    2. 2016. "" Journal of communications and networks, 18(5): 699~712     
    3. Sim, Byeong-Hyo ; Kim, Jin-Hong ; Kim, Won-Jun 2016. "" 정보와 통신 : 한국통신학회지 = Information & communications magazine, 33(6): 34~44     

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기