Szinguláris érték felbontás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. január 5-én felülvizsgált verziótól ; az ellenőrzések 8 szerkesztést igényelnek .

A szinguláris érték dekompozíció egy téglalap alakú mátrix egy bizonyos típusú dekompozíciója , amelyet vizuális geometriai értelmezése miatt széles körben használnak számos alkalmazott probléma megoldásában. A szinguláris érték dekompozíció újrafogalmazása, az úgynevezett Schmidt-dekompozíció , alkalmazható a kvantuminformáció-elméletben , például az összefonódásban .

A mátrix szinguláris értékbontása lehetővé teszi egy adott mátrix szinguláris értékeinek, valamint a mátrix bal és jobb oldali szinguláris vektorainak kiszámítását : $M$ $M$

a mátrix bal oldali szinguláris vektorai a mátrix sajátvektorai ; $M$ $MM^{{*}}$
a mátrix jobb oldali szinguláris vektorai a mátrix sajátvektorai . $M$ $M^{{*}}M$

Hol van a hermitikus konjugált mátrix a mátrixhoz valós mátrix esetén . $M^{*}$ $M$ ${\displaystyle M^{*}=M^{T))$

A mátrix szinguláris értékeit nem szabad összetéveszteni ugyanazon mátrix sajátértékeivel .

A szinguláris érték dekompozíció hasznos a mátrix rangjának, a mátrix magjának és a mátrix pszeudoinverzének kiszámításához .

A szinguláris érték dekompozíciót a mátrixok adott rangú mátrixokkal való közelítésére is használják.

Definíció

Legyen a sorrendi mátrix a mező elemeiből , ahol vagy a valós számok mezője , vagy a komplex számok mezője . $M$ $m\szer n$ $K$ $K$

Szinguláris számok és szinguláris vektorok

Egy nem negatív valós számot mátrix szinguláris értéknek nevezünk , ha két egységnyi hosszúságú vektor van, és így: $\sigma$ $M$ $u\in K^{m}$ $v\in K^{n}$

Mv=\sigma u,

és

M^{*}u=\sigma v.

Az ilyen vektorokat rendre bal oldali szinguláris vektornak , illetve a szinguláris számnak megfelelő jobb oldali szinguláris vektornak nevezzük . $u$ $v$ $\sigma$

Mátrix dekompozíció

A rendelési mátrix szinguláris értékű dekompozíciója a következő forma bontása $M$ $m\szer n$

M=U\Sigma V^{*},

ahol egy méretű mátrix nemnegatív elemekkel, amelyben a főátlón fekvő elemek szinguláris számok (és a főátlón kívül eső összes elem nulla), és a (sorrendű ) és ( sorrendű ) mátrixok két unitárius mátrix, amelyek bal és jobb oldali szinguláris vektorokból állnak (a a konjugált-transzponált mátrix k ). $\Sigma$ $m\szer n$ $U$ $m$ $V$ $n$ $V^*$ $V$

Példa

Legyen adott a mátrix:

M={\begin{bmatrix}1&0&0&0&2\\0&0&3&0&0\\0&0&0&0&0\\0&4&0&0&0\end{bmátrix}}

Ennek a mátrixnak az egyik szinguláris értékű dekompozíciója a dekompozíció , ahol a mátrixok és a következők: $M=U\Sigma V^{*}$ $U$ $\Sigma$ $V^*$

U={\begin{bmatrix}0&0&1&0\\0&1&0&0\\0&0&0&-1\\1&0&0&0\end{bmátrix)),\quad \Sigma ={\begin{bmatrix}4&0&0&0&0\\0&3&0&0&0&0\\0&0&5 }}&0&0\\0&0&0&0&0\end{bmatrix}},\quad V^{*}={\begin{bmatrix}0&1&0&0&0\\0&0&1&0&0\\{\sqrt {0.2}}&0&0&0&{\sqrt\\\\0.8}} 0&0&0&1&0\\-{\sqrt {0.8}}&0&0&0&{\sqrt {0.2}}\end{bmatrix}},

mivel a és mátrixok egységesek ( és , ahol az azonosságmátrix ), és egy téglalap alakú átlós mátrix , vagyis ha . $U$ $V$ $UU^{*}=I$ $VV^{*}=I$ $én$ $\Sigma$ $\Sigma _{{ij}}=0$ $i \neq j$

Geometriai érzék

Legyen a mátrix egy lineáris operátorral társítva . A szinguláris érték dekompozíció geometriai értelemben újrafogalmazható. A térelemeket önmagába leképező lineáris operátor a forgatás és nyújtás egymás után végrehajtott lineáris operátoraiként ábrázolható. Ezért a szinguláris érték dekompozíció komponensei egyértelműen geometriai változásokat mutatnak, amikor egy lineáris operátor vektorhalmazt képez le egy vektortérből önmagába vagy egy másik dimenziójú vektortérbe [1] . $A$ $\mathbb {R} ^{n}$ $A$

