SVD: každé zobrazení je otočení, natažení a otočení
Kapitola 9 řekla, že symetrická matice je ve správně natočené soustavě čisté natažení. Napadne otázka, co se dá říct o té zbylé, mnohem větší skupině — nesymetrických, nečtvercových, singulárních. Odpověď je překvapivě silná: totéž, jen se otáčí dvakrát.
- jednotkový kruh → A → elipsa
Pusťme na jednotkový kruh libovolnou matici. Ať je jakkoli ošklivá, výsledkem je vždycky elipsa — nikdy nic jiného. To samo o sobě je věta, která se dá vidět.
- Vᵀ — otoč kruh
Nejdřív se kruh otočí. Na kruhu se tím nic nezmění — je kulatý — ale značky na něm se posunou, a právě ony ukazují, které dva kolmé směry se za chvíli budou natahovat.
- Σ = diag(1,91, 0,79)
Pak se to natáhne podél os — každou osu zvlášť, žádné zkosení. Ta dvě čísla se jmenují singulární hodnoty a jsou to poloosy výsledné elipsy.
- U — otoč na místo
A nakonec se elipsa otočí do konečné polohy. Tři kroky a je hotovo.
- A = U · Σ · Vᵀ
Každá matice — čtvercová i ne, singulární i ne — se dá rozložit na otočení, natažení podél kolmých os, otočení. Nic jiného zobrazení dělat neumí. Tohle je nejsilnější věta v celé lineární algebře a je vidět na jednom obrázku.
- κ = σ₁/σ₂ = 2,42
Poměr největší a nejmenší singulární hodnoty je číslo podmíněnosti: jak moc je ta elipsa protáhlá. Kruh (κ = 1) je ideál; doutník znamená, že jeden směr skoro zanikl. Kolik jich je nenulových, to je hodnost. Tři nejdůležitější vlastnosti matice se čtou z jednoho obrázku.
Slovy: otoč, natáhni podél kolmých os, otoč. A nic jiného lineární zobrazení dělat neumí — žádné čtvrté chování neexistuje. Tohle je nejsilnější věta v celé lineární algebře a vejde se do jednoho obrázku.
Co se z toho čte
| veličina | ze singulárních hodnot | co to znamená v obrázku |
|---|---|---|
| hodnost | kolik jich je nenulových | kolik rozměrů elipsa opravdu má |
| ‖A‖₂ | σ_max | nejvíc, co se dá natáhnout |
| podmíněnost κ | σ_max / σ_min | jak je elipsa protáhlá |
| |det A| | součin všech σ | obsah elipsy / obsah kruhu |
| pseudoinverze | 1/σ pro nenulové | kapitola 12 |
Kruh (κ = 1) je ideál: zobrazení natahuje ve všech směrech stejně. Doutník znamená, že jeden směr skoro zanikl — matice je skoro singulární, a to i tehdy, když determinant vypadá nevinně.
Proč je to lepší než vlastní čísla
| vlastní čísla | singulární hodnoty | |
|---|---|---|
| existují pro | jen čtvercové | každou matici |
| můžou být komplexní | ano | ne, vždycky reálné ≥ 0 |
| vektory kolmé | jen u symetrických | vždycky |
| numericky | můžou být velmi citlivé | velmi stabilní |
Proto se v praktických výpočtech hodnost, podmíněnost i nejmenší čtverce počítají ze SVD a ne z determinantu nebo vlastních čísel.
Jak se to počítá tady — a co to stojí. SVD se v téhle labce počítá přes symetrický eigenproblém matice AᵀA. Je to krátké a pro učební matice úplně dostatečné, ale umocnění půlí počet platných číslic u nejmenších singulárních hodnot. Prakticky to znamená, že tenhle solver nerozliší podmíněnost nad ~10⁷ a nad tou hranicí hlásí ∞ místo velkého čísla, kterému nemá nikdo věřit. Je to napsané v komentáři solveru a chytily to jeho vlastní testy — viz kapitola 7. Skutečné knihovny používají Golubův–Kahanův algoritmus, který AᵀA nikdy nesestaví.
Kde se s tím potkáte
- Nejmenší čtverce a pseudoinverze — kapitola 12 a OptiLab.
- Inverzní kinematika tlumenými nejmenšími čtverci — u singularity se malé singulární hodnoty potlačí místo obrácení, jinak by rameno vystřelilo. Viz KineLab.
- Kalibrace kamery — homografie se hledá jako singulární vektor příslušející nejmenší singulární hodnotě. Viz VisionLab.
- Komprese a redukce dimenze — nechat jen největší singulární hodnoty je nejlepší možná aproximace nižší hodností (Eckartova–Youngova věta). PCA je SVD kovarianční matice.