SVD

Vlastní čísla

Vlastním číslem matice $A \in \mathbb{R}^{n,n}$ je každé číslo $\lambda \in C$ takovy ze: $Ax=\lambda x$ . Vektoru $x$ říkáme vlastní vektor příslušný vlastnímu číslu $\lambda$ Víme ze: $$Ax = λIx ⇐⇒ (A − λI)x = θ ⇐⇒ A − λI\ \text{je singulární}$$

Víme, že matice je singulární, právě když je její determinant nulový: $$A − λI\ \text{je singulární} ⇐⇒ det(A − λI) = 0.$$ Zavzpomínáme-li na to, co je to determinant, dojdeme k následujícímu poznatku: výraz $$p_A(λ) = det(A − λI)$$ Z toho, co jsme si řekli, plyne důležitá vlastnost tohoto polynomu Množina vlastních čísel matice je shodná s množinou kořenů jejího charakteristického polynomu.: $$λ ∈ C \text{ je vlastní číslo } A ⇐⇒ p_A(λ) = 0$$

Algebraická násobnost a geometrická násobnost rozhoduji o tom, zda existuje rozklad matice ve tvaru: $A=PDP^{-1}$ kde $P$ je regulární matice a $D$ matice diagonální (tj. všude mimo diagonálu nulová). Neboli $A$ a $D$ jsou podobne matice

Věta 2.4: Podobné matice mají stejná vlastní čísla

Věta 2.5 (diagonalizovatelnost matic): Buď $A \in R^{n,n}$ matice a $λ1, . . . , λk$ všechna její navzájem různá vlastní čísla. Označme dále $i_1, . . . , i_k$ algebraické násobnosti těchto vlastních čísel a $j_1, . . . , j_k$ jejich geometrické násobnosti. Potom platí: (i) Geometrická násobnost není větší než algebraická. (ii) Matice A je diagonalizovatelná právě tehdy, když pro všechna $l= 1, . . . , k$ platí $j = i$.

Symetrické matice

Matice $A ∈ R^{n,n}$ je symetrická, jestliže je rovna svojí inverzi, tedy $A^T = A$. Je jasné, že matice $X^TX$ je symetrická pro libovolnou matici $X$. O takové matici víme i další věci, které shrneme v následující větě.

Věta 2.6: Pro každou matici $X \in \mathbb{R}^{m,n}$ platí:

1. Matice $X^TX \in \mathbb{R}^{n,n}$ a $XX^T \in \mathbb{R}^{m,m}$ jsou symetrické.
2. Matice $X^TX \in \mathbb{R}^{n,n}$ a $XX^T \in \mathbb{R}^{m,m}$ mají stejnou hodnost jako matice $X$.
3. Matice $X^TX \in \mathbb{R}^{n,n}$ a $XX^T \in \mathbb{R}^{m,m}$ jsou pozitivně semidefinitní.
4. Matice $X^TX \in \mathbb{R}^{n,n}$ je pozitivně definitní, právě když $h(X) = n$.
5. Matice $XX^T \in \mathbb{R}^{m,m}$ je pozitivně definitní, právě když $h(X) = m$.

Věta 2.7: (symetrické matice): Buď $S \in \mathbb{R}^{n,n}$ symetrická matice. Potom platí následující:

1. Matice $S$ je diagonalizovatelná a navíc lze vlastní vektory volit tak, že tvoří ortonormální bázi. Jinými slovy: existuje ortogonální matice $Q$ a diagonální matice $D$ tak, že

$$S = QDQ^T$$

1. Všechna vlastní čísla matice $S$ jsou reálná.
2. Je-li matice $S$ pozitivně semidefinitní, jsou vlastní čísla nezáporná.
3. Je-li matice $S$ pozitivně definitní, jsou vlastní čísla kladná.

SVD rozklad matice a jeho vlastnosti

SVD - Dulezite predpoklady

