Singulärvärdesfaktorisering

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 5 januari 2022; kontroller kräver 8 redigeringar .

Singular värdenedbrytning är en viss typ av nedbrytning av en rektangulär matris , som på grund av dess visuella geometriska tolkning används flitigt för att lösa många tillämpade problem. En omformulering av singulära värdenedbrytning, den så kallade Schmidt-nedbrytningen , har tillämpningar inom kvantinformationsteorin , såsom i entanglement .

Singularvärdesuppdelningen av en matris gör det möjligt att beräkna singularvärdena för en given matris, såväl som de vänstra och högra singularvektorerna i matrisen : $M$ $M$

de vänstra singularvektorerna för matrisen är matrisens egenvektorer ; $M$ $MM^{{*}}$
de högra singularvektorerna för matrisen är matrisens egenvektorer . $M$ $M^{{*}}M$

Var är den hermitiska konjugerade matrisen till matrisen , för en riktig matris . $M^{*}$ $M$ ${\displaystyle M^{*}=M^{T))$

De singulära värdena för en matris ska inte förväxlas med egenvärdena för samma matris.

Singular värdenedbrytning är användbar för att beräkna rangen av en matris , kärnan i en matris och pseudoinversen av en matris .

Singularvärdesuppdelning används också för att approximera matriser med matriser av en given rang.

Definition

Låt ordningsmatrisen bestå av element från fältet , där är antingen fältet av reella tal eller fältet av komplexa tal . $M$ $m\ gånger n$ $K$ $K$

Singulartal och singularvektorer

Ett icke-negativt reellt tal kallas ett matrissingularvärde när det finns två vektorer med enhetslängd och sådana att: $\sigma$ $M$ $u\in K^{m}$ $v\in K^{n}$

Mv=\sigma u,

och

M^{*}u=\sigma v.

Sådana vektorer kallas för den vänstra singularvektorn respektive den högra singularvektorn motsvarande singulartalet . $u$ $v$ $\sigma$

Matrisupplösning

Ordningsmatrisens singularvärdesuppdelning är nedbrytningen av följande form $M$ $m\ gånger n$

M=U\Sigma V^{*},

där är en storleksmatris med icke-negativa element, där elementen som ligger på huvuddiagonalen är singulartal (och alla element som inte ligger på huvuddiagonalen är noll), och matriserna (av ordning ) och (i ordning ) är två enhetliga matriser, bestående av vänster respektive höger singulära vektorer (a är den konjugattransponerade matrisen k ). $\Sigma$ $m\ gånger n$ $U$ $m$ $V$ $n$ $V^*$ $V$

Exempel

Låt matrisen ges:

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}}

En av de singularvärdesuppdelningarna av denna matris är nedbrytningen , där matriserna och är följande: $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 {{\sq&0 }}&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}},

eftersom matriserna och är enhetliga ( och , där är identitetsmatrisen ), och är en rektangulär diagonal matris , det vill säga om . $U$ $V$ $UU^{*}=I$ $VV^{*}=I$ $jag$ $\Sigma$ $\Sigma _{{ij}}=0$ $i \neq j$

Geometrisk känsla

Låt matrisen associeras med en linjär operator . Singularvärdesuppdelningen kan omformuleras i geometriska termer. En linjär operator som kartlägger rymdelement i sig själv kan representeras som successivt utförda linjära operatorer för rotation och sträckning. Därför visar komponenterna i singulära värdenedbrytningen tydligt geometriska förändringar när en linjär operator mappar en uppsättning vektorer från ett vektorrum in i sig självt eller in i ett vektorrum av en annan dimension [1] . $A$ $\mathbb {R} ^{n}$ $A$

