Levinsonova rekurze - Levinson recursion

Levinsonova rekurze nebo Rekurze Levinson – Durbin je postup v lineární algebra na rekurzivně vypočítat řešení rovnice zahrnující a Toeplitzova matice. The algoritmus běží dovnitř Θ (n²) času, což je výrazné zlepšení oproti Eliminace Gauss-Jordan, který běží v Θ (n³).

Algoritmus Levinson – Durbin jako první navrhl Norman Levinson v roce 1947 vylepšeno o James Durbin v roce 1960 a následně se zlepšil na 4n² a poté 3n² násobení W. F. Trenchem a S. Zoharem.

Mezi další metody zpracování dat patří Schurův rozklad a Choleský rozklad. Ve srovnání s nimi má Levinsonova rekurze (zejména rozdělená Levinsonova rekurze) tendenci být rychlejší výpočetně, ale citlivější na výpočetní nepřesnosti jako chyby zaokrouhlování.

Bareissův algoritmus pro Toeplitzovy matice (nezaměňovat s generálem Bareissův algoritmus ) běží přibližně stejně rychle jako Levinsonova rekurze, ale využívá Ó(n²) prostor, zatímco Levinsonova rekurze využívá pouze Ó(n) prostor. Algoritmus Bareiss však je numericky stabilní,^[1][2] zatímco Levinsonova rekurze je v nejlepším případě jen slabě stabilní (tj. vykazuje numerickou stabilitu pro dobře podmíněný lineární systémy).^[3]

Novější algoritmy, tzv asymptoticky rychle nebo někdy super rychlý Toeplitzovy algoritmy, lze vyřešit v Θ (n log^pn) pro různé p (např. p = 2,^[4][5] p = 3 ^[6]). Levinsonova rekurze zůstává populární z několika důvodů; pro jednoho je to ve srovnání relativně snadné pochopit; pro jiného to může být rychlejší než superrychlý algoritmus pro malé n (obvykle n < 256).^[7]

Derivace

Pozadí

Maticové rovnice mají tvar:

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

Algoritmus Levinson – Durbin lze použít pro jakoukoli takovou rovnici, pokud M je známý Toeplitzova matice s nenulovou hlavní úhlopříčkou. Tady ${ displaystyle { vec {y}}}$ je známý vektor, a ${ displaystyle { vec {x}}}$ je neznámý vektor čísel X_i ještě bude stanoveno.

V zájmu tohoto článku E_i je vektor složený výhradně z nul, kromě jeho ith místo, které drží hodnotu jedna. Jeho délka bude implicitně určena okolním kontextem. Termín N odkazuje na šířku matice výše - M je N×N matice. Nakonec v tomto článku odkazují horní indexy na indukční index, zatímco indexy označují indexy. Například (a definice) v tomto článku matice Tⁿ je n × n matice, která kopíruje levý horní n × n blokovat od M - to je, Tⁿ_ij = M_ij.

Tⁿ je také Toeplitzova matice; což znamená, že jej lze zapsat jako:

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

Úvodní kroky

Algoritmus probíhá ve dvou krocích. V prvním kroku byly použity dvě sady vektorů zvané vpřed a dozadu vektory. Vpřed vektory se používají k získání sady zpětných vektorů; pak mohou být okamžitě zlikvidovány. Zpětné vektory jsou nezbytné pro druhý krok, kde se používají k vytvoření požadovaného řešení.

Rekurze Levinson – Durbin definuje n^th "vpřed vektor", označeno ${ displaystyle { vec {f}} ^ {n}}$, jako vektor délky n který splňuje:

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

The n^th "zpětný vektor" ${ displaystyle { vec {b}} ^ {n}}$ je definován podobně; je to vektor délky n který splňuje:

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

Důležité zjednodušení může nastat, když M je symetrická matice; pak jsou dva vektory příbuzné bⁿ_i = Fⁿ_n+1−i- to znamená, že se vzájemně obracejí. To může v tomto zvláštním případě ušetřit nějaké další výpočty.

Získání zpětných vektorů

I když matice není symetrická, pak n^th dopředný a zpětný vektor lze najít z vektorů délky n - 1 následovně. Nejprve lze dopředný vektor rozšířit o nulu, abychom získali:

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

Při odchodu Tⁿ⁻¹ na Tⁿ, navíc sloupec přidán do matice nebude rušit řešení, když se k prodloužení dopředného vektoru použije nula. Nicméně navíc řádek přidán do matice má narušilo řešení; a vytvořil nežádoucí termín chyby ε_F který se vyskytuje na posledním místě. Výše uvedená rovnice jí dává hodnotu:

${ displaystyle epsilon _ {f} ^ {n} = součet _ {i = 1} ^ {n-1} M_ {ni} f_ {i} ^ {n-1} = součet _ {i = 1} ^ {n-1} t_ {ni} f_ {i} ^ {n-1}.}$

Tato chyba bude brzy vrácena a odstraněna z nového dopředného vektoru; ale nejprve musí být zpětný vektor rozšířen podobným (i když obráceným) způsobem. Pro zpětný vektor,

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

Stejně jako dříve zvláštní sloupec přidaný do matice tento nový zpětný vektor nepůsobí rušivě; ale další řádek ano. Zde máme další nechtěnou chybu ε_b s hodnotou:

${ displaystyle epsilon _ {b} ^ {n} = součet _ {i = 2} ^ {n} M_ {1i} b_ {i-1} ^ {n-1} = součet _ {i = 1} ^ {n-1} t _ {- i} b_ {i} ^ {n-1}. }$

Tyto dva chybové výrazy lze použít k vytvoření dopředných a zpětných vektorů vyššího řádu popsaných níže. Pomocí linearity matic platí pro všechny následující identita ${ 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}}.}$

Li α a β jsou vybrány tak, aby výnosy na pravé straně E₁ nebo E_n, potom množství v závorkách splní definici n^th dopředu nebo dozadu vektor. Při výběru alfa a beta je vektorový součet v závorkách jednoduchý a poskytuje požadovaný výsledek.

Chcete-li najít tyto koeficienty, ${ displaystyle alpha _ {f} ^ {n}}$, ${ displaystyle beta _ {f} ^ {n}}$ jsou takové, že:

${ displaystyle { vec {f}} ^ {n} = alpha _ {f} ^ {n} { begin {bmatrix} { vec {f}} ^ {n-1} 0 end { bmatrix}} + beta _ {f} ^ {n} { begin {bmatrix} 0 { vec {b}} ^ {n-1} end {bmatrix}}}$

resp ${ displaystyle alpha _ {b} ^ {n}}$, ${ displaystyle beta _ {b} ^ {n}}$ jsou takové, že:

${ displaystyle { vec {b}} ^ {n} = alpha _ {b} ^ {n} { begin {bmatrix} { vec {f}} ^ {n-1} 0 end { bmatrix}} + beta _ {b} ^ {n} { begin {bmatrix} 0 { vec {b}} ^ {n-1} end {bmatrix}}.}$

Vynásobením obou předchozích rovnic číslem ${ displaystyle { mathbf {T}} ^ {n}}$ jeden dostane následující rovnici:

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

Nyní jsou všechny nuly uprostřed dvou vektorů výše ignorovány a sbaleny, zbývá pouze následující rovnice:

${ 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}} = { start { bmatrix} 1 a 0 0 a 1 end {bmatrix}}.}$

S těmito vyřešenými pro (pomocí inverzního vzorce matice Cramer 2 × 2) jsou nové vektory vpřed a vzad:

${ displaystyle { vec {f}} ^ {n} = {1 nad {1- epsilon _ {b} ^ {n} epsilon _ {f} ^ {n}}} { begin {bmatrix} { vec {f}} ^ {n-1} 0 end {bmatrix}} - { epsilon _ {f} ^ {n} přes {1- epsilon _ {b} ^ {n} epsilon _ {f} ^ {n}}} { begin {bmatrix} 0 { vec {b}} ^ {n-1} end {bmatrix}}}$

${ displaystyle { vec {b}} ^ {n} = {1 nad {1- epsilon _ {b} ^ {n} epsilon _ {f} ^ {n}}} { begin {bmatrix} 0 { vec {b}} ^ {n-1} end {bmatrix}} - { epsilon _ {b} ^ {n} přes {1- epsilon _ {b} ^ {n} epsilon _ {f} ^ {n}}} { begin {bmatrix} { vec {f}} ^ {n-1} 0 end {bmatrix}}.}$

Provedení těchto vektorových součtů pak dává n^th dopředu a dozadu vektory z předchozích. Zbývá jen najít první z těchto vektorů a poté některé rychlé součty a násobení dají zbývajícím. První vektory vpřed a vzad jsou jednoduše:

${ displaystyle { vec {f}} ^ {1} = { vec {b}} ^ {1} = doleva [{1 nad M_ {11}} doprava] = doleva [{1 nad t_ {0}} vpravo].}$

Použití zpětných vektorů

Výše uvedené kroky dávají N zpětné vektory pro M. Odtud je libovolnější rovnice:

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