Mějme matici $A \in \mathbb{R}^{m,n}$. Hlavní finta spočívá v tom, že se nebudeme snažit hledat vlastní čísla $A$, ale zaměříme se na matici $A^TA$. Tato matice $A^TA$ má několik klíčových vlastností:

1. Tato matice je čtvercová o rozměru $n \times n$.

2. Je čtvercová, pozitivně semidefinitní a symetrická.

3. Jelikož je symetrická, je diagonalizovatelná, má reálná (a nezáporná) vlastní čísla a z vlastních vektorů lze vytvořit ortonormální bázi prostoru $\mathbb{R}^n$.

4. Matice $A^TA$ a $A$ mají stejnou hodnost $r$, která je menší nebo rovna $\min\{m, n\}$.

5. Matice $A^TA$ má $n$ vlastních čísel, z toho $r$ kladných a pokud $r < n$, tak má vlastní číslo 0 s násobností $n - r$.

6. Kladná vlastní čísla matice $A^TA$ jsou označena $\sigma^2_i$ a jsou uspořádána sestupně, tedy: $\sigma^2_1 \geq \sigma^2_2 \geq \ldots \geq \sigma^2_r > 0$. Tyto vlastní hodnoty budou užitečné, protože později budeme pracovat s jejich odmocninami, $\sigma_i$.

7. Ke každému vlastnímu číslu existuje tolik ortonormálních vlastních vektorů, kolik je násobnost daného vlastního čísla. Tedy máme ortonormální soubor $(v_1, v_2, . . . , v_r)$, pro který platí $A^TAv_i = \sigma^2_i v_i$ pro všechna $i = 1, 2, . . . , r$.

8. Pokud $r < n$, pak můžeme doplnit tento soubor o $n - r$ vlastních vektorů příslušejících k vlastnímu číslu $0$ a tak vytvořit ortonormální bázi prostoru $\mathbb{R}^n$.

SVD

Buď matice $A \in \mathbb{R}^{m \times n}$ s hodností $r$. Potom existují ortogonální matice $V \in \mathbb{R}^{n \times n}$ a $U \in \mathbb{R}^{m \times m}$ a diagonální matice $\Sigma \in \mathbb{R}^{m \times n}$, která má na diagonále kladná čísla serazena: $\sigma_1 \geq \sigma_2 \geq \ldots \geq \sigma_r > 0$ a doplněná příslušným počtem nul, takové, že

$$A = U \Sigma V^T$$ Tomuto rozkladu říkáme SVD rozklad a číslům $σ_i$ pak singulární hodnoty matice $A$. Navíc víme, že singulární hodnoty $σ_i$ jsou odmocniny vlastních čísel matic $A^TA$ a $AA^T$ a sloupce matic $V$ a $U$ jsou tvořeny příslušnými vlastními vektory tvořícími ortonormální bázi.

Zakladni vlastnosti - SVD

Pro každé $i = 1, 2, \ldots, r$ definujeme vektor $u_i \in \mathbb{R}^m$ takto:

$$u_i = \frac{1}{\sigma_i} A v_i$$

Získáme tak soubor vektorů $(u_1, \ldots, u_r)$ z $\mathbb{R}^m$.

Ortonormalita

Soubor vektorů $(u_1, \ldots, u_r)$ je ortonormální. To je dáno výrazem:

$$u_i^T u_j = \left(\frac{1}{\sigma_i} A v_i\right)^T \frac{1}{\sigma_j} A v_j = \frac{1}{\sigma_i\sigma_j} v_i^T (A^T A v_j) = \frac{1}{\sigma_i\sigma_j} v_i^T (\sigma_j^2 v_j) = \frac{\sigma_j^2}{\sigma_i\sigma_j} v_i^T v_j = \begin{cases} 0 & \text{pro } i \neq j,\\ 1 & \text{pro } i = j. \end{cases}$$

Vlastní vektory a vlastní čísla

