레빈슨 재귀

레빈슨 재귀 또는 레빈슨-두르빈 재귀는 토우플리츠 행렬을 포함하는 방정식에 대한 해결책을 재귀적으로 계산하기 위한 선형 대수학의 절차다.알고리즘은 θ(n²) 시간에 실행되며, 이는 θ(n³)에서 실행되는 가우스-요르단 제거에 비해 강력한 개선이다.

레빈슨-더빈 알고리즘은 1947년 노먼 레빈슨에 의해 처음 제안되었고, 1960년 제임스 더빈에 의해 개선되었으며, 이후 W. F. 트렌치와 S. 조하르에 의해 각각 4n², 3n² 배수로 개선되었다.

데이터를 처리하는 다른 방법으로는 Schur 분해와 Cholesky 분해가 있다.이와 비교하여, 레빈슨 재귀(특히 분할된 레빈슨 재귀)는 계산상으로는 더 빠른 경향이 있지만, 반올림 오류와 같은 계산상의 부정확성에 더 민감하다.

토우플리츠 행렬에 대한 바리스 알고리즘(일반 바리스 알고리즘과 혼동되지 않음)은 레빈슨 재귀속만큼 빠르게 실행되지만 O(n²) 공간을 사용하는 반면 레빈슨 재귀속은 O(n) 공간만 사용한다.그러나 바리스 알고리즘은 수치적으로 안정적이지만 ^[1][2]레빈슨 재귀는 기껏해야 약하게 안정되어 있을 뿐이다(즉, 잘 컨디셔닝된 선형 시스템에 대해 수치적 안정성을 나타낸다).^[3]

점증적으로 빠르거나 때로는 초고속 토플리츠 알고리즘이라고 불리는 새로운 알고리즘은 다양한 p(예: p = 2, ^[4][5]p = 3 )에 대해 θ(n logn^p)에서 해결할 수 있다.레빈슨 재귀는 여러 가지 이유로 여전히 인기가 있다. 한 가지 이유로, 그것은 비교적 이해하기 쉽다. 다른 한 가지 이유로, 그것은 작은 n (보통 n < 256)에 대한 초고속 알고리즘보다 더 빠를 수 있다.^[7]

파생

배경

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

${\displaystyle \mathbf {M} \,{\vec {x}={\vec {y}}.}$

M이 0이 아닌 주 대각선으로 알려진 토플리츠 행렬인 한, 레빈슨-더빈 알고리즘은 그러한 방정식에 사용할 수 있다.여기서 $y{\displaystyle \stackrel{}{}}$→ ${\$은(는$$) 알려진 벡터이고, $x{\displaystyle \stackrel{}{}}$ →${\$ {$x}}$은(는) 아직 결정되지 않은 숫자 x의_i 알 수 없는 벡터다$$.

이 글의 목적상, 엣은_i 값어치 1을 가지고 있는 ith 위치를 제외하고 0으로 전적으로 구성된 벡터다.그것의 길이는 주변 상황에 의해 암묵적으로 결정될 것이다.N이라는 용어는 위의 행렬의 너비를 가리킨다 – M은 N×N 행렬이다.마지막으로, 이 글에서 위첨자는 귀납 지수를 참조하는 반면, 첨자는 지수를 나타낸다.예를 들어 (그리고 정의) 이 글에서 매트릭스 T는ⁿ 왼쪽 위 n×n 블록을 M – 즉, Tⁿ_ij = M에서_ij 복사하는 n×n 매트릭스다.

T도ⁿ 토우플리츠 행렬로, 라고 쓸 수 있다는 뜻이다.

${\displaystyle \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}}.}$

소개 단계

알고리즘은 두 단계로 진행된다.첫 번째 단계에서는 전진 벡터와 후진 벡터라고 불리는 두 세트의 벡터가 설정된다.전진 벡터는 후진 벡터 세트를 얻는 데 도움을 주기 위해 사용된다. 그러면 그것들은 즉시 폐기될 수 있다.역방향 벡터는 원하는 솔루션을 구축하는 데 사용되는 두 번째 단계에 필요하다.