Vizuálisabb megjelenítéshez vegyünk egy egységnyi sugarú gömböt a térben . A vonalleképezés ezt a gömböt térellipszoidra képezi le . Ekkor a mátrix átlójának nullától eltérő szinguláris értékei ennek az ellipszoidnak a féltengelyeinek hossza . Abban az esetben, ha minden szinguláris érték különbözik és különbözik nullától, a lineáris leképezés szinguláris érték dekompozíciója könnyen elemezhető három művelet eredményeként: vegyünk egy ellipszoidot és tengelyeit; majd vegye figyelembe az irányokat abban , hogy a leképezés ezekre a tengelyekre vonatkozik. Ezek az irányok merőlegesek. Először az izometriát alkalmazzuk úgy, hogy ezeket az irányokat koordinátatengelyekre leképezzük . A második lépés a koordinátatengelyek mentén átlósított endomorfizmus alkalmazása, és ezen irányok kiterjesztése/összehúzása, a féltengelyek hosszát használva nyújtási tényezőként. A szorzat ezután leképezi az egységgömböt egy izometrikus ellipszoidra . Az utolsó lépés meghatározásához egyszerűen alkalmazzon izometriát erre az ellipszoidra, és alakítsa át a következőre . Amint azt könnyen ellenőrizheti, a termék megegyezik a . $S$ $\mathbb {R} ^{n}$ $T$ $\mathbb{R} ^{m}$ $\Sigma$ $n=m$ $T$ $T(S)$ $\mathbb {R} ^{n}$ $T$ ${\mathbf {v))^{*}$ $\mathbb {R} ^{n}$ $\mathbf{d}$ $T(S)$ ${\mathbf {d}}\otimes {\mathbf {v}}^{*}$ $T(S)$ $u$ $T(S)$ ${\mathbf {u}}\otimes {\mathbf {d}}\otimes {\mathbf {v}}^{*}$ $T$

Alkalmazások

Pszeudo-inverz mátrix

A szinguláris érték dekompozíció segítségével pszeudoinverz mátrixokat találhatunk , amelyek különösen a legkisebb négyzetek módszerére vonatkoznak .

Ha , akkor a mátrix pszeudo-inverzét a következő képlettel találjuk meg: $M=U\Sigma V^{*}$

M^{+}=V\Sigma ^{-1}U^{*},

ahol a mátrix pszeudoinverze , amelyet abból kapunk, hogy minden átlós elemet inverzére cserélünk: és transzponáljuk. $\Sigma ^{{-1}}$ $\Sigma$ $\sigma$ ${\displaystyle {\sigma }^{-1))$

Közelítés alacsonyabb rangú mátrixszal

Egyes gyakorlati feladatokban egy adott mátrixot egy másik , előre meghatározott rangú mátrixszal kell közelíteni . Ismeretes a következő tétel, amelyet néha Eckart - Yang tételnek is neveznek. [2] $M$ $M_{k}$ $k$

Ha megköveteljük, hogy egy ilyen közelítés legyen a legjobb abban az értelemben, hogy a mátrixok különbségének euklideszi normája és minimális, a megszorítás mellett, akkor kiderül, hogy a legjobb ilyen mátrixot a szinguláris érték felbontásból kapjuk. mátrix a következő képlettel: $M$ $M_{k}$ ${\mbox{rank}}(M_{k})=k$ $M_{k}$ $M$

M_{k}=U\Sigma _{k}V^{*},

ahol az a mátrix , amelyben az összes átlós elemet nullák helyettesítik, kivéve a legnagyobb elemeket. $\Sigma _{k}$ $\Sigma$ $k$

Ha a mátrix elemei nem növekvő sorrendben vannak rendezve, akkor a mátrix kifejezése a következő formában írható át: $\Sigma$ $M_{k}$

M_{k}=U_{k}\Sigma _{k}V_{k}^{*},

ahol a , és mátrixokat a megfelelő mátrixokból kapjuk a mátrix szinguláris érték felosztásában , pontosan az első oszlopokra vágva. $U_k$ $\Sigma _{k}$ $V_{k}$ $M$ $k$

Látható tehát, hogy ha a mátrixot egy alacsonyabb rangú mátrixszal közelítjük, egyfajta tömörítést hajtunk végre a ben foglalt információkból : a méretmátrixot kisebb méretű mátrixok és egy átlós mátrix elemekkel helyettesítjük. Ebben az esetben a tömörítés veszteséggel történik - a mátrixnak csak a legjelentősebb része marad meg a közelítésben . $M$ $M$ $M$ $m\szer n$ $m \idő k$ $k \szer n$ $k$ $M$

Nagyrészt ennek a tulajdonságnak köszönhetően a szinguláris érték dekompozíció széles körű gyakorlati alkalmazást talál: adattömörítésben, jelfeldolgozásban, mátrixokkal végzett numerikus iteratív módszerekben, főkomponens -analízisben , látens szemantikai elemzésben és más területeken.

Rövidített változat

Egy sorrendű mátrix esetén , ha egy mátrixnál kisebb rangú mátrixszal kell közelíteni, gyakran használnak kompakt dekompozíciós ábrázolást [3] : $M$ $m\szer n$ $r$ $n$

M=U_{r}\Sigma _{r}V_{r}^{*}.