Každý vektor $u_i$ je vlastním vektorem matice $A A^T \in \mathbb{R}^{m \times m}$, která je čtvercová, symetrická a pozitivně semidefinitní. Tento vektor přísluší kladnému vlastnímu číslu $\sigma_i^2$ matice. To lze ukázat následující rovností:

$$A A^T u_i = A A^T \left(\frac{1}{\sigma_i} A v_i\right) = \frac{1}{\sigma_i} A (A^T A v_i) = \frac{1}{\sigma_i} A \left(\sigma_i^2 v_i\right) = \sigma_i^2(\frac{1}{\sigma_i}Av_i) = \sigma_i^2 u_i$$

SVD Rozklad Matice

Matice $A^T A$ a $A A^T$ mají shodná kladná vlastní čísla $\sigma_1^2 \geq \ldots \geq \sigma_r^2$ a soubor vektorů $(u_1, \ldots, u_r)$ je jejich ortonormální vlastní vektor.

Vytvoření matic $V$ a $U$

Z vektorových souborů $(v_1, v_2, \ldots, v_n)$ a $(u_1, u_2, \ldots, u_m)$ vytvoříme matice $V$ a $U$. Tyto soubory jsou sloupce obou matic, které jsou proto ortogonální, tedy $V^T V = I_n$ a $U^T U = I_m$.

Definice matice $\Sigma$

Matici $\Sigma$ definujeme jako diagonální matici s vlastními čísly $\sigma_1, \sigma_2, \ldots, \sigma_r$. Pokud $r < \min\{m, n\}$, diagonálu doplňujeme nulami.

Maticová rovnost

Výsledkem je maticová rovnost $A V = U \Sigma$.

SVD rozklad a aproximace matice maticí s nižší hodností

Aproximace maticí nízké hodnosti je efektivní technika pro kompresi dat. Tento koncept je založený na fundamentálním principu lineární algebry, kde součin dvou matic o rozměrech $m \times d$ a $d \times n$ produkuje matici velikosti $m \times n$.

Předpokládejme, že máme matici $A \in \mathbb{R}^{m,n}$. Cílem je najít takové matice $B \in \mathbb{R}^{m,d}$ a $C \in \mathbb{R}^{d,n}$, že platí $A = BC$. Tímto způsobem dosáhneme komprese dat.

Hodnost součinu matic nemůže být vyšší, než hodnost jednotlivých matic, tedy $h(BC) \leq \min\{h(B), h(C)\}$. Potom nejmenší možné $d$, pro které lze najít matice B a C takové, že $A = BC$, je rovno hodnosti matice A, tj. $d = r = h(A)$.

Z vlastností SVD ale snadno plyne, že pro $d = r$ lze matice $B$ a $C$ najít najitim rozkladem: $$A=U \Sigma V^T \ \ \text{ a }\ \ A=BC\ \ \ \Rightarrow\ \ \ B = U_r\ \ \text{ a }\ \ C = Σ_rV^T_r$$

Optimální volba matic B a C

Máme-li pevně zadané $d$, pak hledáme takové matice $B \in \mathbb{R}^{m,d}$ a $C \in \mathbb{R}^{d,n}$, že součin $BC$ je co nejblíže matici $A \in \mathbb{R}^{m,n}$. K měření vzdálenosti matic použijeme Frobeniovu normu, která je definována pro matici $A \in \mathbb{R}^{m,n}$ se složkami $a_{ij}$ jako:

$$||A||_F = \sqrt{\sum_{i=1}^{m} \sum_{j=1}^{n} a_{ij}^2 }$$

Tato norma má zajímavou vlastnost, že je rovna odmocnině součtu kvadrátů singulárních hodnot matice A, tj.

$$||A||_F = \sqrt{\sum_{i=1}^{r} \sigma_i^2 }$$

kde $r = h(A)$ je hodnost matice.

Eckart–Young–Mirsky Theorem

Pokud je SVD rozklad matice A definován jako $U \Sigma V^T$, můžeme definovat matice $U_d$, $\Sigma_d$ a $V_d$, které vzniknou tak, že vezmeme prvních $d$ sloupců z $U$, $\Sigma$ a $V$.

