next up previous
Next: 7.6 Konvergence střední hodnoty Up: 7. Cvičení 7: Konvergenční Previous: 7.4 NLMS

Subsections


7.5 Úvod do vlastního rozkladu symetrických matic

Než začneme, definujeme některé pojmy, které se budou později hodit.

7.5.0.0.1 Hermitovská transpozice:

Hermitovskou traspozici značím $ H$ v horním indexu nad symbolem matice, má význam transpozice matice a nahrazení prvků matice jejich komplexně sdruženými verzemi

$\displaystyle \mathbf{A}^H = (\mathbf{A}^T)^* = (\mathbf{A}^*)^T$ (7.15)

Jak vidíte pro reálnou matici (vektor) se hermitovská transpozice od obyčejné transpozice neliší. Vektory chápu jako matice se speciálním rozměrem (jeden řádek, nebo jeden sloupec). Vztahem (7.15) je tedy hermitovská transpozice zavedena i pro vektory.

7.5.0.0.2 Frobeniova norma:

Frobeniovu normu matice $ \mathbf{A}$ značím $ \Vert\mathbf{A}\Vert$ a definuji ji následujícím způsobem

$\displaystyle \Vert\mathbf{A}\Vert = \sqrt{\sum_{i,j} a_{i,j}^*a_{i,j}} \:\:\: \left( = \sqrt{\mathrm{tr}(\mathbf{A}^H\mathbf{A})} \right),$ (7.16)

kde součet jde přes všechny prvky $ a_{i,j}$ matice $ \mathbf{A}$. Tím je Frobeniova norma definována rověž pro vektory. Je-li $ \mathbf{a}$ sloupcový, lze (7.16) zjednodušit (odmocnica ze skalárního součinu)

$\displaystyle \Vert\mathbf{a}\Vert = \sqrt{\mathbf{a}^H\mathbf{a}},$ (7.17)

je-li navíc reálný

$\displaystyle \Vert\mathbf{a}\Vert = \sqrt{\mathbf{a}^T\mathbf{a}}.$ (7.18)

7.5.0.0.3 Vztah kvadratických forem a symetrických matic

Mějme vektor $ \mathbf{h}^T = [h_1,\ldots, h_N] \in \mathcal{R}^N$ a reálnou matici $ \mathbf{A}$ o rozměru $ N\times N$. Funkce typu

$\displaystyle \sum_{i=1}^{N}\sum_{j=1}^N a_{i,j} h_i h_j = \mathbf{h}^T \mathbf{A} \mathbf{h},$ (7.19)

kde $ a_{i,j}$ značím prvky $ \mathbf{A}$ se nazývá kvadratickou formou v $ h_1,\ldots, h_N$. Všiměte si, že je-li $ \mathbf{A}$ nesymetrická mohu ji nahradit symetrickou $ \frac{1}{2}(\mathbf{A} + \mathbf{A}^T)$ aniž by se funkce (7.19) (kvadratická forma) změnila. Při studiu kvadratických forem v reálných proměnných ( $ h_1,\ldots, h_N$) tedy stačí omezíme-li se na reálné symetrické matice $ \mathbf{A}$.

Chybový povrch $ \mathrm{E}[e^2[n]](\mathbf{w})$ se dá zapsat jako kvadratická forma (povšiměte si výrazu $ \mathbf{w}^T \mathbf{R}_{xx}\mathbf{w}$ v (4.4)). Studovat chybový povrch znamená tedy studovat kvadratickou formu, případně reálné symetrické matice (autokorelační matice $ \mathbf{R}_{xx}$ je reálná symetrická). V dalším textu se tedy zaměřím a omezím na studium reálných symetrických matic. Připomínám, že matice je symetrická právě tehdy, když

$\displaystyle \mathbf{A} = \mathbf{A}^T.$ (7.20)

(prvky symetricky umístěné vzhledem k diagonále jsou shodné $ a_{i,j} = a_{j,i}$).

Uvedu zde jeden výsledek, který se nám bude později hodit. Mějme komplexní vektor $ \mathbf{h}^T = [h_1,\ldots, h_N] \in \mathcal{C}^N$ a reálnou symetrickou matici $ \mathbf{A}$ ( $ \mathbf{A} = \mathbf{A}^T$) o rozměru $ N\times N$. Pak platí

