MUSIC (알고리즘)

MUSIC(multiple sIgnal classification)은 주파수 추정^[1][2][3] 및 무선 방향 탐지에 사용되는 알고리즘이다.^[4]

MUSIC 알고리즘에 의한 무선 방향 탐지

역사

많은 실용적인 신호 처리 문제에서 목표는 수신 신호가 의존하는 일련의 상수 매개변수를 측정값으로부터 추정하는 것이다. 카폰(1969)의 최대 우도(ML) 방법과 버그의 최대 엔트로피(ME) 방법과 같은 여러 접근 방식이 있었다. 이러한 방법들은 종종 성공적이고 널리 사용되지만, 측정값에 대해 (특수 ARMA 대신 AR과 같은) 잘못된 모델을 사용하기 때문에 특정 근본적인 한계(특히 매개변수 추정치의 편향 및 민감도)를 가지고 있다.

피사렌코(Pisarenko)(1973)는 공분산 접근 방식을 사용하여 가산 노이즈 내에서 복소수 사인파의 매개변수 추정이라는 맥락에서 데이터 모델의 구조를 활용한 최초의 사람 중 한 명이다. 노스롭 그러먼에서 근무하던 슈미트(Schmidt)(1977)와 독립적으로 비엥베누(Bienvenu)와 코프(Kopp)(1979)는 임의 형태의 센서 배열의 경우에 측정 모델을 올바르게 활용한 최초의 사람이었다. 특히 슈미트는 먼저 노이즈가 없는 상태에서 완전한 기하학적 해를 도출한 다음, 기하학적 개념을 영리하게 확장하여 노이즈가 있는 상태에서 합리적인 근사 해를 얻음으로써 이를 달성했다. 그 결과로 나온 알고리즘은 MUSIC(multiple signal classification)이라고 불렸고 널리 연구되었다.

수천 건의 시뮬레이션에 기반한 상세한 평가에서 매사추세츠 공과대학교 링컨 연구소는 1998년 현재 인정되는 고해상도 알고리즘 중에서 MUSIC이 가장 유망하며 추가 연구 및 실제 하드웨어 구현을 위한 선도적인 후보라고 결론지었다.^[5] 그러나 MUSIC의 성능 이점이 상당하지만, 계산( 매개변수 공간 검색) 및 저장(배열 보정 데이터) 비용이 든다.^[6]

이론

MUSIC 방법은 신호 벡터 ${\displaystyle \mathbf {x} }$가 가우시안 백색 잡음 ${\displaystyle \mathbf {n} }$이 있는 상태에서 주파수 ${\displaystyle \omega }$가 알려지지 않은 ${\displaystyle p}$개의 복소수 지수 함수로 구성된다고 가정하며, 이는 선형 모델로 다음과 같이 주어진다.

${\displaystyle \mathbf {x} =\mathbf {A} \mathbf {s} +\mathbf {n} .}$

여기서 ${\displaystyle \mathbf {A} =[\mathbf {a} (\omega _{1}),\cdots ,\mathbf {a} (\omega _{p})]}$는 조향 벡터 ${\displaystyle \mathbf {a} (\omega )=[1,e^{j\omega },e^{j2\omega },\ldots ,e^{j(M-1)\omega }]^{T}}$의 ${\displaystyle M\times p}$ 방데르몽드 행렬이고, ${\displaystyle \mathbf {s} =[s_{1},\ldots ,s_{p}]^{T}}$는 진폭 벡터이다. 중요한 가정은 소스의 개수 ${\displaystyle p}$가 측정 벡터의 요소 개수 ${\displaystyle M}$보다 작다는 것이다. 즉, ${\displaystyle p<M}$이다.

${\displaystyle \mathbf {x} }$의 ${\displaystyle M\times M}$ 자기상관 행렬은 다음과 같이 주어진다.

${\displaystyle \mathbf {R} _{x}=\mathbf {A} \mathbf {R} _{s}\mathbf {A} ^{H}+\sigma ^{2}\mathbf {I} ,}$

여기서 ${\displaystyle \sigma ^{2}}$는 잡음 분산이고, ${\displaystyle \mathbf {I} }$는 ${\displaystyle M\times M}$ 단위 행렬이며, ${\displaystyle \mathbf {R} _{s}}$는 ${\displaystyle \mathbf {s} }$의 ${\displaystyle p\times p}$ 자기상관 행렬이다.

자기상관 행렬 ${\displaystyle \mathbf {R} _{x}}$는 전통적으로 샘플 상관 행렬을 사용하여 추정된다.

${\displaystyle {\widehat {\mathbf {R} }}_{x}={\frac {1}{N}}\mathbf {X} \mathbf {X} ^{H}}$