Csak az oszlopok és sorok számítanak ki . A többi oszlop és sor nem kerül kiszámításra. Ez sok memóriát takarít meg, ha . $r$ $U$ $r$ $V^*$ $U$ $V^*$ $r\ll n$

Mondjunk egy példát, mondjuk ez azoknak a felhasználóknak a száma, akik egy-egy filmre adott értékelést, amelyek teljes számát jelöli majd a mátrix (nagyon ritka, mivel minden felhasználó csak a filmek egy kis részét) jelölik és kellően nagy méretűek . $m$ $n$ $M$ $[m\times n]$

Ha kisebb méretű mátrixszal akarunk dolgozni, akkor ki kell számítanunk a szinguláris érték dekompozíciót:

$M=U\Sigma V^{*}$ ebben az esetben a mátrix , mint korábban említettük, átlós. Ezek után, ha csak információt akarunk menteni , akkor vegyük úgy , hogy az első elemek négyzeteinek összege az átlós elemek összes négyzetének összegéből legyen . $\Sigma$ $90\%$ $r$ $\Sigma$ $90\%$ $\Sigma$

Így megkapjuk a dimenziót ( az oszlopokat véve), a méretet és a c -t . Ekkor mátrix helyett egy alacsonyabb dimenziójú mátrixot is manipulálhatunk , amelyet gyakran a filmkategóriák szerinti felhasználói értékelések mátrixaként értelmeznek. $U$ $[m\times r]$ $r$ $\Sigma$ $[r\times r]$ $V^*$ $[r\times n]$ $M$ $M'=U\Sigma$ $[m\times r]$

Szoftver implementációk

A szinguláris érték dekompozíció megtalálására szolgáló numerikus algoritmusok számos matematikai csomagba vannak beépítve. Például MATLAB és GNU Octave rendszerekben a paranccsal található meg

[ U , S , V ] = svd ( M );

Az SVD számos matematikai könyvtár alapvető módszereinek listáján szerepel, beleértve a szabadon terjesztetteket is.
Például vannak megvalósítások

A GNU Scientific könyvtárból (GSL):

https://www.gnu.org/software/gsl/manual/html_node/Singular-Value-Decomposition.html

A CERN-ben kifejlesztett és a tudományos közösségben széles körben használt ROOT keretrendszerben:

https://root.cern.ch/root/htmldoc/guides/users-guide/LinearAlgebra.html#svd

Az Intel® Math Kernel Library-ben (Intel® MKL).

https://software.intel.com/en-us/intel-mkl

A Python lineáris algebrájának numpy könyvtárában :

https://numpy.org/doc/stable/reference/generated/numpy.linalg.svd.html

A tensorflow gépi tanulási könyvtárban:

https://www.tensorflow.org/api_docs/python/tf/linalg/svd

És néhány másik

https://tedlab.mit.edu/~dr/SVDLIBC/
http://www.alglib.net/matrixops/general/svd.php

Lásd még

Jegyzetek

↑ Szinguláris érték dekompozíció a Felismerés wikin . Letöltve: 2009. november 8. Az eredetiből archiválva : 2012. május 26.. (határozatlan)
↑ Eckart, C. és Young, G. Egy mátrix közelítése egy alacsonyabb rangú mátrixhoz. Psychometrica, 1936, 1, 211-218.
↑ Peter Harrington. Gépi tanulás működés közben . - Menedéksziget, 2012. - S. 280 . — ISBN 9781617290183 .

Irodalom

William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. 2.6 Egyedi érték felbontása // Numerikus receptek C. - 2. kiadás. — Cambridge: Cambridge University Press. - ISBN 0-521-43108-5 .

Linkek

Cikkek

Cikk a szinguláris értékek lebontásáról a machinelearning.ru oldalon
Cikk a MathWorldről és egy példa a képtömörítésre. (Angol)

Előadások on-line

Előadás a szinguláris értékbontásról a főkomponens -analízis kontextusában , Heidelbergi Egyetem, prof. Fred Hamprecht

Vektorok és mátrixok

Vektorok

Alapfogalmak	Vektor a geometriában Alap Ortogonális alap Vektor koordináták Kollinearitás Ortogonalitás Lineáris függőség Oszlopköz
A vektorok fajtái	Egységvektor Axiális vektor izotróp vektor Normál Kollinearitás Nulla vektor Sugár vektor Sajátvektor
Műveletek vektorokon	Skaláris szorzat vektor termék vegyes termék Pszeudoszkaláris termék Dupla kereszttermék
Tértípusok	vektor tér affin tér Euklideszi tér Pszeudoeuklideszi tér Normált tér Minkowski tér

mátrixok

Alapfogalmak	Mátrixszorzás Transzponált mátrix Hermitikus konjugált mátrix Szimmetrikus mátrix inverz mátrix Sajátérték Mátrix karakterisztikus polinomja
Speciális mátrixok	Identitásmátrix Nulla mátrix Átlós mátrix lambda mátrix
Mátrix dekompozíciók	LU bomlás Cholesky-bomlás QR-bontás LUP bomlás szinguláris érték felbontás Mátrix spektrális lebontása

Egyéb