För en mer visuell representation, överväg en sfär med enhetsradie i rymden . Linjemappning mappar denna sfär till en rymdellipsoid . Då är singularvärdena som inte är noll för matrisens diagonal längden på halvaxlarna för denna ellipsoid. I fallet när och alla singularvärden är olika och skiljer sig från noll, kan singularvärdesuppdelningen av en linjär mappning enkelt analyseras som en konsekvens av tre åtgärder: överväg en ellipsoid och dess axlar; överväg sedan riktningarna i att kartläggningen mappar till dessa axlar. Dessa riktningar är ortogonala. Först tillämpar vi isometri genom att kartlägga dessa riktningar för att koordinera axlar . Det andra steget är att applicera en endomorfism diagonaliserad längs koordinataxlarna och expandera/sammandraga dessa riktningar, med hjälp av längderna på semiaxlarna som sträckningsfaktorer. Produkten mappar sedan enhetssfären på en isometrisk ellipsoid . För att bestämma det sista steget , tillämpa helt enkelt isometri på denna ellipsoid för att omvandla den till . Som du enkelt kan kontrollera är produkten densamma som . $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$

Applikationer

Pseudo-invers matris

Singular värdenedbrytning kan användas för att hitta pseudoinversa matriser , som särskilt gäller minsta kvadratmetoden .

Om , så hittas matrisen pseudo-invers till den av formeln: $M=U\Sigma V^{*}$

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

där är pseudoinversen till matrisen , erhållen från den genom att ersätta varje diagonalelement med dess invers: och transponera. $\Sigma ^{{-1}}$ $\Sigma$ $\sigma$ ${\displaystyle {\sigma }^{-1))$

Approximation med en matris av lägre rang

I vissa praktiska problem krävs det att approximera en given matris med någon annan matris med en förutbestämd rangordning . Följande sats är känd, som ibland kallas Eckart -Yang-satsen. [2] $M$ $M_{k}$ $k$

Om vi kräver att en sådan approximation är den bästa i den meningen att den euklidiska normen för skillnaden mellan matriser och är minimal, under begränsningen , så visar det sig att den bästa sådan matrisen erhålls från singularvärdesuppdelningen av matris med formeln: $M$ $M_{k}$ ${\mbox{rank}}(M_{k})=k$ $M_{k}$ $M$

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

där är matrisen där alla diagonala element är ersatta av nollor, förutom de största elementen. $\Sigma _{k}$ $\Sigma$ $k$

Om elementen i matrisen är ordnade i icke-ökande ordning, kan uttrycket för matrisen skrivas om i följande form: $\Sigma$ $M_{k}$

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

där matriserna , och erhålls från motsvarande matriser i singularvärdesuppdelningen av matrisen genom att skära till exakt de första kolumnerna. $Storbritannien$ $\Sigma _{k}$ $V_{k}$ $M$ $k$

Således kan det ses att genom att approximera matrisen med en matris av lägre rang, utför vi en slags komprimering av informationen som finns i : storleksmatrisen ersätts av mindre storleksmatriser och en diagonal matris med element. I det här fallet sker komprimeringen med förluster - endast den mest betydande delen av matrisen bevaras i approximationen . $M$ $M$ $M$ $m\ gånger n$ $m \tid k$ $k \ gånger n$ $k$ $M$

Till stor del på grund av denna egenskap får singulära värdenedbrytning bred praktisk tillämpning: inom datakomprimering, signalbehandling, numeriska iterativa metoder för att arbeta med matriser, huvudkomponentanalys , latent semantisk analys och andra områden.

Förkortad version

För en matris av ordning , om det är nödvändigt att approximera med en matris med rang som är mindre än , används ofta en kompakt nedbrytningsrepresentation [3] : $M$ $m\ gånger n$ $r$ $n$

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

Endast kolumner och rader beräknas . Resten av kolumnerna och raderna beräknas inte. Detta sparar mycket minne när . $r$ $U$ $r$ $V^*$ $U$ $V^*$ $r\ll n$

Låt oss ge ett exempel, låt oss säga att detta är antalet användare, som var och en lägger ner en del av betygen för filmer, vars totala antal kommer att betecknas med , sedan matrisen (mycket sparsam, eftersom varje användare endast har betygsatt en liten del av filmerna) kommer att betecknas och ha en tillräckligt stor dimension . $m$ $n$ $M$ $[m\times n]$