\begin{equation*}
% latex2html id marker 18024
\begin{aligned}\mathbf{h}^T \math...
..._{i,j} (h_i^* h_j + (h_i^* h_j)^*) \in \mathcal{R}. \end{aligned}\end{equation*}

7.5.0.0.4 Ortogonální matice

Reálná čtvercová matice $ \mathbf{Q}$ se nazývá ortogonální právě tehdy, když

$\displaystyle \mathbf{Q}\mathbf{Q}^T = \mathbf{Q}^T\mathbf{Q} = \mathbf{E}.$ (7.22)

Ekvivalentně se dá říci, že sloupcové vektory tvoří ortonormální bázi $ \mathcal{R}^N$, kde $ N\times N$ je rozměr $ \mathbf{Q}$ (rozepište si maticový součin pomocí skalárních součinů sloupců $ \mathbf{Q}$). Zavedeme-li označení $ <\mathbf{A}>$ pro lineární obal sloupců matice $ \mathbf{A}$, lze uvedené tvrzení zapsat jednodušeji takto $ <\mathbf{Q}> = \mathcal{R}^N$. Povšiměte si, že z (7.22) a jednoznačnosti inverze rovněž plyne

$\displaystyle \mathbf{Q}^{-1} = \mathbf{Q}^T.$ (7.23)

7.5.0.0.5 Úloha hledání vlastních čísel a vlastních vektorů matice:

$ \lambda$ nazveme vlastním číslem matice $ \mathbf{A}$ právě tehdy, když existuje vektor $ \mathbf{v}$ tak, že platí

$\displaystyle \mathbf{A} \mathbf{v} = \lambda\mathbf{v},\;\;\;\; \Vert\mathbf{v}\Vert \neq 0.$ (7.24)

$ \mathbf{v}$ pak nazýváme vlastním vektorem matice $ \mathbf{A}$ příslušným vlastnímu číslu $ \lambda$.

Odečtením pravé strany můžeme (7.24) přepsat

$\displaystyle (\mathbf{A} -\lambda \mathbf{E}) \mathbf{v} = \mathbf{o}, \;\;\;\; \Vert\mathbf{v}\Vert \neq 0.$ (7.25)

Vlastní vektory příslušné vlastímu číslu $ \lambda$ tedy tvoří lineární prostor (až na vyjmuté triviální řešení $ \mathbf{v} = \mathbf{o}$) dimenze větší nebo rovné 1 (alespoň jedno netriviální řešení musí existovat, abychom $ \lambda$ prohlásili za vlastní číslo). Proto se při hledání vlastních vektorů stačí omezit na hledání ortonormálních bází, tohoto lineárního prostoru. Označením vlastní vektor budu tedy mínit i to, že daný vektor má normu 1.

Pokusme se nyní nalézt vlastní čísla matice $ \mathbf{A}$ o rozměru $ N\times N$. Aby rovnice (7.25) poskytla nějaká netriviální řešení $ \mathbf{v}$ (podmínka pro vlastní číslo), musí mít matice $ (\mathbf{A} -\lambda \mathbf{E})$ lineárně závislé sloupce (složky $ \mathbf{v}$ můžeme chápat jako koeficienty v lineární kombinaci sloupcových vektorů matice), tedy matice $ (\mathbf{A} -\lambda \mathbf{E})$ musí být nutně singulární. Tuto podmínku lze jednoduše zapsat pomocí jejího determinantu

$\displaystyle \vert\mathbf{A} -\lambda \mathbf{E}\vert = 0.$ (7.26)

Polynom v $ \lambda$ na levé straně se nazývá charakteristický polynom matice $ \mathbf{A}$. Snadno nahlédnete, že má stupeň $ N$ ($ N\times N$ je rozměr $ \mathbf{A}$) z definice determinantu. Platí tedy následující lemma.

Lemma 7.1   Vlastních čísel matice $ \mathbf{A}$ o rozměru $ N\times N$ je $ N$ (včetně násobnosti). Vlastní čísla reálné symetrické matice jsou reálná nebo komplexně sdružená.

Proof. [ ] Důkaz:Plyne jednoduše z toho, že vlastní čísla matice $ \mathbf{A}$ jsou kořeny jejího charakteristického polynomu. $ \qedsymbol$

Lemma 7.2   Vlastní čísla reálné symetrické matice $ \mathbf{A}$ jsou reálná, a vlastní vektory příslušné vlastním číslům $ \mathbf{A}$ mají reálné složky.