여기서:

${\displaystyle N>M}$은 벡터 관측값의 개수이고,

${\displaystyle \mathbf {X} =[\mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{N}]}$이며,

${\displaystyle \mathbf {X} ^{H}}$는 ${\displaystyle \mathbf {X} }$의 켤레 전치를 나타낸다.

${\displaystyle \mathbf {R} _{x}}$의 추정값이 주어지면 MUSIC은 고유 공간 방법을 사용하여 신호 또는 자기상관 행렬의 주파수 내용을 추정한다.

${\displaystyle \mathbf {R} _{x}}$는 에르미트 행렬이므로, 모든 ${\displaystyle M}$개의 고유 벡터 ${\displaystyle \{\mathbf {v} _{1},\mathbf {v} _{2},\ldots ,\mathbf {v} _{M}\}}$는 서로 직교한다. ${\displaystyle \mathbf {R} _{x}}$의 고유값이 내림차순으로 정렬되면, ${\displaystyle p}$개의 가장 큰 고유값(즉, 가장 큰 변동성의 방향)에 해당하는 고유 벡터 ${\displaystyle \{\mathbf {v} _{1},\ldots ,\mathbf {v} _{p}\}}$는 신호 부분 공간 ${\displaystyle {\mathcal {U}}_{S}}$를 스팬한다. 나머지 ${\displaystyle M-p}$개의 고유 벡터는 ${\displaystyle \sigma ^{2}}$와 같은 고유값에 해당하며, 신호 부분 공간에 직교하는 잡음 부분 공간 ${\displaystyle {\mathcal {U}}_{N}}$을 스팬한다. ${\displaystyle {\mathcal {U}}_{S}\perp {\mathcal {U}}_{N}}$.

${\displaystyle M=p+1}$일 때, MUSIC은 피사렌코 고조파 분해와 동일하다는 점에 유의하라. MUSIC 방법의 일반적인 아이디어는 잡음 부분 공간을 스팬하는 모든 고유 벡터를 사용하여 피사렌코 추정기의 성능을 향상시키는 것이다.

신호 부분 공간 ${\displaystyle \mathbf {e} \in {\mathcal {U}}_{S}}$에 속하는 모든 신호 벡터 ${\displaystyle \mathbf {e} }$는 잡음 부분 공간에 직교해야 하므로 ${\displaystyle \mathbf {e} \perp {\mathcal {U}}_{N}}$, 즉 잡음 부분 공간을 스팬하는 모든 고유 벡터 ${\displaystyle \{\mathbf {v} _{i}\}_{i=p+1}^{M}}$에 대해 ${\displaystyle \mathbf {e} \perp \mathbf {v} _{i}}$여야 한다. ${\displaystyle \mathbf {e} }$가 모든 ${\displaystyle \mathbf {v} _{i}\in {\mathcal {U}}_{N}}$에 대해 직교하는 정도를 측정하기 위해 MUSIC 알고리즘은 다음과 같은 제곱 노름을 정의한다.

${\displaystyle d^{2}=\|\mathbf {U} _{N}^{H}\mathbf {e} \|^{2}=\mathbf {e} ^{H}\mathbf {U} _{N}\mathbf {U} _{N}^{H}\mathbf {e} =\sum _{i=p+1}^{M}|\mathbf {e} ^{H}\mathbf {v} _{i}|^{2}}$

여기서 행렬 ${\displaystyle \mathbf {U} _{N}=[\mathbf {v} _{p+1},\ldots ,\mathbf {v} _{M}]}$는 잡음 부분 공간 ${\displaystyle {\mathcal {U}}_{N}}$을 스팬하는 고유 벡터들의 행렬이다. 직교 조건에 따라 ${\displaystyle \mathbf {e} \in {\mathcal {U}}_{S}}$이면 ${\displaystyle d^{2}=0}$이다. 제곱 노름 표현의 역수를 취하면 신호 주파수에서 날카로운 피크가 생성된다. MUSIC의 주파수 추정 함수(또는 의사 스펙트럼)는 다음과 같다.

${\displaystyle {\hat {P}}_{MU}(e^{j\omega })={\frac {1}{\mathbf {e} ^{H}\mathbf {U} _{N}\mathbf {U} _{N}^{H}\mathbf {e} }}={\frac {1}{\sum _{i=p+1}^{M}|\mathbf {e} ^{H}\mathbf {v} _{i}|^{2}}},}$

여기서 ${\displaystyle \mathbf {v} _{i}}$는 잡음 고유 벡터이고,

