Singulaariarvon hajottelu

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 5. tammikuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 8 muokkausta .

Yksittäisen arvon hajottelu on suorakaiteen muotoisen matriisin tietynlainen hajotus , jota käytetään laajasti sen visuaalisen geometrisen tulkinnan vuoksi monien sovellettujen ongelmien ratkaisemisessa. Singulaarisen arvon hajottelun uudelleenmuotoilulla, niin kutsutulla Schmidt-hajotelmalla , on sovelluksia kvanttiinformaatioteoriassa , kuten sotkeutumisessa .

Matriisin singulaariarvojen hajottelu mahdollistaa tietyn matriisin singulaariarvojen sekä matriisin vasemman ja oikean singulaarisen vektorin laskemisen : $M$ $M$

matriisin vasemmanpuoleiset singulaarivektorit ovat matriisin ominaisvektorit ; $M$ $MM^{{*}}$
matriisin oikeat singulaarivektorit ovat matriisin ominaisvektorit . $M$ $M^{{*}}M$

Missä on hermiittinen konjugaattimatriisi matriisiin , todelliselle matriisille . $M^{*}$ $M$ ${\displaystyle M^{*}=M^{T))$

Matriisin singulaariarvoja ei pidä sekoittaa saman matriisin ominaisarvoihin .

Yksittäisen arvon hajottelu on hyödyllinen matriisin arvon, matriisin ytimen ja matriisin pseudoinverssin laskennassa .

Singulaaristen arvojen hajottelua käytetään myös matriisien likiarvoon tietyn järjestyksen matriiseilla.

Määritelmä

Olkoon järjestysmatriisi elementtejä kentästä , jossa on joko reaalilukukenttä tai kompleksilukukenttä . $M$ $m\ kertaa n$ $K$ $K$

Yksikköluvut ja yksikkövektorit

Ei-negatiivista reaalilukua kutsutaan matriisin singulaariseksi arvoksi , kun on kaksi yksikköpituista vektoria ja sellainen, että: $\sigma$ $M$ $u\in K^{m}$ $v\in K^{n}$

Mv=\sigma u,

M^{*}u=\sigma v.

Tällaisia vektoreita kutsutaan vastaavasti vasen yksikkövektoriksi ja yksikkölukua vastaava oikea yksikkövektori . $u$ $v$ $\sigma$

Matriisihajotus

Järjestysmatriisin yksikköarvohajotelma on seuraavan muodon hajotelma $M$ $m\ kertaa n$

M=U\Sigma V^{*},

jossa on ei-negatiivisia elementtejä sisältävä matriisi, jossa päälävistäjällä sijaitsevat alkiot ovat yksikkölukuja (ja kaikki alkiot, jotka eivät ole päälävistäjällä, ovat nollia), ja matriisit (järjestyksen ) ja (järjestyksen ) ovat kaksi unitaarimatriisia , jotka koostuvat vasemmasta ja oikeasta singulaarivektoreista (a on konjugaattitransponoitu matriisi k ). $\Sigma$ $m\ kertaa n$ $U$ $m$ $V$ $n$ $V^*$ $V$

Esimerkki

Olkoon matriisi annettu:

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

Yksi tämän matriisin yksittäisarvojaotteluista on dekompositio , jossa matriisit ja ovat seuraavat: $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{bmatrix)),\quad \Sigma ={\begin{bmatrix}4&0&0&0&0\\0&3&0&0&0&0\sq&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}},

koska matriisit ja ovat unitaarisia ( ja , missä on identiteettimatriisi ), ja on suorakaiteen muotoinen diagonaalinen matriisi , eli jos . $U$ $V$ $UU^{*}=I$ $VV^{*}=I$ $minä$ $\Sigma$ $\Sigma _{{ij}}=0$ $i \neq j$

Geometrinen tunne

Olkoon matriisi liitetty lineaariseen operaattoriin . Yksittäisen arvon hajottelu voidaan muotoilla uudelleen geometrisesti. Lineaarinen operaattori, joka kartoittaa avaruuselementtejä itseensä, voidaan esittää peräkkäin suoritettavina kierto- ja venytysoperaattoreina. Siksi singulaariarvojaottelun komponentit osoittavat selvästi geometrisia muutoksia, kun lineaarinen operaattori kuvaa joukon vektoreita vektoriavaruudesta itseensä tai toisen ulottuvuuden vektoriavaruuteen [1] . $A$ $\mathbb {R} ^{n}$ $A$