Proof. [ ] Důkaz:Z předchozího lemmatu 7.1 víme, že vlastní čísla $ \mathbf{A}$ mohou být komplexní. Vezměme libovolné vlastní číslo $ \mathbf{A}$ (z 7.1 víme, že existuje) $ \lambda \in \mathcal{C}$. A jeden k $ \lambda$ příslušný vlastní vektor $ \mathbf{v} \in \mathcal{C}^N$ (opět víme, že existuje, jinak by $ \lambda$ nebylo vlastní číslo $ \mathbf{A}$), kde $ N$ je rozměr $ \mathbf{A}$. Z (7.25) musíme uvažovat komplexní vektor, neboť máme komplexní $ \lambda$. Utvořme součin

% latex2html id marker 18142
$\displaystyle \mathbf{v}^H\mathbf{A}\mathbf{v} =^...
...a7eigr1})}
\lambda \mathbf{v}^H \mathbf{v} = \lambda \Vert \mathbf{v} \Vert^2.
$

Vyjádříme $ \lambda$

$\displaystyle \lambda = \frac{\mathbf{v}^H\mathbf{A}\mathbf{v}}{\Vert \mathbf{v} \Vert^2}.
$

Reálnost čitatele jsme ověřili v (7.21) jmenovatel je dokonce reálný kladný. Tedy $ \lambda$ je reálné a z (7.25) jsou reálné i k němu příslušné vlastní vektory. $ \qedsymbol$

Lemma 7.3   Vlastní vektory příslušné různým vlastním číslům reálné symetrické matice $ \mathbf{A}$ jsou navzájem ortogonální.

Proof. [ ] Důkaz:Nechť $ \lambda_1 \neq \lambda_2$ jsou vlastní čísla $ \mathbf{A}$. Existují tedy vektory $ \mathbf{v_1}$, $ \mathbf{v_2}$ (k nim příslušné vlasní vektory) tak , že

\begin{displaymath}\begin{gathered}\mathbf{A}\mathbf{v_1} = \lambda_1 \mathbf{v_...
...{v_2}^T\mathbf{A} = \lambda_2 \mathbf{v_2}^T, \\ \end{gathered}\end{displaymath} (7.27)

(druhou rovnost jsem pouze transponoval a použil symetrii $ \mathbf{A}$). Součin $ \mathbf{v_2}^T\mathbf{A}\mathbf{v_1}$ pak můžeme zjednodušit různými způsoby, podle toho, kterou z rovností (7.27) použijeme

\begin{equation*}\begin{aligned}\mathbf{v_2}^T\mathbf{A}\mathbf{v_1} &= \lambda_...
...bf{v_1} \\ &= \lambda_2 \mathbf{v_2}^T\mathbf{v_1}, \end{aligned}\end{equation*}

tedy

$\displaystyle \lambda_1 \mathbf{v_2}^T\mathbf{v_1} = \lambda_2 \mathbf{v_2}^T\mathbf{v_1} .$ (7.29)

Je-li skalární součin $ \mathbf{v_2}^T\mathbf{v_1}$ různý od 0, můžeme jím vydělit a dostáváme ihned spor $ \lambda_1 = \lambda_2$. Proto musí být skalární součin $ \mathbf{v_2}^T\mathbf{v_1}$ nutně nulový a oba vektory jsou tedy navzájem ortogonální. $ \qedsymbol$

Lemma 7.4   Nechť $ \lambda_i$ je vlastní číslo násobnosti $ K_i$ reálné symetrické matice $ \mathbf{A}$ o rozměru $ N\times N$, pak dimenze prostoru řešení (7.25) je rovna $ K_i$.

Závěr věty lze formulovat ekvivaleně takto: Maximální počet lineárně nezávislých vlastních vektorů příslušných $ \lambda_i$ je roven $ K_i$. Nebo, hodnost $ (\mathbf{A} - \lambda_i \mathbf{E})$ je $ N-K_i$.

Proof. [ ] Důkaz:Nechť platí předpoklad tvrzení. Dokážu, že ke každému $ \lambda_i$ lze nalézt $ K_i$ lineárně nezávislých vektorů. Z lematu 7.3 pak plyne, že tento počet nemůže být vyšší (jinak by prostory řešení (7.25) pro různá vlastní čísla nebyly navzájem ortogonálními podprostory $ \mathcal{R}^N$).

Označme $ \mathbf{v}_{i,0}$ vlastní vektor příslušný k $ \lambda_i$ (z (7.24) víme, že jeden určitě existuje).

Utvořme ortogonální matici $ \mathbf{Q}$

\begin{displaymath}\begin{gathered}\mathbf{Q}_1 = [ \mathbf{v}_{i,0} \vert \tild...
...1 ],\\ \mathbf{Q}_1^T \mathbf{Q}_1 = \mathbf{E}. \end{gathered}\end{displaymath} (7.30)

Povšiměte si, že volba $ \tilde{\mathbf{Q}}_1$ není nijak jednoznačná7.1. Utvořme součin

$\displaystyle \mathbf{Q}_1^T \mathbf{A} \mathbf{Q}_1 = \left[ \begin{array}{c} ...
...t c} \lambda_i & \mathbf{o}^T \\ \mathbf{o} & \mathbf{A}_1 \end{array}\right] .$ (7.31)

