다중 후보 매칭 퍼슛 = Multiple Candidate Matching Pursuit

다국어 초록 (Multilingual Abstract)

As a greedy algorithm reconstructing the sparse signal from underdetermined system, orthogonal matching pursuit (OMP) algorithm has received much attention. In this paper, we multiple candidate matching pursuit (MuCaMP), which builds up candidate support set in every iteration and uses the minimum residual at last iteration. Using the restricted isometry property (RIP), we derive the sufficient condition for MuCaMP to recover the sparse signal exactly. The MuCaMP guarantees to reconstruct the K-sparse signal when the sensing matrix satisfies the RIP constant ${\delta}_{N+K}<\frac{\sqrt{N}}{\sqrt{K}+3\sqrt{N}}$. In addition, we show a recovery performance both noiseless and noisy measurements.

국문 초록 (Abstract)

Orthogonal matching pursuit (OMP) 알고리듬은 underdetermined 시스템에서 희소 신호를 복구하는 대표적인 greedy 알고리듬으로 많은 관심을 받고 있다. 본 논문에서는 OMP 알고리듬의 반복과정에서 후보 support 집합들을 구성하여 마지막 반복과정에서 최소 잔차를 이용하는 multiple candidate matching pursuit (MuCaMP) 기법을 제안한다. MuCaMP 가 완벽한 신호 복원을 보장하기 위한 restricted isometry property (RIP)를 이용한 충분조건, ${\delta}_{N+K}<\frac{\sqrt{N}}{\sqrt{K}+3\sqrt{N}}$을 제시한다. 실험을 통해 후보 support 집합들의 크기에 따른 성능과 MuCaMP의 복원 성능이 기존의 기법들에 비해 우수함을 확인하였다.

참고문헌 (Reference)

1 D. L. Donoho, "Uncertainty principles and signal recovery" 49 (49): 906-931, 1989

2 E. J. Candes, "The restricted isometry property and its implications for compressed sensing" 346 (346): 589-592, 2008

3 W. Dai, "Subspace pursuit for compressive sensing signal reconstruction" 55 (55): 2230-2249, 2009

4 D. L. Donoho, "Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit" Mar 2006

5 J. A. Tropp, "Signal recovery from random measurements via orthogonal matching pursuit" 53 (53): 4655-4666, 2007

6 D. Needell, "Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit" 4 (4): 310-316, 2010

7 E. Candes, "Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information" 52 (52): 489-509, 2006

8 R. Giryes, "RIP-Based Near-Oracle Performance Guarantees for SP,CoSaMP,and IHT" (99) : 2011

9 J. A. Tropp, "Greed is good:Algorithmic results for sparse approximation" 50 (50): 2231-2242, 2004

10 E. Candes, "Decoding by linear programming" 51 (51): 4203-4215, 2005

11 D. Needell, "CoSaMP:Iterative signal recovery from incomplete and inaccurate samples" 26 (26): 301-321, 2009

12 M. A. Davenport, "Analysis of Orthogonal Matching Pursuit using the restricted isometry property" 56 (56): 4395-4401, 2010

13 R. Baraniuk, "A simple proof of the restricted isometry property for random matrices" 28 (28): 253-263, 2008