Journal of the Institute of Electronics Engineers of Korea SP (대한전자공학회논문지SP)

The Institute of Electronics and Information Engineers (대한전자공학회)
권호 표지

Generalized Orthogonal Matching Pursuit

일반화된 직교 매칭 퍼슛 알고리듬

  • Kwon, Seok-Beop (School of Information and Communication, Korea University) ;
  • Shim, Byong-Hyo (School of Information and Communication, Korea University)
  • 권석법 (고려대학교 컴퓨터.전파통신공학과) ;
  • 심병효 (고려대학교 컴퓨터.전파통신공학과)
  • Received : 2011.10.21
  • Accepted : 2012.02.09
  • Published : 2012.03.25
Download PDF
⟨ Previous Next ⟩

Abstract

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.

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들를 선택함으로써 높은 복원 성능과 낮은 복잡도를 가짐을 확인하였다.

Keywords

References

  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. https://doi.org/10.1137/0149053
  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. https://doi.org/10.1007/s00365-007-9003-x
  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. https://doi.org/10.1109/TIT.2005.862083
  4. E. Candes and T. Tao, "Decoding by linear programming," IEEE Trans. on Information Theory, Vol. 51, no. 12, pp. 4203-4215, Dec. 2005. https://doi.org/10.1109/TIT.2005.858979
  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. https://doi.org/10.1109/TIT.2007.909108
  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. https://doi.org/10.1016/j.acha.2008.07.002
  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. https://doi.org/10.1109/TIT.2009.2016006
  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. https://doi.org/10.1109/JSTSP.2010.2042412
  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. https://doi.org/10.1109/TIT.2010.2054653
  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. https://doi.org/10.1016/j.crma.2008.03.014
  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. https://doi.org/10.1109/TIT.2004.834793