V posledním kroku jsem označil $ \mathbf{A}_1 = \tilde{\mathbf{Q}}_1^T \mathbf{A} \tilde{\mathbf{Q}}_1$. Použitím (7.30) a vlastností determinantu 7.2. dostaneme

$\displaystyle \vert\mathbf{Q}_1^T\vert \vert\mathbf{Q}_1\vert = \vert\mathbf{Q}_1^T \mathbf{Q}_1\vert = \vert\mathbf{E}\vert = 1.$ (7.32)

S použitím (7.32), (7.31) (a stejné vlastnosti determinantu) nyní můžeme zapsat charakteristický polynom $ \mathbf{A}$ pomocí $ \mathbf{A}_1$

\begin{equation*}\begin{aligned}\vert\mathbf{A} - \lambda \mathbf{E}\vert &= \ve...
...lambda)\vert\mathbf{A}_1- \lambda \mathbf{E}\vert . \end{aligned}\end{equation*}

Z (7.33) plyne, že násobnost $ \lambda_i$ pro $ \mathbf{A}_1$ se oproti $ \mathbf{A}$ snížila o 1 tedy na $ K_i-1$ (jestliže $ K_i=1$ tak $ \lambda_i$ vůbec není vlastním číslem $ \mathbf{A}_1$) jinak mají $ \mathbf{A}_1$ a $ \mathbf{A}$ všechna ostatní vlastní čísla totožná včetně násobností.

V případě, že $ K_i=1$ jsme již $ K_i=1$ vlastních lineárně nezávislých vlastních vektorů našli a jsme hotovi. V opačném případě postupujeme následovně. Jelikož $ \mathbf{A}_1$ má vlastní číslo $ \lambda_i$, existuje k němu příslušný vlastní vektor. Označme ho $ \mathbf{u}_{i,1}$. Tvrdím, že vektor $ \mathbf{v}_{i,1} = \tilde{\mathbf{Q}}_1\mathbf{u}_{i,1}$ je vlastním vektorem $ \mathbf{A}$

\begin{equation*}\begin{aligned}\mathbf{A}\mathbf{v}_{i,1} &= \mathbf{Q}_1\mathb...
...bda_i \mathbf{u}_{i,1} = \lambda_i \mathbf{v}_{i,1} \end{aligned}\end{equation*}

ortogonálním k $ \mathbf{v}_{i,0}$

$\displaystyle \mathbf{v}_{i,0}^T \mathbf{v}_{i,1} = \mathbf{v}_{i,0}^T \tilde{\mathbf{Q}}_1 \mathbf{u}_{i,1} = \mathbf{o}^T \mathbf{u}_{i,1} = 0.$ (7.35)

Nyní můžeme postup opakovat, s tím, že v $ k$-tém kroku volíme ortogonální matici $ \mathbf{Q}_k$ způsobem $ \mathbf{Q}_k =
[ \mathbf{\mathbf{v}_{i,0}},\ldots,\mathbf{\mathbf{v}_{i,k-1}}
\vert\tilde{\mathbf{Q}}_k ]$ dokud $ \mathbf{A}_k$ má vlastní číslo $ \lambda_i$. Uvedený způsobem získáme právě $ K_i$ navzájem ortonormálních vektorů příslušných $ \lambda_i$. $ \qedsymbol$

Lemma 7.5   I. Pro každou reálnou symetrickou matici $ \mathbf{A}$ rozměru $ N\times N$ existuje rozklad typu 7.3