Levinson-Durbin 재귀는 $f$^th → ${\displaystyle n^{}}$ ${\$bec$}^{n$을$($를) n의 길이 벡터로 나타내는 n "전방 벡터"를 정의하며, 이 벡터는 다음을 만족한다.

${\displaystyle \mathbf{T}^{n}{\vec{f}^{n}={\hat{e}_{1}.}$

n^th "뒤로 향하는 벡터"${\displaystyle {\stackrel{}{}}^{}}b{\displaystyle {\stackrel{}{}}^{}}$ → ${\displaystyle n^{}}${\$displaystyle {\b}^{n}}}$은(는) 유사하게 정의되며, 이는 다음을 만족하는 길이 n의 벡터다.

${\displaystyle \mathbf{T}^{n}{\vec{b}^{n}={\hat{e}_{n}.}$

중요한 단순화는 M이 대칭 행렬일 때 발생할 수 있다. 그 다음 두 벡터는ⁿ_i b = f로ⁿ_n+1−i 연관된다. 즉, 그들은 서로의 행 역행이다.이것은 특별한 경우에 약간의 여분의 연산을 절약할 수 있다.

역방향 벡터 획득

행렬이 대칭이 아니더라도 다음과 같이 길이 n - 1의 벡터에서 n 전방^th 및 후방 벡터를 찾을 수 있다.첫째, 전방 벡터를 0으로 확장하여 다음을 얻을 수 있다.

${\displaystyle \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}\\0\\\ \\\end{bmatrix}}={\begin{bmatrix}1\\0\\\ ^{n-1}\\\.vdots \\0\\\epsilon _{f}^{n}\end{bmatrix}}.}$

T에서ⁿ⁻¹ T로ⁿ 이동할 때 매트릭스에 추가된 추가 컬럼은 전방 벡터를 확장하기 위해 0을 사용할 때 용액을 동요시키지 않는다.그러나 매트릭스에 추가된 추가 행은 해결책을 혼란스럽게 했고, 마지막 단계에서 발생하는 원하지 않는 오류 용어 ε을_f 만들었다.위의 방정식은 다음과 같은 값을 제공한다.

${\displaystyle \epsilon \epsilon _{f}^{n-1}\M_{ni}\f_{n-1}\{n-1}\\\\\sum \{n=1}^{n-1}\{n-1}\\{n-i}^{n-1}.}$

이 오류는 곧 되돌아와 새로운 전방 벡터에서 제거될 것이다. 그러나 먼저, 역방향 벡터는 유사한 (직접 역) 방식으로 확장되어야 한다.역방향 벡터에는

${\displaystyle \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}}}^{n-1}\\\ \\\end{bmatrix}}={\begin{bmatrix}\epsilon 즉\\0\\\ \\{\vec{b}{\begin{bmatrix}\{.b}\\0\\1\end{bmatrix}}^{n}\\0\\\vdots.}$

이전처럼, 행렬에 추가된 여분의 열은 이 새로운 역방향 벡터를 동요시키지 않지만 여분의 열은 그렇다.여기에 값과 함께 또 다른 원치 않는 오류가 있다_b.

${\displaystyle \epsilon \epsilon _{b}^{n}\\\\sum \{i=2}\m_{n-1}\b_{i-1}\\\\sum \{i=1}^{n-1}\{n-1}\{i}-1}.\ }$

이 두 가지 오류 용어는 다음과 같이 설명한 고차 전방 및 후방 벡터를 형성하는 데 사용할 수 있다.행렬의 선형성을 사용하여 다음 ID는 모든${\displaystyle }$(${\displaystyle \alpha }$ ,${\displaystyle \beta }$) ${\displaystyle (\alpha ,\beta )}$에 대해 유지된다$.$

${\displaystyle \mathbf {T} \left(\alpha {\begin{bmatrix}{\vec {f}}\\\ \\0\\\end{bmatrix}}+\beta {\begin{bmatrix}0\\\ \\{\vec {b}}\end{bmatrix}}\right)=\alpha {\begin{bmatrix}1\\0\\\vdots \\0\\\epsilon _{f}\\\end{bmatrix}}+\beta {\begin{bmatrix}\epsilon _{b}\\0\\\vdots \\0\\1\end{bmatrix}}.}$

α와 β를 선택하여 우측이 ê₁ 또는 ê을_n 산출하면 괄호 안의 양이 각각 n 전방^th 또는 후진 벡터의 정의를 충족한다.이러한 알파와 베타를 선택하면 괄호 안의 벡터 합이 단순하여 원하는 결과를 산출한다.