Om vi vill arbeta med en matris med mindre dimensioner måste vi beräkna singularvärdesuppdelningen:

$M=U\Sigma V^{*}$ i detta fall är matrisen , som tidigare nämnts, diagonal. Efter det, om vi bara vill spara information, måste vi ta , så att summan av kvadraterna av de första elementen är från den totala summan av alla kvadraterna av de diagonala elementen . $\Sigma$ $90\%$ $r$ $\Sigma$ $90\%$ $\Sigma$

Så vi får dimensionen (tar kolumnerna), dimensionen och c . Sedan, istället för en matris, kan vi manipulera en matris med lägre dimensioner , som ofta tolkas som en matris av användarbetyg efter filmkategori. $U$ $[m\times r]$ $r$ $\Sigma$ $[r\times r]$ $V^*$ $[r\times n]$ $M$ $M'=U\Sigma$ $[m\times r]$

Programvaruimplementeringar

Numeriska algoritmer för att hitta singularvärdesuppdelningen är inbyggda i många matematiska paket. Till exempel, i MATLAB- och GNU Octave- system kan den hittas med kommandot

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

SVD ingår i listan över grundläggande metoder för många matematiska bibliotek, inklusive fritt distribuerade.
Det finns till exempel implementeringar

Från GNU Scientific library (GSL):

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

I ROOT-ramverket, utvecklat vid CERN och allmänt använt i det vetenskapliga samfundet:

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

I Intel® Math Kernel Library (Intel® MKL).

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

I numpy- biblioteket för linjär algebra i Python:

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

I tensorflow-maskininlärningsbiblioteket:

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

Och några andra

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

Se även

Anteckningar

↑ Singular värdenedbrytning på erkännandewikin . Hämtad 8 november 2009. Arkiverad från originalet 26 maj 2012. (obestämd)
↑ Eckart, C. och Young, G. Approximationen av en matris med en annan av lägre rang. Psychometrica, 1936, 1, 211-218.
↑ Peter Harrington. Machine Learning in Action . - Shelter Island, 2012. - S. 280 . — ISBN 9781617290183 .

Litteratur

William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. 2.6 Singular Value Decomposition // Numeriska recept i C. - 2:a upplagan. — Cambridge: Cambridge University Press. - ISBN 0-521-43108-5 .

Länkar

Artiklar

Artikel om nedbrytning av singular värde på machinelearning.ru
Artikel om MathWorld och ett exempel på användning för bildkomprimering. (Engelsk)

Föreläsningar online

Föreläsning om singular värdenedbrytning inom ramen för huvudkomponentanalys , Heidelbergs universitet, prof. Fred Hamprecht

Vektorer och matriser

Vektorer

Grundläggande koncept	Vektor i geometri Grund Ortogonal grund Vektorkoordinater Kolinearitet Ortogonalitet Linjärt beroende Kolumnutrymme
Typer av vektorer	Enhet vektor Axiell vektor isotrop vektor Vanligt Kolinearitet Noll vektor Radie vektor Egenvektor
Operationer på vektorer	Skalär produkt vektor produkt blandad produkt Pseudoskalär produkt Dubbelkorsprodukt
Utrymmestyper	vektor utrymme affint utrymme Euklidiskt utrymme Pseudo-euklidiskt utrymme Normerat utrymme Minkowski utrymme

matriser

Grundläggande koncept	Matrismultiplikation Transponerad matris Hermitisk konjugatmatris Symmetrisk matris invers matris Eget värde Karakteristiskt polynom för en matris
Specialmatriser	Identitetsmatris Noll matris Diagonal matris lambda matris
Matrisnedbrytningar	LU-nedbrytning Cholesky nedbrytning QR-sönderdelning LUP-nedbrytning singulärvärdesfaktorisering Spektral nedbrytning av en matris

Övrig