$\displaystyle \mathbf{A} = \mathbf{V} \mathbf{D} \mathbf{V}^T,$ (7.36)

kde $ \mathbf{V}$ je ortogonální a $ \mathbf{D}$ diagonální.

II. Mějme libovolný rozklad matice $ \mathbf{A}$ typu (7.36) výše uvedených vlastností, pak sloupcové vektory matice $ \mathbf{V}$ v rozkladu jsou vlastními vektory $ \mathbf{A}$ a diagonální prvky matice $ \mathbf{D}$ v rozkladu jsou vlastní čísla $ \mathbf{A}$ (diagonála $ \mathbf{D}$ obsahuje každé vlastní číslo $ \mathbf{A}$ právě tolikrát, kolik činí jeho násobnost). Tím je $ \mathbf{D}$ pro danou matici $ \mathbf{A}$ určena jednoznačně, až na permutaci diagonálních prvků.

Proof. [ ] Důkaz:I. Nechť $ \mathbf{A}$$ I$ různých vlastních čísel $ \lambda_1,\ldots,\lambda_I$. Z lemmatu 7.4 víme, že pro dané vlastní číslo $ \lambda_i$ tvoří vlastní vektory $ \mathbf{A}$ lineární prostor s dimenzí rovnou násobnosti tohoto vlastního čísla $ K_i$. Můžeme tedy vybrat $ K_i$ vlastních vektorů tvořících ortonormální bázi tohoto prostoru. Označme je $ \mathbf{v}_{i,0},\ldots,\mathbf{v}_{i,K_i-1}$. Učiňme tak pro všechna vlastní čísla. Celkem jsme tedy vybrali $ \sum_{i=1}^{I} K_i = N$ vlastních vektorů. Tyto vektory jsou navzájem ortonormální. Ortonormalitu v rámci $ i$-té skupiny (vlastních vektorů příslušných $ \lambda_i$) jsme zajistili vhodnou volbu a ornormalita pro různá $ i$ (pro různá vlastní čísla) plyne z lemmatu 7.3. Tvoří tedy bázi $ \mathcal{R}^N$ navíc ortonormální. Mohu z nich tedy sestavit ortogonální matici $ \mathbf{V}$ tak, že vybrané vlastní vektory tvoří sloupce $ \mathbf{V}$

$\displaystyle \mathbf{V} = [ \mathbf{v}_{1,0},\mathbf{v}_{1,1}\ldots,\mathbf{v}_{1,K_1-1},\ldots, \mathbf{v}_{I,K_I-1} ].$ (7.37)

Utvořme součin $ \mathbf{A}\mathbf{V}$ a použijme (7.24)

$\displaystyle \mathbf{A}\mathbf{V} = [ \lambda_1\mathbf{v}_{1,0},\lambda_1\math...
...,1}\ldots,\lambda_1\mathbf{v}_{1,K_1-1},\ldots, \lambda_I\mathbf{v}_{I,K_I-1} ]$ (7.38)

Jedná se vlastně o matici $ \mathbf{V}$ s přenásobenými sloupci, to lze jednodušeji zapsat přenásobením diagonální maticí zprava

$\displaystyle \mathbf{A}\mathbf{V} = \mathbf{V}\mathbf{D},$ (7.39)

kde

$\displaystyle \mathbf{D} = \mathrm{diag}([ \lambda_1,\lambda_1,\ldots,\lambda_1\ldots,\lambda_I ]).$ (7.40)

Vynásobením (7.38) $ \mathbf{V}^{-1}$ zprava (z (7.23) lze zapsat i jako $ \mathbf{V}^T$ neboť $ \mathbf{V}$ je ortogonální) dostáváme rozklad (7.36) matice $ \mathbf{A}$ požadovaných vlastností.

II. Mějme libovolnou dvojcí matic $ \mathbf{V}$, $ \mathbf{D}$, kde $ \mathbf{V}$ je ortogonální a $ \mathbf{D}$ diagonální, splnující (7.36). Vynásobením (7.36) $ \mathbf{V}$ zprava získáme

$\displaystyle \mathbf{A}\mathbf{V} = \mathbf{V}\mathbf{D} .$ (7.41)

Označme sloupce $ \mathbf{V}$, a diagonální prvky $ \mathbf{D}$

