최근에 압축 센싱(compressive sensing)은 많은 연구자들로부터 신호의 획득과 복원 분야에서 새로운 대안으로 심도있는 관심을 받고 있다. 나이퀴스트 표본 이론은 신호 처리 분야에서 오랫동안 기본 이론으로서 중요한 역할을 수행해 왔다. 그러나 그 이론은 단지 아날로그 신호를 획득할 때에 완벽한 복원을 보장하는 충분조건일 뿐이다. 특정 신호의 경우 나이퀴스트 비율로 표본화하면 매우 비효율적인 처리 과정을 겪게 된다.

만약 어떤 실수 값을 갖는 신호 x∈R^N 가 K개의 0이 아닌 성분을 갖는다고 하자. K< 이라면 x는 희소(sparse)하다고 한다. 압축 센싱 이론에서는 N보다 작은M개의 측정값, 즉 y∈R^M 만으로도 희소한 x를 완벽히 복원할 수 있음이 증명되어있다[1,2].

K는 희소도(sparsity level)라고 하며 x는 K–희소하다고 한다. 측정값 y는 M×N 측정 행렬 Φ와 x의 곱으로 표현될 수 있다. 즉,

이다. M < N이므로 y로부터 x를 구하는 문제는 하나 이 상의 많은 해를 가질 수 있다. Candes[1]와 Donoho[2] 는 두 가지 조건 즉, (1) x가 충분히 희소하고 (2) M이 O(Klog(N/K))라면 l₁최소화와 같은 비선형 컨벡스 최적화 방법을 이용하여 y로부터 x를 정확히 복원해 낼 수 있음을 보였다. 이 문제를 풀기위한 방법 중의 하나인 기저 추구(basis pursuit) 방법에서 x는 다음과 같이 구 할 수 있다[3].

그러나 이 방법의 계산량도 O(N³)이므로 대부분의 응용에서 사용하기 어렵다.

계산량을 줄이기 위해 많은 연구가 수행되었으며 탐욕 알고리듬 기반의 여러 방법들이 제안되었다. Matching pursuit (MP) [4]와 orthogonal matching pursuit (OMP) [5]가 선구적인 연구이며, 신호 복원 성능과 수렴 속도 및 계산량을 줄이기 위한 많은 연구가 이어졌다. Stagewise OMP (StOMP) [6], Compressive Sampling Matching Pursuit (CoSaMP) [7], Subspace Pursuit (SP) [8], generalized Orthogonal Matching Pursuit (gOMP) [9], Backtracking base Adaptive OMP(BAOMP) [10] 등이 그 결과이다.

그러나 이 알고리듬들의 공통된 특징은 희소도가 증가함에 따라 해를 찾지 못하는 빈도가 늘어난다는 점이다. 가장 근본적인 이유는 반복과정에서 support set이 잔차의 크기는 작지만 잘못된 atom을 포함하고 있는, 즉 국소 최저에 빠져서 이후의 반복과정에서도 그 국소최저에서 벗어나지 못하기 때문이다. 이는 탐욕 알고리듬의 근본적인 문제이기도 하다. 본 논문에서는 이러한 국소최저 문제를 회피할 수 있는 새로운 희소 신호 복원 알고리듬을 제안한다. 다른 OMP 기반의 알고리듬과 같이 매 반복과정에서 잔차 신호로부터 새로운 atom을 찾아 내어 희소도도 추정하고 support set도 갱신한다. 또한, CoSaMP, SP, BAOMP처럼 그 유효성이 입증되지 않는 atom들은 support set에서 제거한다. 제안된 방법에서는 추가적으로 유전 알고리듬의 주요 도구인 확률적 변이를 support set에 적용하여 국소 최저를 벗어 날 수 있는 기능을 보강하였다.