이러한 계수를 찾으려면 ${\displaystyle {\alpha f}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$ $\beta {\displaystyle {}_{}^{}}$ ${\displaystyle f_{}^{}}$ ${\displaystyle {}_{}^{}}${\$displaystyle \beta _{f}^{n}}}}}$은(는) 다음과$$ 같다.

${\displaystyle {\vec{n}^{n}=\f}{n}{bmatrix}{\bmatrix}{\vec}{n-1}\0\bmatrix}+\{f}^{f}{n}{bmatrix}}{bmatrix}}}}}}{n-1}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

및 각각 α ${\displaystyle {}_{}^{}}$ ${\$$\beta {\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$\ \$_{b}^{n}}}}$은 다음과 같다$$.

${\displaystyle {\vec{b}^{n}=\b}{b}^{n}{bmatrix}{\bmatrix}{n1}\0\bmatrix}+\{b}^{b}{n}{bmatrix}}\\\vc{n-1}}}{bmatrix}}$

이전의 두 방정식을 $모두{\displaystyle {\mathbf{}}^{}}$ T ${\displaystyle n^{}}$ ${\$에 곱하면 다음과$$ 같은 방정식이 나온다.

${\displaystyle {\begin{bmatrix}1&\epsilon _{b}^{n}\\0&0\\\vdots &\vdots \\0&0\\\epsilon _{f}^{n}&1\end{bmatrix}}{\begin{bmatrix}\alpha _{f}^{n}&\alpha _{b}^{n}\\\beta _{f}^{n}&\beta _{b}^{n}\end{bmatrix}}={\begin{bmatrix}1&0\\0&0\\\vdots &\vdots \\0&0\\0&1\end{bmatrix}}.}$

이제 위의 두 벡터 가운데에 있는 모든 0은 무시되고 무너지고, 다음 방정식만 남는다.

${\displaystyle {\begin{bmatrix}1&\epsilon _{b}^{n}\\\epsilon _{f}^{n}&1\end{bmatrix}}{\begin{bmatrix}\alpha _{f}^{n}&\alpha _{b}^{n}\\\beta _{f}^{n}&\beta _{b}^{n}\end{bmatrix}}={\begin{bmatrix}1&0\\0&1\end{bmatrix}}.}$

(Cramer 2×2 매트릭스 역 공식 사용)을 위해 해결된 새로운 전방 및 후방 벡터는 다음과 같다.

${\displaystyle {\vec {f}}^{n}={1 \over {1-\epsilon _{b}^{n}\epsilon _{f}^{n}}}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}-{\epsilon _{f}^{n} \over {1-\epsilon _{b}^{n}\epsilon _{f}^{n}}}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}}$

${\displaystyle {\vec {b}}^{n}={1 \over {1-\epsilon _{b}^{n}\epsilon _{f}^{n}}}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}-{\epsilon _{b}^{n} \over {1-\epsilon _{b}^{n}\epsilon _{f}^{n}}}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}.}$

그러면 이러한 벡터 합산을 수행하면 이전 벡터로부터 n개의^th 앞뒤 벡터를 얻는다.남은 것은 이 벡터들 중 첫 번째 벡터를 찾는 것 뿐이고, 그 다음 몇 가지 빠른 액수와 승수는 나머지 벡터를 준다.첫 번째 전진 및 후진 벡터는 다음과 같다.

${\displaystyle {\vec{f}^{1}={\vec{b}^{1}=\왼쪽[{1\over M_{11}}\right]=\왼쪽[{1\over t_{0}}\right].}$

역방향 벡터 사용

위의 단계는 M에 대한 N 역방향 벡터를 제공한다.여기서 보다 자의적인 방정식은 다음과 같다.

${\displaystyle {\vec{y}=\mathbf {M} \\vec {x}}.}$

이 솔루션은 역방향 벡터가 구축된 것과 동일한 반복적인 방식으로 구축될 수 있다.${\displaystyle {따라서}^{}}$ $x{\displaystyle \stackrel{}{}}$${\displaystyle {\stackrel{}{}}^{}}$→ ${\$$vec{$$x}}}}$은(는) 중간자 $x{\displaystyle {\stackrel{}{}}^{}}$→ n → ${\$의 순서로 일반화되어야 한다$$$.$

그런 다음 다음, 다음과 같은 사실을 알아채고 솔루션을 재귀적으로 구축한다.

${\displaystyle \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}}.}$

