레빈슨 재귀 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 유도
3. 블록 레빈슨 알고리즘
4. 참고 문헌
참조

1. 개요

레빈슨 재귀 알고리즘은 주 대각선이 0이 아닌 값을 갖는 토플리츠 행렬을 포함하는 행렬 방정식을 풀기 위한 재귀적 방법이다. 이 알고리즘은 순방향 및 역방향 벡터를 사용하여 해를 구하며, 대칭 행렬의 경우 계산을 단순화할 수 있다. 블록 토플리츠 행렬에도 적용될 수 있으며, 신호 처리 분야에서 활용된다.

더 읽어볼만한 페이지

수치해석학 - 수학적 최적화
수학적 최적화는 주어진 집합에서 실수 또는 정수 변수를 갖는 함수의 최댓값이나 최솟값을 찾는 문제로, 변수 종류, 제약 조건, 목적 함수 개수에 따라 다양한 분야로 나뉘며 여러 학문 분야에서 활용된다.
수치해석학 - 선형대수학
선형대수학은 벡터, 벡터 공간, 행렬 등의 개념으로 선형 방정식과 선형 변환을 연구하는 수학 분야로, 선형성을 활용해 행렬로 표현 및 계산하며, 연립일차방정식 해법, 고유값/고유벡터를 통한 행렬 분석, 벡터 공간의 기저와 차원 등을 다루고 물리학, 공학, 컴퓨터 과학 등 다양한 분야에 응용된다.
행렬 - 스핀 (물리학)
스핀은 양자역학적 각운동량으로, 양자화된 값을 가지며 자기 쌍극자 모멘트를 유발하여 다양한 분야에 응용되고 스핀트로닉스 기술 발전에 기여하지만, 전자의 스핀 기원은 아직 완전히 밝혀지지 않았다.
행렬 - 파울리 행렬
파울리 행렬은 양자역학에서 스핀을 나타내는 데 사용되는 에르미트 행렬이자 유니타리 행렬로, 행렬식은 -1이고 대각합은 0이며, 리 대수의 생성원이자 파울리 벡터로 정의되어 다양한 물리학 분야에서 활용된다.

레빈슨 재귀 알고리즘
개요
분야	선형 대수학
유형	재귀 알고리즘
시간 복잡도	Θ(n²)
공간 복잡도	O(n²)
상세 정보
계산 복잡도 (덧셈 및 곱셈)	4n²
계산 복잡도 (나눗셈)	3n²
다른 알고리즘의 복잡도	Θ(n logⁿ n)

2. 유도

(내용 없음)

2. 1. 배경

행렬 방정식은 다음 형식을 따른다.

:

\mathbf M \, \vec x = \vec y

레빈슨-더빈 알고리즘은 행렬 M이 0이 아닌 주 대각선을 가진 알려진 토플리츠 행렬일 경우, 이러한 형태의 모든 방정식을 푸는 데 사용될 수 있다. 여기서

\vec y

는 이미 알고 있는 벡터이고,

\vec x

는 아직 결정되지 않은 미지수 ''x''_''i''들로 이루어진 벡터이다.

이 문서에서는 다음과 같은 표기법을 사용한다.

''ê''_''i''는 ''i''번째 성분만 1이고 나머지 성분은 모두 0인 벡터를 나타낸다. 벡터의 길이는 문맥에 따라 결정된다.
''N''은 위 행렬 M의 차원(크기)을 나타낸다. 즉, M은 ''N''×''N'' 크기의 정사각 행렬이다.
위첨자는 귀납 지수를 나타내고, 아래첨자는 행렬이나 벡터의 성분 지수를 나타낸다. 예를 들어, 행렬 T^''n''은 행렬 M의 왼쪽 위 ''n''×''n'' 부분 행렬을 의미한다. 즉, T^''n''의 (''i'', ''j'') 성분은 M의 (''i'', ''j'') 성분과 같다 (''T''^''n''_''ij'' = ''M''_''ij'').

T^''n'' 또한 토플리츠 행렬이며, 다음과 같은 형태로 나타낼 수 있다.

:

\mathbf T^n = \begin{bmatrix}t_0    & t_{-1}  & t_{-2}  & \dots  & t_{-n+1}   \\t_1    & t_0     & t_{-1}  & \dots  & t_{-n+2} \\t_2    & t_1     & t_0     & \dots  & t_{-n+3} \\\vdots & \vdots  & \vdots  & \ddots & \vdots   \\t_{n-1}& t_{n-2} & t_{n-3} & \dots  & t_0\end{bmatrix}