제 2장에서는 제안된 유전 알고리듬 기반 OMP(GAOMP) 방법의 단계별 동작을 설명한다. 제 3장에서는 GAOMP의 성능을 거론된 몇몇 알고리듬들과 모의실험 결과를 이용하여 비교하고, 마지막으로 본 논문의 기여를 제 4장에서 요약한다.

식 (1)의 Φ의 열벡터는 atom이라 정의되며 모든 atom들의 집합은 dictionary라고 한다. 희소 신호 x를 복원하는 문제는 dictionary로부터 atom들을 선택하되 선택된 atom들의 선형 합이 y와 같아지도록 만드는 것과 동일하다. 이 때 선택된 atom 들의 번호의 집합을 support set이라 한다. 이러한 희소 신호 복원 문제에 탐욕 알고리듬을 적용한 선구적인 연구는 MP이다. OMP는 초기화와 새로운 atom 선택은 MP와 동일하게 동작한다. OMP가 MP보다 탁월한 성능을 보이는 이유는 새로 선택된 atom들로부터 least squares 방법으로 희소 신호의 추정값을 구하기 때문이다. OMP 기반의 알고리듬들이 공통적으로 수행하는 세가지 기본 동작은 다음과 같다. 매 반복 수행 과정에서, 가장 높은 상관관계를 갖는 atom들을 선택하고 (선택), 그 atom들의 인덱스를 support set에 추가하고 (추가), 새로운 support set으로 복원한 신호의 추정값을 계산한 후 잔차를 갱신한다 (갱신). 몇몇 알고리듬에서는 추가 단계 이후에 신뢰도가 떨어지는 atom들을 제거한다 (정리). 정리 단계를 통해 신호의 복원 성능을 높이고 수렴 속도도 향상 시킬 수 있다[7,8,10]. 이러한 직교 정합 추구 방법의 계산 복잡도는 O(KMN)이며, 이는 K<이라면 BP방법과 같은 l₁ 최소화보다 매우 작은 값이 된다. ROMP, StOMP, SP, CoSaMP, gOMP, BAOMP등은 모두 OMP에 기반을 두고 있으며, 한편으로는 매 반복과정에서 여러개의 atom을 선택하여 수렴속도를 향상시키고 있다.

비록 탐욕 알고리듬이 일반적으로 비용을 최소화하기 위한 효율적인 방법이기는 하지만 국소 최저 문제를 겪기도 한다. 탐욕적인 OMP 기반 알고리듬들도 이 문제에 취약하다. Support set을 갱신해 나가면서 잔차의 크기를 줄여 나가지만 국소 최저에 빠질 수 있으며, 그 경우에 오랜 반복 과정으로도 희소한 원 신호를 복원할 수 없게 된다. 최근에 보고된 gOMP나 BAOMP도 국소 최저 문제로 인해 희소 신호를 복원하지 못하는 경우가 발생한다.

유전 알고리듬은 국소 최저를 갖는 비용 함수의 전역최저를 찾을 수 있는 확률적인 반복 방법이며, 일반적인 최적화 문제에서 gradient search 방법보다 우수한 성능을 보인다[11]. “세대”라고 불리는 매 반복 과정마다 각 “개인”의 적합도를 평가한다. 높은 적합도를 갖는 개인을 확률적으로 선택하고 그 후보의 유전자를 변형하여 다음 세대를 준비한다. 변이(mutation)가 선택(selection)이나 교차(crossover)보다 우수한 유전 알고리듬의 연산자임이 잘 알려져 있다. 적절한 확률로 변이 과정을 거치면 자신과 유사한 특성을 피할 수 있다. 이로 인해 국소최저를 빠져 나올 수 있으며 결과적으로 알고리듬의 수렴이 늦어지거나 멈추는 상황을 개선할 수 있다.