그런 다음 다시 0으로 확장하고 필요한 경우 오류 상수를 정의하십시오.

${\displaystyle \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}\\\epsilon _{x}^{n-1}\end{bmatrix}}.}$

그런^th 다음 n 역방향 벡터를 사용하여 오차항을 제거하고 다음과 같이 원하는 공식으로 대체할 수 있다.

${\displaystyle \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}-\epsilon _{x}^{n-1})\ {\vec {b}}^{n}\right)={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n-1}\\y_{n}\end{bmatrix}}.}$

이 방법을 n = N이 솔루션 $x{\displaystyle \stackrel{}{}}$→ ${\$까지 확장$.$

실제로 이러한 단계는 나머지 절차와 동시에 이루어지는 경우가 많지만, 일관된 단위를 형성하고 있어 자신의 단계로 취급할 만하다.

블록 레빈슨 알고리즘

M이 엄격히 토우플리츠가 아니라 블록 토플리츠인 경우, 블록 토플리츠 매트릭스를 매트릭스 요소가 있는 토우플리츠 매트릭스(Musicus 1988)로 간주함으로써 레빈슨 재귀현상을 훨씬 같은 방법으로 도출할 수 있다.블록 토플리츠 매트릭스는 다중 신호 스트림(예: MIMO 시스템) 또는 사이클로-스테이션 신호를 처리할 때 신호 처리 알고리즘에서 자연적으로 발생한다.

참고 항목

• 스플릿 레빈슨 재귀
• 선형예측
• 자기 회귀 모형

메모들

참조

소스 정의

• 레빈슨, 뉴욕주 (1947)"필터 설계 및 예측 시 Wiener RMS 오류 기준."J. 수학 물리, 25 페이지 261-278.
• 더빈, J. (1960)."시계열 모델의 적합성." Rev. 인스트 인트 통계분석, 28페이지 233-243.
• 트렌치, W. F. (1964)"유한 토우플리츠 행렬의 역전을 위한 알고리즘."J. Soc 근면하다. 답안. 수학 v. 12, 페이지 515–522.
• Musicus, B. R. (1988)"토플리츠 및 거의 토플리츠 매트릭스를 위한 레빈슨 및 패스트 숄레스키 알고리즘." RLE TR 538, MIT. [1]
• Delsarte, P.와 Genin, Y. V. (1986)."스플릿 레빈슨 알고리즘." IEEE 음향, 음성 및 신호 처리, v. ASSP-34(3), 페이지 470–478.

추가 작업

• Bojanczyk, A.W.; Brent, R.P.; De Hoog, F.R.; Sweet, D.R. (1995). "On the stability of the Bareiss and related Toeplitz factorization algorithms". SIAM Journal on Matrix Analysis and Applications. 16: 40–57. arXiv:1004.5510. doi:10.1137/S0895479891221563.
• Brent R.P. (1999), "구조화된 선형 시스템을 위한 고속 알고리즘의 안정성", 구조를 가진 매트릭스를 위한 고속 신뢰 알고리즘(편집자—T)Kailath, A.H. Sayed, ch.4 (SIAM).
• 번치, J. R. (1985)"방정식의 토플리츠 시스템 해결 방법의 안정성." SIAM J. Sci 통계분석, 6, 페이지 349–364.[2]
• Krishna, H.; Wang, Y. (1993). "The Split Levinson Algorithm is weakly stable". SIAM Journal on Numerical Analysis. 30 (5): 1498–1508. doi:10.1137/0730078.

요약

• 벡스트룀, T. (2004)"2.2. Levinson-Durbin 재귀" 음성 - 제한조건 및 선 스펙트럼 쌍 분해의 선형 예측 모델링.박사 논문.보고서 71번 / 헬싱키 공과대학 음향 및 음성 신호 처리 연구소핀란드 에스푸.[3]
• 클라르바우트, 존 F. (1976년)."7장 – 최소 제곱의 파형 애플리케이션"지구물리학적 데이터 처리의 기초.Palo Alto: Blackwell Science Publishes.[4]
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 2.8.2. Toeplitz Matrices", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
• Golub, G.H., 그리고 London, C.F. Van (1996년)."섹션 4.7 : 토플리츠 및 관련 시스템" 매트릭스 연산, 존스홉킨스 대학 출판부