Řešení lze postavit stejným rekurzivním způsobem, jakým byly vytvořeny zpětné vektory. V souladu s tím ${ displaystyle { vec {x}}}$ musí být zobecněn na posloupnost meziproduktů ${ displaystyle { vec {x}} ^ {n}}$, takový, že ${ displaystyle { vec {x}} ^ {N} = { vec {x}}}$.

Řešení je pak vytvořeno rekurzivně, když si všimnete, že pokud

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

Poté se znovu rozšíří s nulou a v případě potřeby se definuje chybová konstanta:

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

Poté můžeme použít n^th zpětný vektor k odstranění chybového členu a jeho nahrazení požadovaným vzorcem následujícím způsobem:

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

Prodloužení této metody do n = N získá řešení ${ displaystyle { vec {x}}}$.

V praxi se tyto kroky často provádějí souběžně se zbytkem postupu, ale tvoří ucelenou jednotku a zaslouží si, aby s nimi bylo zacházeno jako s vlastním krokem.

Blokovat Levinsonův algoritmus

Li M není přísně Toeplitz, ale blok Toeplitz, Levinsonova rekurze může být odvozena v podstatě stejným způsobem, pokud jde o blokovou Toeplitzovu matici jako Toeplitzovu matici s maticovými prvky (Musicus 1988). Blokové Toeplitzovy matice vznikají přirozeně v algoritmech zpracování signálu, když se jedná o více toků signálu (např. V MIMO systémy) nebo cyklostacionární signály.

Viz také

• Rozdělit Levinsonovu rekurzi
• Lineární predikce
• Autoregresní model

Poznámky

Reference

Definování zdrojů

• Levinson, N. (1947). „Kritérium chyby Wiener RMS v návrhu a predikci filtru.“ J. Math. Phys., v. 25, s. 261–278.
• Durbin, J. (1960). „Přizpůsobení modelů časových řad.“ Rev. Inst. Int. Stat., v. 28, s. 233–243.
• Trench, W. F. (1964). „Algoritmus pro inverzi konečných Toeplitzových matic.“ J. Soc. Indust. Appl. Matematika., v. 12, s. 515–522.
• Musicus, B. R. (1988). „Algoritmy Levinson a Fast Choleski pro matice Toeplitz a téměř Toeplitz.“ RLE TR Č. 538, MIT. [1]
• Delsarte, P. a Genin, Y. V. (1986). „Rozdělený Levinsonův algoritmus.“ Transakce IEEE na akustiku, řeč a zpracování signálu, v. ASSP-34 (3), s. 470–478.

Další práce

• Bojanczyk, A.W .; Brent, R.P .; De Hoog, F.R .; Sweet, D.R. (1995). "O stabilitě Bareisse a souvisejících Toeplitzových faktorizačních algoritmů". SIAM Journal on Matrix Analysis and Applications. 16: 40–57. arXiv:1004.5510. doi:10.1137 / S0895479891221563.
• Brent R.P. (1999), „Stabilita rychlých algoritmů pro strukturované lineární systémy“, Rychlé spolehlivé algoritmy pro matice se strukturou (redaktoři - T. Kailath, A.H. Sayed), kap.4 (SIAM ).
• Bunch, J. R. (1985). „Stabilita metod pro řešení Toeplitzových soustav rovnic.“ SIAM J. Sci. Stat. Comput., v. 6, s. 349–364. [2]
• Krishna, H .; Wang, Y. (1993). „Split Levinsonův algoritmus je slabě stabilní“. Časopis SIAM o numerické analýze. 30 (5): 1498–1508. doi:10.1137/0730078.

Shrnutí

• Bäckström, T. (2004). „2.2. Rekurze Levinson – Durbin.“ Lineární prediktivní modelování řeči - omezení a rozklad párového spektra. Disertační práce. Zpráva č. 71 / Helsinki University of Technology, Laboratory of Acoustics and Audio Signal Processing. Espoo, Finsko. [3]
• Claerbout, Jon F. (1976). „Kapitola 7 - Aplikace křivek nejmenších čtverců.“ Základy zpracování geofyzikálních dat. Palo Alto: Blackwell Scientific Publications. [4]
• Stiskněte, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), „Oddíl 2.8.2. Toeplitzovy matice“, Numerické recepty: Umění vědecké práce na počítači (3. vyd.), New York: Cambridge University Press, ISBN  978-0-521-88068-8
• Golub, G.H. a Loan, C.F. Van (1996). „Oddíl 4.7: Toeplitz a související systémy“ Maticové výpočty, Johns Hopkins University Press