Visuaalisempaa esitystä varten harkitse yksikkösäteen palloa avaruudessa . Viivakartoitus kartoittaa tämän pallon avaruusellipsoidiksi . Tällöin matriisin diagonaalin nollasta poikkeavat singulaariarvot ovat tämän ellipsoidin puoliakselien pituuksia . Siinä tapauksessa, että kaikki singulaariarvot ovat erilaisia ja poikkeavat nollasta, lineaarisen kartoituksen singulaarinen hajoaminen voidaan helposti analysoida kolmen toimenpiteen seurauksena: tarkastellaan ellipsoidia ja sen akseleita; harkitse sitten suuntia, joissa kartoitus kartoittaa näille akseleille. Nämä suunnat ovat ortogonaalisia. Ensin käytämme isometriaa kartoittamalla nämä suunnat koordinaattiakseleiksi . Toinen vaihe on soveltaa koordinaattiakseleita pitkin diagonalisoitua endomorfismia ja laajentaa/supistaa näitä suuntia käyttämällä venytystekijöinä puoliakselien pituuksia. Sitten tuote kartoittaa yksikköpallon isometriseen ellipsoidiin . Määrittääksesi viimeisen vaiheen , käytä isometriaa tähän ellipsoidiin, jotta se muunnetaan muotoon . Kuten voit helposti tarkistaa, tuote on sama kuin . $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$

Sovellukset

Pseudo-inverse matriisi

Singulaaristen arvojen hajottelulla voidaan löytää pseudoinversomatriiseja , jotka pätevät erityisesti pienimmän neliösumman menetelmään .

Jos , niin matriisi pseudo-inversio löytyy kaavasta: $M=U\Sigma V^{*}$

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

missä on pseudoinversio matriisiin , joka saadaan siitä korvaamalla jokainen diagonaalinen elementti sen käänteisellä: ja transponoimalla. $\Sigma ^{{-1}}$ $\Sigma$ $\sigma$ ${\displaystyle {\sigma }^{-1))$

Approksimaatio alemman tason matriisilla

Joissakin käytännön ongelmissa tietty matriisi on lähennettävä jollakin toisella matriisilla , jolla on ennalta määrätty arvo . Tunnetaan seuraava lause, jota joskus kutsutaan Eckart -Yang -lauseeksi. [2] $M$ $M_{k}$ $k$

Jos vaadimme, että tällainen approksimaatio on paras siinä mielessä, että matriisien eron euklidinen normi on minimaalinen rajoitteen alaisena , niin käy ilmi, että paras tällainen matriisi saadaan matriisien singulaariarvohajotelmasta. matriisi kaavalla: $M$ $M_{k}$ ${\mbox{rank}}(M_{k})=k$ $M_{k}$ $M$

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

missä on matriisi , jossa kaikki diagonaaliset alkiot on korvattu nolilla, paitsi suurimmat alkiot. $\Sigma _{k}$ $\Sigma$ $k$

Jos matriisin elementit on järjestetty ei-nousevaan järjestykseen, matriisin lauseke voidaan kirjoittaa uudelleen seuraavaan muotoon: $\Sigma$ $M_{k}$

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

jossa matriisit , ja saadaan vastaavista matriiseista matriisin singulaariarvojaottelussa leikkaamalla täsmälleen ensimmäisiin sarakkeisiin. $U_k$ $\Sigma _{k}$ $V_{k}$ $M$ $k$

Siten voidaan nähdä, että approksimoimalla matriisia alemman tason matriisilla, suoritamme eräänlaisen informaation pakkaamisen : kokomatriisi korvataan pienempikokoisilla matriiseilla ja diagonaalimatriisilla elementeillä . Tässä tapauksessa pakkaus tapahtuu häviöillä - vain merkittävin osa matriisista säilyy approksimaatiossa . $M$ $M$ $M$ $m\ kertaa n$ $m \ aika k$ $k \ kertaa n$ $k$ $M$

Suurelta osin tämän ominaisuuden ansiosta singulaariarvojen hajottelu löytää laajan käytännön sovelluksen: tiedon pakkaamisessa, signaalinkäsittelyssä, numeerisissa iteratiivisissa menetelmissä matriisien kanssa työskennellä, pääkomponenttianalyysissä , piilevässä semanttisessa analyysissä ja muilla aloilla.

Lyhennetty versio

Järjestyksen matriisille , jos on tarpeen approksimoida matriisilla, jonka arvo on pienempi kuin , käytetään usein kompaktia hajotteluesitystä [3] : $M$ $m\ kertaa n$ $r$ $n$

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

Vain sarakkeet ja rivit lasketaan . Muita sarakkeita ja rivejä ei lasketa. Tämä säästää paljon muistia, kun . $r$ $U$ $r$ $V^*$ $U$ $V^*$ $r\ll n$