Potom nejlepší aproximace matice $A$ s hodností nejvýše $d$ je dána maticí $$A_d = U_d \Sigma_d V_d^T$$ Takže $d$ největších singulárních hodnot a k nim příslušné sloupce matic $U$ a $V$ definují nejlepší aproximaci maticí o hodnosti $d$.

Kvalita této aproximace je určena zbylými $r - d$ singulárními hodnotami, protože platí:

$$||A - A_d||_F = \sqrt{\sum_{i=d+1}^{r} \sigma_i^2 }$$

SVD rozklad a pseudoinverze matice

Pseudoinverze matice je koncept, který rozšiřuje pojem inverze matice, který je definován pouze pro čtvercové a regulární matice. Pseudoinverzi lze definovat pro jakoukoliv obdélníkovou matici.

Definice Pseudoinverze

Pro matici $A \in \mathbb{R}^{m,n}$ definujeme Mooreovu-Penroseovu pseudoinverzi $A^{+} \in \mathbb{R}^{n,m}$, která splňuje následující tři podmínky:

1. $AA^{+}A = A$

2. $A^{+}AA^{+} = A^{+}$

3. Matice $AA^{+}$ a $A^{+}A$ jsou symetrické.

Výpočet Pseudoinverze

Pseudoinverze matice lze vypočítat pomocí SVD rozkladu matice. Označíme-li SVD rozklad matice $A$ jako $A = UΣV^T$, kde $Σ$ je diagonální matice se singulárními hodnotami $\sigma_i$, můžeme definovat pseudoinverzní matici $Σ^{+}$, která má na diagonále inverzní hodnoty k singulárním hodnotám, tj.

$$Σ^{+} = \begin{pmatrix} (\sigma_1)^{-1} & 0 & \cdots & 0 & \cdots & 0 \\ 0 & (\sigma_2)^{-1} & \cdots & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots& \vdots \\ 0 & 0 & \cdots & (\sigma_r)^{-1}& \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots& \vdots \\ 0 & 0 & \cdots & 0 & \cdots & 0 \end{pmatrix} \in \mathbb{R}^{n,m}$$ Platí totiž, že matice $Σ^{+}Σ ∈ R^{n,n} \ \text{ a }\ ΣΣ^+ ∈ R^{m,m}$ mají na diagonále $r$ jedniček a všude jinde jsou nulové. Z toho už snadno vyvodíme ze pseudoinverze matice je dána jako:

$$A^{+} = VΣ^{+}U^T$$

Jistě, můžeme to ověřit pro každou z podmínek pseudoinverze:

Ověření pro podmínku (1) potazmo i (2):

Dosadíme $A^{+} = VΣ^{+}U^T$ do $AA^{+}A = A$:

$$AA^{+}A = (UΣV^T)(VΣ^{+}U^T)(UΣV^T) = UΣΣ^{+}ΣV^T = UΣV^T = A$$

Kde jsme využili ortogonality matic $U$ a $V$ a také toho, že $\Sigma\Sigma^{+}\Sigma = \Sigma$.

Ověření pro podmínku (3):

V této podmínce potřebujeme ukázat, že matice $AA^{+}$ a $A^{+}A$ jsou symetrické. Začneme s maticí $AA^{+}$:

$$(AA^{+})^T = (UΣV^TVΣ^{+}U^T)^T = (UΣΣ^{+}U^T)^T = U(\Sigma\Sigma^{+})^TU^T = UΣ\Sigma^{+}U^T = UΣV^TVΣ^+U^T= AA^{+}$$

Zde jsme využili toho, že $\Sigma\Sigma^{+}$ je symetrická a ortogonality matic $U$ a $V$.

Podobný postup lze použít pro ověření, že matice $A^{+}A$ je také symetrická.

Tedy, matice $A^{+} = VΣ^{+}U^T$ splňuje všechny podmínky pro pseudoinverzi matice $A$.