표 1에 나와 있는 제안된 GAOMP 알고리듬은 두 부분으로 이루어져 있다. 1단계부터 3단계는 OMP 부분으로 least squares 방법으로 support set을 원 신호에 가깝게 보완해 나가며, 4단계는 GA 부분으로 확률적 변이를 통해 원 신호를 향한 다양성을 제공한다. x_n , r_n 및 Λ_n 은 각각 n번째 반복 과정의 복원될 희소 신호, 잔차, 그리고 support set이다. 반복되는 과정은 4단계로 구성된다. 1단계에서는 잔차와 atom(𝜓_i, _i∈[1,N])들간의 상관도를 구하여 문턱값보다 큰 모든 atom들의 번호를 support set에 추가한다. OMP는 가장 큰 상관도(ρ_max)를 보이는 atom 만 사용하지만 GAOMP에서는 수렴 속도를 향상시키기 위하여 StOMP, gOMP, BAOMP와 유사하게 여러개의 atom을 추가한다. gOMP는 추가하는 atom의 수를 고정하고 있는데 이는 희소도 K를 모를 경우 틀린 atom을 추가할 가능성이 존재한다. 1b단계에 있는 μ는 0과 1사이의 실수 상수로서 문턱값 계산에 사용되며 따라서 추가되는 atom들의 개수에 영향을 미친다.

μ=1이라면 OMP와 같이 ρ_max에 해당되는 하나의 atom만 추가된다.0< μ< 1일 때 추가되는 atom의 수는 고정되지 않지만 최대 L개까지 가능하다. BAOMP에서는 추가되는 atom의 수에 제한이 없기 때문에 상관도의 분포가 완만할 경우에는 많은 수의 atom이 추가되기 때문에 잘못된 atom이 포함될 가능성이 높다. 𝛥 는 1b 단계에서 선택된 atom들의 번호의 집합이며 1c단계에서 support set에 추가되어 임시의 support set θ 를 구성한다.

두 번째 단계에서는 θ 에 포함되어 있을 수 있는 잘못된 atom들을 제거한다. Φ_θ 는 Φ의 열벡터 중 그 번호가 θ 에 있는 것들만 모아서 구성한 부분 행렬이며, 는 그의 pseudo inverse이다. 따라서 2a 단계의 x_θ는 θ 에 있는 atom들로 least squares 방법으로 복원한 x이다. 즉 x_θ 의 각 성분은 θ에 있는 각 atom들의 x에 대한 기여도이다. x_θ 의 성분 중에 Δ 에 속한 atom들에 대한 최대값을 α_max라 하자. 만약 α_max보다 작은 계수를 갖는 atom이 {θ \𝛥}에 있다면 그 atom은 비록 이전 반복과정에서 support set에 추가되었지만 현 반복과정에서 추가된 atom보다 중요도가 작다는 의미이다. 즉 support set에 포함될 자격이 없으므로 제거되어야 한다. 그러나 그 atom이 희소 신호의 atom이 맞다면 이후의 반복과정에서 다시 추가될 가능성은 열려있다. 2c 단계에서 ν=0.7이라면 α_max의 70%보다 작은 계수를 갖는 atom들은 모두 support set에서 제거된다.

Λ_n이 갱신되면 3 단계에서 least squares 방법으로 x가 추정되고, 이어서 새로운 잔차가 계산된다. 이러한 반복과정은 잔차의 크기가 𝜖_max보다 작거나 반복 횟수가 최대 반복 횟수, n_max와 같아지면 알고리듬은 종료된다.

제안된 GAOMP는 support set을 확률적으로 변이시킴으로써 국소 최저를 피할 수 있다. 4b 단계에서는 Λ_n 의 임의의 원소를 제외시켜 변이를 일으킨 후 수용 확률 p에 따라 새로운 support set으로 선택한다. 복원하려는 신호가 희소하다고 가정하였으므로 Λ_n 은 그 크기가 커질수록 신뢰도는 떨어진다. 특히 |Λ_n|≥ M 이면 support set은 무조건 변이되어야 한다 (p=1). 알고리듬 실행 초기에는 즉, |Λ_n| ≪ M 인 경우에는 OMP부분이 성공적으로 atom들을 찾기 때문에 p는 작은 값으로 유지되어야 한다. 4a 단계에서 보는 바와 같이 수용 확률 p는 |Λ_n|이 증가함에 따라 0에서 1까지 기울기인수 k에 따라 단조 증가한다. k로 전반적인 변이 특성을 조절할 수 있다.