Otetaan esimerkki, oletetaan , että tämä on käyttäjien määrä, jotka kukin laittoivat osan arvioista elokuville, joiden kokonaismäärä merkitään , sitten matriisi (erittäin harva, koska jokainen käyttäjä arvioi vain pieni osa elokuvista) merkitään ja niillä on riittävän suuri koko . $m$ $n$ $M$ $[m\times n]$

Jos haluamme työskennellä pienempien mittojen matriisin kanssa, meidän on laskettava singulaariarvon hajoaminen:

$M=U\Sigma V^{*}$ tässä tapauksessa matriisi , kuten aiemmin mainittiin, on diagonaalinen. Tämän jälkeen, jos haluamme tallentaa vain tietoja, meidän on otettava , jotta ensimmäisten elementtien neliöiden summa on lävistäjäelementtien kaikkien neliöiden kokonaissummasta . $\Sigma$ $90\%$ $r$ $\Sigma$ $90\%$ $\Sigma$

Joten saamme dimension ( pylväät huomioon ottaen), ulottuvuuden ja c . Sitten matriisin sijasta voimme käsitellä alemman ulottuvuuden matriisia , joka tulkitaan usein käyttäjien arvioiden matriisiksi elokuvaluokittain. $U$ $[m\times r]$ $r$ $\Sigma$ $[r\times r]$ $V^*$ $[r\times n]$ $M$ $M'=U\Sigma$ $[m\times r]$

Ohjelmistototeutukset

Numeeriset algoritmit yksittäisen arvon hajoamisen löytämiseksi on rakennettu moniin matemaattisiin pakkauksiin. Esimerkiksi MATLAB- ja GNU Octave -järjestelmissä se löytyy komennolla

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

SVD sisältyy monien matemaattisten kirjastojen perusmenetelmien luetteloon, mukaan lukien vapaasti levitettävät kirjastot.
On esimerkiksi toteutuksia

GNU Scientific -kirjastosta (GSL):

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

CERNissä kehitetyssä ROOT-kehyksessä, jota käytetään laajalti tiedeyhteisössä:

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

Intel® Math Kernel Libraryssa (Intel® MKL).

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

Pythonin lineaarialgebran numpy- kirjastossa :

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

Tensorflow-koneoppimiskirjastossa:

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

Ja jotkut muut

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

Katso myös

Muistiinpanot

↑ Yksittäisen arvon hajottelu tunnistuswikissä . Haettu 8. marraskuuta 2009. Arkistoitu alkuperäisestä 26. toukokuuta 2012. (määrätön)
↑ Eckart, C. ja Young, G. Yhden matriisin approksimaatio toisella, jolla on matalampi arvo. Psychometrica, 1936, 1, 211-218.
↑ Peter Harrington. Koneoppiminen toiminnassa . - Shelter Island, 2012. - S. 280 . — ISBN 9781617290183 .

Kirjallisuus

William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. 2.6 Singular Value Decomposition // Numeeriset reseptit C. - 2. painos. — Cambridge: Cambridge University Press. - ISBN 0-521-43108-5 .

Linkit

Artikkelit

Artikkeli yksittäisarvojen hajottelusta osoitteessa machinelearning.ru
Artikkeli MathWorldistä ja esimerkki kuvien pakkaamisesta. (Englanti)

Luennot verkossa

Luento singulaariarvojen hajottelusta pääkomponenttianalyysin yhteydessä , Heidelbergin yliopisto, prof. Fred Hamprecht

Vektorit ja matriisit

Vektorit

Peruskonseptit	Vektori geometriassa Perusta Ortogonaalinen perusta Vektorikoordinaatit Kollineaarisuus Ortogonaalisuus Lineaarinen riippuvuus Saraketila
Vektorityypit	Yksikkövektori Aksiaalinen vektori isotrooppinen vektori Normaali Kollineaarisuus Nolla vektori Sädevektori Omavektori
Operaatiot vektoreille	Skalaarituote vektorituote sekoitettu tuote Pseudoskalaarinen tuote Kaksinkertainen ristituote
Tilatyypit	vektoriavaruus affinista tilaa Euklidinen avaruus Pseudoeuklidinen avaruus Normaali tila Minkowskin tila

matriiseja

Peruskonseptit	Matriisin kertolasku Transponoitu matriisi Hermitian konjugaattimatriisi Symmetrinen matriisi käänteinen matriisi Ominaisarvo Matriisin karakteristinen polynomi
Erikoismatriisit	Identiteettimatriisi Nolla matriisi Diagonaalinen matriisi lambda matriisi
Matriisihajotukset	LU:n hajoaminen Cholesky-hajoaminen QR-hajotus LUP-hajoaminen singulaariarvon hajottelu Matriisin spektrihajotus

Muut