${\displaystyle \mathbf {e} ={\begin{bmatrix}1&e^{j\omega }&e^{j2\omega }&\cdots &e^{j(M-1)\omega }\end{bmatrix}}^{T}}$

는 후보 조향 벡터이다. 추정 함수의 ${\displaystyle p}$개의 가장 큰 피크 위치는 ${\displaystyle p}$개의 신호 구성 요소에 대한 주파수 추정값을 제공한다.

${\displaystyle {\hat {\omega }}=\arg \max _{\omega }\;{\hat {P}}_{MU}(e^{j\omega }).}$

MUSIC은 피사렌코 방법의 일반화이며, ${\displaystyle M=p+1}$일 때 피사렌코 방법으로 축소된다. 피사렌코 방법에서는 주파수 추정 함수 분모를 구성하는 데 단일 고유 벡터만 사용되며, 이 고유 벡터는 일련의 자기회귀 계수로 해석되고, 그 영점은 해석적으로 또는 다항식 근 찾기 알고리즘으로 찾을 수 있다. 대조적으로, MUSIC은 여러 이러한 함수가 함께 추가되었다고 가정하므로 영점이 존재하지 않을 수 있다. 대신 추정 함수의 피크를 계산적으로 검색하여 찾을 수 있는 지역 최소값이 존재한다.

신호 공간의 차원

MUSIC 및 다른 부분 공간 분해 방법이 기반으로 하는 근본적인 관찰은 자기상관 행렬 ${\displaystyle \mathbf {R} _{x}}$의 계수에 대한 것이며, 이는 신호 소스의 개수 ${\displaystyle p}$와 다음과 같이 관련된다.

소스가 복소수이면 ${\displaystyle M>p}$이고 신호 부분 공간 ${\displaystyle {\mathcal {U}}_{S}}$의 차원은 ${\displaystyle p}$이다. 소스가 실수이면 ${\displaystyle M>2p}$이고 신호 부분 공간의 차원은 ${\displaystyle 2p}$이다. 즉, 각 실수 사인파는 두 개의 기저 벡터에 의해 생성된다.

이 근본적인 결과는 스펙트럼 분석 책에서 종종 생략되지만, 입력 신호가 ${\displaystyle {\mathcal {U}}_{S}}$를 스팬하는 ${\displaystyle p}$개의 신호 부분 공간 고유 벡터(실수 값 신호의 경우 ${\displaystyle 2p}$)와 ${\displaystyle {\mathcal {U}}_{N}}$을 스팬하는 잡음 부분 공간 고유 벡터로 분산될 수 있는 이유이다. 이는 신호 임베딩 이론^[2][7]에 기반하며, 다양체의 위상수학 이론으로도 설명할 수 있다.^[4]

다른 방법들과의 비교

MUSIC은 구성 요소의 개수를 미리 알고 있을 때, 최종 보고서에서 노이즈를 무시하기 위해 이 정보를 활용하기 때문에 노이즈가 있는 상황에서 DFT 스펙트럼의 피크를 선택하는 것과 같은 간단한 방법보다 성능이 우수하다.

DFT와 달리, 추정 함수는 DFT 빈 주파수뿐만 아니라 어떤 주파수에 대해서도 평가될 수 있으므로, 한 샘플보다 높은 정확도로 주파수를 추정할 수 있다. 이는 초해상도의 한 형태이다.

주요 단점은 구성 요소의 개수를 미리 알아야 하므로 원래 방법은 더 일반적인 경우에 사용할 수 없다는 것이다. 자기상관 행렬의 통계적 속성만으로 소스 구성 요소의 개수를 추정하는 방법이 존재한다. 예를 들어 다음을 참조하라.^[8] 또한 MUSIC은 공존하는 소스가 비상관적이라고 가정하며, 이는 실제 적용을 제한한다.

최근 반복적 준모수 방법은 매우 상관된 소스에도 불구하고 강력한 초해상도를 제공한다. 예를 들어, SAMV^[9][10]

기타 응용

MUSIC의 수정된 버전인 시간 역전 MUSIC(TR-MUSIC)은 최근 전산 시간 역전 이미징에 적용되었다.^[11][12] MUSIC 알고리즘은 또한 C 라이브러리 - libmusic^[13](MATLAB 구현 포함)^[14] 형태로 DTMF 주파수(이중 주파수 다중 주파수 신호)의 빠른 감지를 위해 구현되었다.

같이 보기

• 스펙트럼 밀도 추정
• 주기그램
• 정합 필터
• 웰치의 방법
• 바틀릿의 방법
• SAMV
• 무선 방향 탐지
• 피치 감지 알고리즘
• 고해상도 현미경