SP나 CoSaMP와 달리 GAOMP는 신호 복원의 실행을 위해 희소도 정보를 요구하지 않는다. 대부분의 응용 예에서도 희소도는 사전에 알 수 없다. Needell이 실행에 앞서 희소도를 추정하는 방법을 제안하였지만 [7] 잘못 추정된 희소도는 신호 복원 실패로 이어짐을 유의해야 한다.

그림 1은 제안된 알고리듬과 BAOMP의 동작 특성을 비교하고 있다. 희소 신호와 측정 신호의 크기는 각각 200과 100이고 (N=200, M=100) 희소도는 40이다 (K=40). BAOMP는 매 반복과정에서 여러개의 atom을 추가하고 제외시키기 때문에 빠른 수렴 속도와 높은 복원 확률을 보인다. 그러나 그림 1(a)에서 확인할 수 있는 바와 같이 support set의 크기가 반복 과정이 진행되면서 계속 커지기도 한다. 물론 잔차의 크기는 지속적으로 줄어들기는 한다. 이 경우에는 support set에 잘못된 atom이 들어 있으며 반복 과정을 거쳐도 제거되지 않기 때문에 잔차의 크기는 0이 되지않는다. 이렇게 BAOMP는 국소 최저를 극복하지 못하였기 때문에 결과적으로 희소 신호 복원에 실패하였다. 그러나 그림 1(b)와 같이 GAOMP는 국소 최저를 빠져 나올 수 있기 때문에 원 희소 신호를 복원할 수 있다. 9번째 반복과정에서 GAOMP는 변이된 support set을 수용하여 국소최저를 빠져나왔다. 비록 잠시 잔차가 커졌지만 곧 올바른 support set을 찾는다.

제안된 GAOMP의 복원 성능을 탐욕 방법의 OMP, StOMP, BAOMP 및 l₁ 최적화 방법 즉, BP와 비교하였다. 입력 신호로는 가우시안과 PAM (pulse amplitude modulation) 신호를 사용하였다.

K -희소한 신호의 support set은 임의로 선택하였고 계수는 가우시안 분포의 랜덤 신호를 발생시키거나 {±1, ± 3}에서 임의로 선택하였다. 복원 확률은 1000번의 독립적인 실험을 통해서 얻었다. 측정 행렬 Φ는 i.i.d. 가우시안 난수로 구성하였으며 각 열벡터는 그 크기를 1로 정규화하였다. 복원 결과는 모든 성분이 원신호와 차이가 10^-3 이하일 때 성공이라고 판단하였다. OMP, StOMP, BP에 대해서는 SparseLab tool[12]을 사용하였다. GAOMP는 Matlab으로 구현하였다. StOMP에서는 문턱값을 FDR (false discovery rate)로 사용하였고 BAOMP에서는 μ₁과 μ₂는 모두 0.6으로 고정하였다. GAOMP에서는 𝜅는 2, L은 5일 때 최고의 성능을 보였다.

희소도 K 는 그림 1과 동일한 조건, 즉 N=200, M=100에서 5부터 80까지 5씩 증가시키면서 복원 성능을 측정하였다. 그림 2(a)와 같이 GAOMP는 BP를 포함한 모든 알고리듬보다 우수한 성능을 보인다. K 가 45일 때까지 GAOMP는 가우시안 희소 신호를 매번 완벽히 복원하였다. 두 번째로 좋은 성능을 보이는 BAOMP도 K 가 35이면 복원에 실패하기 시작한다. GAOMP는 상대적으로 덜 희소한 신호에 대해서도 가장 우수한 성능을 보인다. 예를 들어 K 가 55일 때 다른 알고리듬들은 성공 확률이 10%보다 작지만 GAOMP는 약 70%의 확률로 신호 복원에 성공한다.