2. 2. 단계

이 알고리즘은 두 단계로 진행된다. 첫 번째 단계에서는 순방향 및 역방향 벡터라고 하는 두 세트의 벡터가 설정된다. 순방향 벡터는 역방향 벡터 집합을 얻는 데 사용되며, 이후 즉시 폐기될 수 있다. 역방향 벡터는 원하는 해를 구축하는 데 사용되는 두 번째 단계에 필요하다.

레빈슨-더빈 재귀는

\vec f^n

으로 표시되는 n^번째 "순방향 벡터"를 다음과 같이 정의한다.

:

\mathbf T^n \vec f^n = \hat e_1.

n^번째 "역방향 벡터"

\vec b^n

는 유사하게 정의되며, 다음을 만족하는 길이 n의 벡터이다.

:

\mathbf T^n \vec b^n = \hat e_n.

M이 대칭 행렬인 경우 중요한 단순화가 발생할 수 있다. 이때 두 벡터는 bⁿ_i = fⁿ_n+1−i로 관련된다. 즉, 서로 행을 반전시킨 것이다. 이는 해당 특수한 경우에 추가적인 계산을 절약할 수 있다.

2. 3. 역방향 벡터 구하기

행렬이 대칭이 아니더라도, 길이 ''n'' - 1의 벡터로부터 ''n''^번째 정방향 및 역방향 벡터를 찾을 수 있다. 먼저, 0을 사용하여 정방향 벡터를 확장하면 다음과 같다.

:

\mathbf T^n \begin{bmatrix} \vec f^{n-1} \\ 0 \\ \end{bmatrix} =\begin{bmatrix}\        & \               & \     & t_{-n+1}   \\\        & \mathbf T^{n-1} & \     & t_{-n+2} \\\        & \               & \     & \vdots   \\t_{n-1}  & t_{n-2}         & \dots & t_0      \\\end{bmatrix}\begin{bmatrix}  \            \\\vec f^{n-1} \\\            \\0            \\\            \\\end{bmatrix} =\begin{bmatrix}  1            \\0            \\\vdots       \\0            \\\varepsilon_f^n\end{bmatrix}.