$\displaystyle \mathbf{V} = [\mathbf{v}_1,\ldots,\mathbf{v}_N], \\
\mathbf{D} = \mathrm{diag}([d_1,\ldots,d_N]),
$

kde $ N\times N$ je rozměr obou matic. Rozepišme rovnost (7.41) pro jednotlivé sloupce

$\displaystyle \mathbf{A}\mathbf{v}_k = \mathbf{v}_k d_k, \;\;\;\; k=1,\ldots,N .$ (7.42)

Protože $ \mathbf{v}_k \neq 0$, neboť $ \mathbf{V}$ je ortogonální, jsou podle (7.24) $ d_k$ vlastními čísly matice $ \mathbf{A}$ a $ \mathbf{v}_k$ příslušnými vlastními vektory. Nyní dokáži, že každé vlasní číslo $ \lambda_i$ matice $ \mathbf{A}$ je na diagonále $ \mathbf{D}$ obsaženo nevýše tolikrát, kolik činí jeho násobnost $ K_i$ (to, že počet výskytů $ \lambda_i$ na diagonále $ \mathbf{D}$ je právě $ K_i$ plyne pak jednonuše z toho, že diagonála $ \mathbf{D}$ obsahuje pouze vlastní čísla a počet prvků na diagonále je $ N$, což je počet všech vlastních čísel matice $ \mathbf{A}$ včetně násobnosti). Důkaz provedeme sporem. Předpokládejme tedy, že počet výskytů $ \lambda_i$ na diagonále $ \mathbf{D}$ je $ H$, kde $ H>K_i$. Z (7.42) tedy existuje $ H$ sloupců $ \mathbf{V}$ (označme je $ \mathbf{v}_{i,1},\ldots,\mathbf{v}_{i,H}$), pro které platí

$\displaystyle \mathbf{A}\mathbf{v}_{i,h} = \mathbf{v}_{i,h} \lambda_i, \;\;\;\; h=1,\ldots,H
.
$

Z (7.24) se jedná o vlastní vektory příslušné $ \lambda_i$ ( $ \Vert\mathbf{v}_{i,h}\Vert \neq 0$ z ortogonality $ \mathbf{V}$), navíc jsou (z ortogonality $ \mathbf{V}$) tyto vektory lineárně nezávislé. K $ \lambda_i$ tedy přísluší více než $ K_i$ lineárně nezávislých vlastních vektorů. To je ale spor s lemmatem 7.4. Počet výskytů $ \lambda_i$ na diagonále $ \mathbf{D}$ je tedy menší nebo roven $ K_i$. $ \qedsymbol$

7.5.1 Vlastní struktura korelačních matic a některých speciálních matic

Lemma 7.6   Matice je regulární právě tehdy, když má pouze nenulová vlastní čísla.

Proof. [ ] Důkaz:Místo uvedeného tvrzení dokáži ekvivalentní: Matice je singulární právě tehdy, když má nulové vlastní číslo. Matice $ \mathbf{A}$ má z definice (7.24) nulové vlasní číslo právě tehdy, když existuje netriviální řešení

$\displaystyle \mathbf{A}\mathbf{v} = \mathbf{o}.
$

Tedy existuje netriviální lineární kombinace sloupců $ \mathbf{A}$ jež je rovna nulovému vektoru (sloupce $ \mathbf{A}$ jsou lineárně závislé). Tedy $ \mathbf{A}$ je singulární. $ \qedsymbol$

Lemma 7.7   Matice $ p\mathbf{E}$ má jediné vlastní číslo $ p$ násobnosti $ N$, kde $ N\times N$ je rozměr matice.

Proof. [ ] Důkaz:Jednoduše utvořím některý z vlastních rozkladů $ p\mathbf{E}$. Například zvolím $ \mathbf{V} = \mathbf{E}$ a $ \mathbf{D} = p\mathbf{E}$. Snadno ověřím že se skutečně jedná o vlastní rozklad $ p\mathbf{E}$ ( $ \mathbf{V}\mathbf{D}\mathbf{V}^T = p\mathbf{E}$, $ \mathbf{V}^T\mathbf{V} = \mathbf{E}$ a $ \mathbf{D} = p\mathbf{E}$ je diagonální). Z lemmatu 7.5 musí být na diagonále $ \mathbf{D} = p\mathbf{E}$ pouze vlastní čísla $ p\mathbf{E}$, kde počet výskytů daného vlastního čísla je právě roven jeho násobnosti. Jelikož diagonála obsahuje pouze $ p$ právě $ N$-krát, je $ p$ jediným vlastním číslem $ p\mathbf{E}$ násobnosti $ N$ $ \qedsymbol$