표 2에서는 BAOMP와 GAOMP의 Matlab 수행 시간을 비교하였다. K가 5부터 35의 범위일 경우, 즉 상대적으로 더 희소한 경우에는 두 알고리듬 모두 완벽한 복원 성능을 보였고 실행 시간도 거의 비슷했다. 입력신호의 K 가 40 이상인 경우에는 GAOMP가 우수한 복원 성능을 보이지만 실행 시간은 더 길어진다. K 가 55일 때는 GAOMP의 복원 확률은 BAOMP보다 7배 높지만 실행시간은 5배 늘어난다. 실행시간은 많이 늘어났지만 복원성능이 그 이상으로 향상되었으므로 수용할만한 tradeoff라고 할 수 있겠다.

입력 신호가 PAM 희소 신호인 경우는 그림 2(b)에 나타내었다. 모든 알고리듬이 가우시안 신호의 경우(그림 1(a))보다 다소 낮은 복원 성능을 보이지만 BP만이 거의 유사한 성능을 유지하였다. PAM 신호에 대해서도 GAOMP가 가장 우수한 복원 성능을 보였다.

두 번째 모의 실험에서는 가우시안 신호와 PAM 신호에 대한 복원 성능의 변화를 측정값의 크기 M에 대하여 관찰하였다. 실험 환경은 이전 실험과 같다. 희소도 K는 모든 알고리듬들이 완벽한 복원 성능을 보였던 30으로 고정하였고 M은 40에서 150까지 5씩 증가 하였다. 그림 3에 나타난 바와 같이 제안된 GAOMP가 BP를 포함한 모든 OMP 기반의 알고리듬보다 우수한 복원 성능을 보여준다. 가우시안 신호의 경우(그림 3(a))에는 GAOMP의 BAOMP에 대한 측정값 크기 이득은 복원 확률 50%에서 약 10이다. 즉 GAOMP는 측정값이 10개가 적어도 50%의 복원 확률을 얻을 수 있다. GAOMP의 OMP, BP, StOMP에 대한 이득은 각각 약 15, 25, 50이다. 희소도에 따른 복원성능 실험과 유사하게, PAM 신호에 대한 측정값 크기 이득은 OMP 기반의 알고리듬들이 약 –10 정도이며, BP만이 가우시안 신호와 비슷한 성능을 보인다.

본 논문에서는 희소 신호의 복원을 위해서 GAOMP라 불리는 유전 알고리듬을 활용한 직교 정합 추구 방법을 제안하였다. 원 신호가 덜 희소하거나 또는 측정치의 개수가 부족한 경우에 OMP 변종 알고리듬들은 국소 최저 문제로 인해 신호의 복원에 실패하는 확률이 높아진다. 이는 support set에 잘못 포함된 atom이 반복과정을 통해서 제외되지 않기 때문이며, 특히 잔차의 크기가 작을 때 더욱 복원 가능성은 떨어진다. 이러한 국소 최저 문제는 탐욕 알고리듬의 원천적인 약점이기도 하다. 제안된 GAOMP는 support set에 확률적 변이를 적용하여 잔차의 크기가 작더라도 국소 최저에서 빠져나와 희소 신호를 완벽하게 복원할 수 있는 확률을 향상시켰다. 모의실험 결과로부터 GAOMP가 실험에 사용된 모든 OMP 기반의 방법과 l₁ 최적화 방법보다 우수한 복원 성능을 보임을 알 수 있다. 또한 제안된 방법은 신호의 희소도를 미리 알 필요가 없으므로 희소도 정보를 알 수 없는 일반적인 응용에 적용될 수 있다.