'''''T''^''n''−1'''에서 '''''Tⁿ''''''으로 이동할 때, 0을 사용하여 정방향 벡터를 확장하면 행렬에 추가된 추가적인 ''열''은 해에 영향을 주지 않는다. 그러나 행렬에 추가된 추가적인 ''행''은 해에 영향을 주어, 마지막 위치에서 오차 항 ''ε''_''f''가 발생한다. 위의 방정식에서 이 오차 항의 값은 다음과 같다.

:

\varepsilon_f^n \ = \  \sum_{i=1}^{n-1} \ M_{ni} \  f_{i}^{n-1} \ = \ \sum_{i=1}^{n-1} \  t_{n-i} \ f_{i}^{n-1}.

이 오차는 나중에 새로운 정방향 벡터에서 제거된다. 먼저 역방향 벡터도 비슷한 방식(반대 순서)으로 확장해야 한다. 역방향 벡터의 경우 다음과 같다.

:

\mathbf T^n \begin{bmatrix} 0 \\ \vec b^{n-1} \\ \end{bmatrix} =\begin{bmatrix}t_0     & \dots & t_{-n+2}         & t_{-n+1} \\\vdots  & \     & \               & \       \\t_{n-2} & \     & \mathbf T^{n-1} & \       \\t_{n-1} & \     & \               &\end{bmatrix}\begin{bmatrix}  \            \\0            \\\            \\\vec b^{n-1} \\\            \\\end{bmatrix} =\begin{bmatrix}  \varepsilon_b^n  \\0             \\\vdots        \\0             \\1\end{bmatrix}.

이전과 마찬가지로, 추가된 열은 새로운 역방향 벡터에 영향을 주지 않지만 추가된 행은 영향을 준다. 이로 인해 첫 번째 위치에 또 다른 오차 항 ''ε''_''b''가 발생하며, 그 값은 다음과 같다.

:

\varepsilon_b^n \ = \ \sum_{i=2}^n \  M_{1i} \ b_{i-1}^{n-1} \ = \ \sum_{i=1}^{n-1} \  t_{-i} \ b_i^{n-1}. \

이 두 오차 항

\varepsilon_f^n

와

\varepsilon_b^n

는 더 높은 차수의 정방향 및 역방향 벡터를 형성하는 데 사용된다. 행렬의 선형성을 이용하여 모든 스칼라

(\alpha,\beta)

에 대해 다음 항등식이 성립한다.

:

\mathbf T^n \left( \alpha\begin{bmatrix}\vec f^{n-1} \\0            \\\end{bmatrix} + \beta\begin{bmatrix}0            \\\vec b^{n-1}\end{bmatrix} \right ) = \alpha\begin{bmatrix}  1        \\0        \\\vdots   \\0        \\\varepsilon_f^n \\\end{bmatrix} + \beta\begin{bmatrix}  \varepsilon_b^n  \\0             \\\vdots        \\0             \\1\end{bmatrix}.

만약 ''α'' 와 ''β'' 가 오른쪽 항이 단위 벡터

\mathbf{e}_1 = [1, 0, \dots, 0]^T

또는

\mathbf{e}_n = [0, \dots, 0, 1]^T

가 되도록 선택되면, 괄호 안의 벡터 합은 각각 ''n''^번째 정방향 또는 역방향 벡터의 정의를 만족하게 된다.

''n''^번째 정방향 벡터

\vec f^n

와 역방향 벡터

\vec b^n

를 구하기 위해 다음과 같이 계수

\alpha^n_{f}, \beta^n_{f}

와

\alpha^n_{b}, \beta^n_{b}

를 사용한 선형 결합으로 나타낸다.

:

\vec f^n = \alpha^n_{f} \begin{bmatrix} \vec f^{n-1}\\0\end{bmatrix}+\beta^n_{f}\begin{bmatrix}0\\\vec b^{n-1}\end{bmatrix}

:

\vec b^n = \alpha^n_{b}\begin{bmatrix}\vec f^{n-1}\\0\end{bmatrix}+\beta^n_{b}\begin{bmatrix}0\\\vec b^{n-1}\end{bmatrix}.

이전의 선형 결합 항등식과 위 두 벡터 정의에

{\mathbf T}^n

을 적용하면 다음 방정식이 얻어진다.

:

\begin{bmatrix} 1 & \varepsilon^n_b \\0 & 0 \\\vdots & \vdots \\0 & 0 \\\varepsilon^n_f & 1\end{bmatrix} \begin{bmatrix} \alpha^n_f & \alpha^n_b \\ \beta^n_f & \beta^n_b \end{bmatrix}= \begin{bmatrix}1 & 0 \\0 & 0 \\\vdots & \vdots \\0 & 0 \\0 & 1\end{bmatrix}.

위 벡터 방정식에서 0으로만 구성된 중간 행들을 무시하면 다음과 같은 2x2 행렬 방정식만 남는다.

:

\begin{bmatrix} 1 & \varepsilon^n_b \\ \varepsilon^n_f & 1 \end{bmatrix} \begin{bmatrix} \alpha^n_f & \alpha^n_b \\ \beta^n_f & \beta^n_b \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}.

이 방정식을 크래머의 공식 등을 이용하여 풀면 계수

\alpha, \beta

를 구할 수 있고, 이를 통해 새로운 정방향 및 역방향 벡터는 다음과 같이 표현된다.

:

\vec f^n = {1 \over { 1 - \varepsilon_b^n \varepsilon_f^n }}          \begin{bmatrix} \vec f^{n-1} \\ 0 \end{bmatrix}

{ \varepsilon_f^n \over { 1 - \varepsilon_b^n \varepsilon_f^n }}\begin{bmatrix} 0 \\ \vec b^{n-1} \end{bmatrix}

:

\vec b^n =  { 1 \over { 1 - \varepsilon_b^n \varepsilon_f^n }}         \begin{bmatrix} 0 \\ \vec b^{n-1} \end{bmatrix}

{ \varepsilon_b^n \over { 1 - \varepsilon_b^n \varepsilon_f^n }}\begin{bmatrix} \vec f^{n-1} \\ 0 \end{bmatrix}.

이 벡터 합을 계산하면 이전 단계의 벡터로부터 ''n''^번째 정방향 및 역방향 벡터를 얻을 수 있다. 재귀를 시작하기 위한 첫 번째 정방향 및 역방향 벡터는 다음과 같다.

:

\vec f^1 = \vec b^1 = \left[ {1 \over M_{11}} \right] = \left[ {1 \over t_0} \right].

2. 4. 역방향 벡터 사용

이전 단계에서 얻은 행렬 M에 대한 ''N''개의 후방 벡터를 사용하면 다음과 같은 일반적인 형태의 방정식을 풀 수 있다.

:

\vec y = \mathbf M \  \vec x.

이 방정식의 해

\vec x

는 후방 벡터를 구했던 것과 유사한 재귀적인 방식으로 구성할 수 있다. 이를 위해 해

\vec x

를 중간 단계의 해 벡터

\vec x^n

(단,

\vec x^N = \vec x

)으로 나누어 생각한다.

해는 다음 관계식을 이용하여 재귀적으로 구성된다.

:

\mathbf T^{n-1}\begin{bmatrix}  x_1^{n-1}     \\x_2^{n-1}     \\\vdots   \\x_{n-1}^{n-1} \\\end{bmatrix} =\begin{bmatrix}  y_1     \\y_2     \\\vdots   \\y_{n-1}\end{bmatrix}.

이제 차원을 하나 늘려 ''n''차 정방 퇴플리츠 행렬

\mathbf T^n

을 고려하고, 이전 단계의 해 벡터

x^{n-1}

에 0을 추가하여 다음과 같이 표현한다. 이때 오차 항

\varepsilon_x^{n-1}

이 발생한다.

:

\mathbf T^{n}\begin{bmatrix}  x_1^{n-1}     \\x_2^{n-1}     \\\vdots   \\x_{n-1}^{n-1} \\0\end{bmatrix} =\begin{bmatrix}  y_1     \\y_2     \\\vdots   \\y_{n-1} \\\varepsilon_x^{n-1}\end{bmatrix}.

''n''번째 후방 벡터

\vec b^n

를 이용하여 이 오차 항을 상쇄하고, ''n''번째 요소가

y_n

이 되도록 조정할 수 있다.

:

\mathbf T^{n} \left (\begin{bmatrix}  x_1^{n-1}     \\x_2^{n-1}     \\\vdots   \\x_{n-1}^{n-1} \\0 \\\end{bmatrix} + (y_n - \varepsilon_x^{n-1}) \  \vec b^n \right ) =\begin{bmatrix}  y_1     \\y_2     \\\vdots   \\y_{n-1} \\y_n\end{bmatrix}.

이 과정을 ''n'' = 1부터 ''N''까지 반복하면 최종적으로 원하던 해

\vec x = \vec x^N

을 얻게 된다.

실제 계산에서는 이 과정이 다른 단계들과 동시에 진행되는 경우가 많지만, 개념적으로는 독립된 하나의 단위로 이해할 수 있다.

3. 블록 레빈슨 알고리즘

만약 행렬 '''M'''이 엄격한 토플리츠 행렬은 아니지만 블록 행렬 형태의 토플리츠 행렬이라면, 이 블록 토플리츠 행렬을 행렬 원소를 가진 토플리츠 행렬로 간주하여 레빈슨 재귀 알고리즘을 거의 동일한 방식으로 유도할 수 있다(Musicus 1988). 이러한 블록 토플리츠 행렬은 여러 신호 스트림(예: MIMO 시스템)이나 주기 정상 신호를 처리하는 신호 처리 알고리즘에서 자연스럽게 나타난다.

4. 참고 문헌

Trench, W. F. (1964). "An algorithm for the inversion of finite Toeplitz matrices." ''J. Soc. Indust. Appl. Math.'', v. 12, pp. 515–522.
Musicus, B. R. (1988). "Levinson and Fast Choleski Algorithms for Toeplitz and Almost Toeplitz Matrices." ''RLE TR'' No. 538, MIT. [http://dspace.mit.edu/bitstream/1721.1/4954/1/RLE-TR-538-20174000.pdf]

참조

_[1] 논문 Bojanczyk et al. (1995).
_[2] 논문 Brent (1999).
_[3] 논문 Krishna & Wang (1993).
_[4] 웹사이트 Archived copy https://web.archive.[...] 2013-04-01
_[5] 웹사이트 Archived copy https://web.archive.[...] 2009-04-28
_[6] 웹사이트 Archived copy https://web.archive.[...] 2022-01-12
_[7] 웹사이트 Archived copy https://web.archive.[...] 2006-08-15

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com