Lemma 7.8   Nechť $ \mathbf{A}$ je symetrická reálná matice rozměru $ N\times N$. Kvadratická forma $ \mathbf{h}\mathbf{A}\mathbf{h}$ je nezáporná ( $ \mathbf{h}\mathbf{A}\mathbf{h}
\geq 0$ pro všechna $ \mathbf{h} \in \mathcal{R}^N$) právě tehdy, když $ \mathbf{A}$ má pouze nezáporná vlastní čísla.

Proof. [ ] Důkaz:Jelikož $ \mathbf{A}$ je reálná symetrická, existuje z lematu 7.5 rozklad $ \mathbf{A} = \mathbf{V}\mathbf{D}\mathbf{V}^T$, kde $ \mathbf{V}$ je ortogonální a $ \mathbf{D}$ diagonální. Navíc $ \mathbf{D} = \mathrm{diag}([\lambda_1,\ldots,\lambda_N])$ obsahuje na diagonále všechna vlastní čísla matice $ \mathbf{A}$ včetně násobností. Součin $ \mathbf{h}\mathbf{A}\mathbf{h}$ mohu nyní zapsat

\begin{equation*}\begin{aligned}\mathbf{h}^T\mathbf{A}\mathbf{h} &= \mathbf{h}^T...
...}\mathbf{u} = \\ &= \sum_{k=1}^{N} u_k^2 \lambda_k, \end{aligned}\end{equation*}

kde jsem označil $ \mathbf{u} = [u_1, \ldots u_N]^T= \mathbf{V}^T\mathbf{h}$. Z (7.43) plyne, že má-li $ \mathbf{A}$ pouze nezáporná vlastní čísla ($ \lambda_k$) nemůže být pravá strana záporná pro jakoukoliv volbu $ \mathbf{h} \in \mathcal{R}^N$, tedy i levá strana musí být nezáporná. Naopak, předpokládejme, že $ \mathbf{A}$ má i záporná vlastní čísla, nalezneme tedy $ l$ pro které je $ \lambda_l$ záporné. Sestrojíme takový vektor $ \mathbf{u}$, který má $ u_l = 1$ a ostatní složky nulové. Jelikož je $ \mathbf{V}$ ortogonální (a tedy rovněž regulární), jednoduše k $ \mathbf{u}$ nalezneme vzor $ \mathbf{h} = \mathbf{V}^{-T}\mathbf{u}$. Tedy existuje $ \mathbf{h} \in \mathcal{R}^N$ tak, že $ \mathbf{h}^T\mathbf{A}\mathbf{h} = \sum_{k=1}^{N} u_k^2 \lambda_k
= u_l^2 \lambda_l < 0
$ , což je spor. $ \qedsymbol$

Lemma 7.9   Nechť $ \mathbf{z}$ je reálný náhodný vektor. Korelační matice $ \mathbf{R} = \mathrm{E}[\mathbf{x}\mathbf{x}^T]$, $ \mathbf{x} = \mathbf{z} - \mathrm{E}[\mathbf{z}]$ má pouze nezáporná vlastní čísla.

Proof. [ ] Důkaz:Předně $ \mathbf{R} = \mathrm{E}[\mathbf{x}\mathbf{x}^T]$ je zřejmě reálná symetrická matice. Zvolme libovolný $ \mathbf{u} \in \mathcal{R}$. Pak, platí

$\displaystyle \mathbf{u}^T\mathbf{R}\mathbf{u} =
\mathrm{E}[\mathbf{u}^T\mathbf{x}\mathbf{x}^T\mathbf{u}] =
\mathrm{E}[y^2] \geq 0,
$

kde jsem zavedl náhodnou proměnou $ y = \mathbf{u}^T\mathbf{x}$. Kvadratická forma $ \mathbf{u}^T\mathbf{R}\mathbf{u}$ je tedy nezáporná, takže $ \mathbf{R}$ má podle lemmatu 7.8 pouze nezáporná vlastní čísla. $ \qedsymbol$

7.5.1.0.1 Horní mez na pro vastní čísla korelační matice - stopa matice

Nechť matice $ \mathbf{A}$ má rozměr $ N\times N$. Stopu matice $ \mathbf{A}$ značím $ \mathrm{tr}(\mathbf{A})$ a definuji jako součet jejích diagonálních prvků

$\displaystyle \mathrm{tr}(\mathbf{A}) = \sum_{k=1}^{N} a_{i,i},$ (7.44)

kde $ a_{i,j}$ značím prvky $ \mathbf{A}$.

Nechť $ \mathbf{A}$ má rozměr $ N\times M$ a $ \mathbf{B}$ má rozměr $ M\times N$. Označme $ \mathbf{C} = \mathbf{A}\mathbf{B}$, pak platí

$\displaystyle \mathrm{tr}(\mathbf{A}\mathbf{B}) = \mathrm{tr}(\mathbf{C}) = \su...
..._{m=1}^{M} \sum_{n=1}^{N} b_{m,n} a_{n,m} = \mathrm{tr}(\mathbf{B}\mathbf{A}) .$ (7.45)

Lemma 7.10   Nechť $ \lambda_i$ je vlastním číslem korelační matice $ \mathbf{R}$, pak $ \lambda_i \leq \mathrm{tr}(\mathbf{R})$

Proof. [ ] Důkaz:Jelikož korelační matice je reálná symetrická, existuje podle lemmatu 7.5 rozklad $ \mathbf{R} = \mathbf{V}\mathbf{D}\mathbf{V}^T$, kde $ \mathbf{V}$ je ortogonální a $ \mathbf{D} = [\lambda_1,\ldots,\lambda_N]$ je diagonální (diagonála matice $ \mathbf{D}$ obsahuje pouze vlastní čísla $ \mathbf{R}$ a to všechna včetně násobnosti). Dosaďme za $ \mathbf{R}$ do $ \mathrm{tr}(\mathbf{R})$ a použijme (7.45) a ortogonalitu $ \mathbf{V}$

$\displaystyle \mathrm{tr}(\mathbf{R}) = \mathrm{tr}(\mathbf{V}\mathbf{D}\mathbf...
...athbf{V}) = \mathrm{tr}(\mathbf{D}) = \sum_{k=1}^{N} \lambda_k \geq \lambda_i .$ (7.46)

V posledním kroku jsem použil lemma 7.9 (korelační matice má pouze nezáporná vlastní čísla). $ \qedsymbol$

Shrnu nyní závěry o vlastních číslech korelačnich matic plynoucí z lemmat 7.67.10. Nechť $ \mathbf{R}$ je libovolná korelační matice $ N\times N$ (autokorelační matice je speciální připad korelační matice) a nechť $ \lambda_1,\ldots,\lambda_I$ jsou její různá vlastní čísla. Uspořádejme je od nejmenšího k největšímu $ \lambda_{\mathrm{min}} \le \ldots \le \lambda_{\mathrm{max}}$. Z lemmatu 7.9 a lemmatu 7.10 plyne, omezení na jejich hodnoty

$\displaystyle 0 \leq \lambda_{\mathrm{min}} \leq \ldots \leq \lambda_{\mathrm{max}} \leq \mathrm{tr}(\mathbf{R}) .$ (7.47)

Je-li navíc $ \mathbf{R}$ regulární lze dolní mez s použitím lemmatu 7.6 trochu přiostřit

$\displaystyle 0 \le \lambda_{\mathrm{min}} .$ (7.48)

Jedná-li se o autokorelační matici stacionárního náhodného procesu $ x[n]$ lze horní mez zapsat jako $ N$ násobek jeho disperze $ r_{xx,0} = \mathrm{E}[(x[n] - \mathrm{E}(x[n]))^2]$ (pro nulovou střední hodnotu a ergodický proces můžeme odhadovat jako výkon)

$\displaystyle \lambda_{\mathrm{max}} \leq N r_{xx,0} .$ (7.49)

Autokorelační matice bílých stacionárních procesů mají tvar $ p\mathbf{E}$, a mají tedy z lemmatu 7.7 pouze jediné vlastní číslo násobnosti $ N$. Naopak barevné procesy se vyznačují ruznými vlastními čísly. Dokonce poměr $ \lambda_{max}/\lambda_{min}$ (eigenvalue spread) lze brát jako jakousi míru barevnosti procesu.


next up previous
Next: 7.6 Konvergence střední hodnoty Up: 7. Cvičení 7: Konvergenční Previous: 7.4 NLMS
Mirek 2006-12-12