Inom linjär algebra är singulärvärdesuppdelning (SVD), ibland kallat singulärvärdesfaktorisering eller singulärvärdesdekomposition, en sorts matrisfaktorisering. Alla reella och komplexa matriser kan singulärvärdefaktoriseras.
För en matris A av storlek
är singulärvärdesuppdelningen
![{\displaystyle A=U\Sigma V^{*}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/157896e3c4ac0287275188526829ee759f8b5277)
där U är en kvadratisk unitär
-matris,
en är en diagonal och icke-negativ
-matris och
betecknar det hermiteska konjugatet till V, som är en unitär
-matris. Matrisen
har singulärvärdena till
i sin diagonal, och vanlig praxis är att dessa singulärvärden ordnas i storleksordning med det största singulärvärdet först vänsterifrån i
.
Singulärvärdesuppdelning är inte entydig. Exempelvis är
också en giltig uppdelning, där
och
är diagonalmatriser med
i diagonalen, för godtyckligt värde på
.
Man kan skriva om singulärvärdesuppdelningen
, där matrisen A har rang r, som en summa med r stycken matriser, så att varje matris i summan får rang 1, enligt nedan.
![{\displaystyle A=\underbrace {\sum _{i=1}^{r}\sigma _{i}{\boldsymbol {u}}_{i}{\boldsymbol {v}}_{i}^{*}} _{\mbox{rang r}}=\underbrace {\sigma _{1}{\boldsymbol {u}}_{1}{\boldsymbol {v}}_{1}^{*}} _{\mbox{rang 1}}+\ldots +\underbrace {\sigma _{r}{\boldsymbol {u}}_{r}{\boldsymbol {v}}_{r}^{*}} _{\mbox{rang 1}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e59cb23f17e0226da6e69d43649a18c24c2c0e09)
Här är
singulärvärde nummer
till A,
kolonnvektor
i U och
radvektor
i V.
Tunn singulärvärdesuppdelning fås genom att enbart beräkna de n vektorer i U som korresponderar med radvektorer i
. Övriga kolumnvektorer i U beräknas inte, och därmed går det mycket snabbare att beräkna en tunn singulärvärdesuppdelning jämfört med en vanlig singulärvärdesuppdelning.
![{\displaystyle A=U_{n}\Sigma _{n}V^{*}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d69e1354bc9b851e03a7d4ef8a2f30dacb68bb8)
Matrisen
blir då en
-matris,
en
-matris och V en
-matris.
Tunn singulärvärdesuppdelning är i synnerhet mer beräkningseffektiv än vanlig singulärvärdesuppdelning om
.
Kompakt singulärvärdesuppdelning fås genom att enbart beräkna de r kolumnerna i U och de r raderna i
som korresponderar mot nollskilda singulärvärden. Då fås:
![{\displaystyle A=U_{r}\Sigma _{r}V_{r}^{*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b00259c2544e4239ef31cdc73a723feb6bc5b4d0)
Här är
en
-matris,
en diagonal
-matris och
en
-matris.
Kompakt singulärvärdesuppdelning är mer beräkningseffektiv än tunn singulärvärdesuppdelning om
.
För en
-matris A fås singulärvärdesuppdelningen i ett fåtal steg. Man börjar med att beräkna den kvadratiska matrisen
. Varför man gör detta syns tydligare om man skriver om
med singulärvärdesuppdelning:
![{\displaystyle A^{*}A=(U\Sigma V^{*})^{*}U\Sigma V^{*}=V\Sigma ^{*}\underbrace {U^{*}U} _{=I}\Sigma V^{*}=V\Sigma ^{*}\Sigma V^{*}\ =V\underbrace {\begin{pmatrix}|\sigma _{1}|^{2}&&&\\&|\sigma _{2}|^{2}&&\\&&\ddots &&\\&&&|\sigma _{k}|^{2}\end{pmatrix}} _{\tilde {\Sigma }}V^{*},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/851bf130043c75d51328aa92025695e9359a5084)
Spektralsatsen för hermiteska matriser säger att alla hermiteska matriser M kan skrivas som
, där
är en diagonal matris med egenvärdena till matrisen M i diagonalen. Kolonnvektorerna till W utgörs av egenvektorerna till matrisen M , som i sin tur utgör en ortonormerad bas. Notera att eftersom M är en hermitesk matris har den enbart reella egenvärden.
Eftersom
är en hermitesk matris (
) har vi alltså likheten
![{\displaystyle V{\tilde {\Sigma }}V^{*}=W\Lambda W^{*}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca0e61b54ab404d98f52e665f6ae6d2330b4f5c3)
Eftersom singulärvärdena till A är positiva (alltså är
) ser man att dessa fås genom att ta roten ur egenvärdena till
, dessutom ser man att V fås genom att beräkna egenvektorer till matrisen
.
Med
,
och
kända beräknas
enkelt genom att ställa upp
. Eftersom
är en diagonal matris är det enkelt att beräkna likheten. Ifall, för
-matrisen A,
eller ifall matrisen A inte har full rang kommer några kolonner inte att fås i detta steg, eftersom de multipliceras med 0. Dessa kolonnvektorer väljs då med fördel så att matrisen U blir unitär.
Alternativt kan man beräkna U genom att ställa upp
, då har man istället V som obekant och V kan beräknas som förklaras ovan. Man kan även beräkna U samt V separat genom att ställa upp
och
, denna metod innebär dock oftast mer arbete då man måste beräkna egenvektorer till två matriser.
![{\displaystyle A={\begin{pmatrix}1&0\\0&1\\-1&2\end{pmatrix}}\;,\;m=3\;,\;n=2\;,\;{\mbox{reellt}}(A^{*}=A^{T})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9612651603052d734e4a1d29676af8900e439028)
Man börjar med att beräkna
.
![{\displaystyle A^{*}A={\begin{pmatrix}1&0&-1\\0&1&2\end{pmatrix}}{\begin{pmatrix}1&0\\0&1\\-1&2\end{pmatrix}}={\begin{pmatrix}2&-2\\-2&5\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc35f71c958cd25f2de7a9454df14723deecffd5)
Nu beräknar man egenvärden och egenvektorer till
genom att ställa upp det karakteristiska polynomet, för exempel på detta se artikeln om egenvärden och egenvektorer. Vi får egenvärdena till
, och därmed blir singulärvärdena
. Vi får egenvektorerna (normerade) enligt nedan:
![{\displaystyle {\boldsymbol {v}}_{1}={\frac {1}{\sqrt {5}}}{\begin{pmatrix}1\\-2\end{pmatrix}},{\boldsymbol {v}}_{2}={\frac {1}{\sqrt {5}}}{\begin{pmatrix}2\\1\end{pmatrix}}\Rightarrow V={\frac {1}{\sqrt {5}}}{\begin{pmatrix}1&2\\-2&1\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/576809cada2287f9452070cfe8f85aaba9828f7b)
Nu beräknar man U med hjälp av sambandet
![{\displaystyle AV={\frac {1}{\sqrt {5}}}{\begin{pmatrix}1&2\\-2&1\\-5&0\end{pmatrix}}={\begin{pmatrix}|&|&|\\{\boldsymbol {u}}_{1}&{\boldsymbol {u}}_{2}&{\boldsymbol {u}}_{3}\\|&|&|\end{pmatrix}}{\begin{pmatrix}{\sqrt {6}}&0\\0&1\\0&0\end{pmatrix}}=U\Sigma \,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e4a6c178cddf142d38bfa4c12f125ccaab55276d)
Man ser att
kommer multipliceras med
, att
kommer multipliceras med 1 och att
kommer multipliceras med 0. Nu väljer man
och
så att likheten
gäller,
väljs ortogonal mot
och
.
![{\displaystyle {\boldsymbol {u}}_{1}={\frac {1}{\sqrt {30}}}{\begin{pmatrix}1\\-2\\-5\end{pmatrix}},{\boldsymbol {u}}_{2}={\frac {1}{\sqrt {5}}}{\begin{pmatrix}2\\1\\0\end{pmatrix}},{\boldsymbol {u}}_{3}={\frac {1}{\sqrt {6}}}{\begin{pmatrix}1\\-2\\1\end{pmatrix}}\Rightarrow U={\begin{pmatrix}{\frac {1}{\sqrt {30}}}&{\frac {2}{\sqrt {5}}}&{\frac {1}{\sqrt {6}}}\\{\frac {-2}{\sqrt {30}}}&{\frac {1}{\sqrt {5}}}&{\frac {-2}{\sqrt {6}}}\\{\frac {-5}{\sqrt {30}}}&0&{\frac {1}{\sqrt {6}}}\end{pmatrix}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/100e02f9988b29f25f78ecc573a87cf39fe203bd)
Alltså har vi vår singulärvärdesuppdelning enligt nedan.
Singulärvärdesuppdelningen på vanlig form:
![{\displaystyle \underbrace {\begin{pmatrix}1&0\\0&1\\-1&2\end{pmatrix}} _{A}=\underbrace {\begin{pmatrix}{\frac {1}{\sqrt {30}}}&{\frac {2}{\sqrt {5}}}&{\frac {1}{\sqrt {6}}}\\{\frac {-2}{\sqrt {30}}}&{\frac {1}{\sqrt {5}}}&{\frac {-2}{\sqrt {6}}}\\{\frac {-5}{\sqrt {30}}}&0&{\frac {1}{\sqrt {6}}}\end{pmatrix}} _{U}\underbrace {\begin{pmatrix}{\sqrt {6}}&0\\0&1\\0&0\end{pmatrix}} _{\Sigma }\underbrace {\begin{pmatrix}{\frac {1}{\sqrt {5}}}&{\frac {-2}{\sqrt {5}}}\\{\frac {2}{\sqrt {5}}}&{\frac {1}{\sqrt {5}}}\end{pmatrix}} _{V^{*}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86f84b653386a7aa53f4d1d30c9b027231f3fae8)
Singulärvärdesuppdelningen på summaform:
![{\displaystyle \underbrace {\begin{pmatrix}1&0\\0&1\\-1&2\end{pmatrix}} _{A}=\underbrace {\sqrt {6}} _{\sigma _{1}}\underbrace {\begin{pmatrix}{\frac {1}{\sqrt {30}}}\\{\frac {-2}{\sqrt {30}}}\\{\frac {-5}{\sqrt {30}}}\end{pmatrix}} _{{\boldsymbol {u}}_{1}}\underbrace {\begin{pmatrix}{\frac {1}{\sqrt {5}}}&{\frac {-2}{\sqrt {5}}}\end{pmatrix}} _{{\boldsymbol {v}}_{1}^{*}}+\underbrace {1} _{\sigma _{2}}\underbrace {\begin{pmatrix}{\frac {2}{\sqrt {5}}}\\{\frac {1}{\sqrt {5}}}\\0\end{pmatrix}} _{{\boldsymbol {u}}_{2}}\underbrace {\begin{pmatrix}{\frac {2}{\sqrt {5}}}&{\frac {1}{\sqrt {5}}}\end{pmatrix}} _{{\boldsymbol {v}}_{2}^{*}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/81ab1c72996beae39fabe53f09ac57cdf2f24f32)
Singulärvärdesuppdelningen på tunn form:
![{\displaystyle \underbrace {\begin{pmatrix}1&0\\0&1\\-1&2\end{pmatrix}} _{A}=\underbrace {\begin{pmatrix}{\frac {1}{\sqrt {30}}}&{\frac {2}{\sqrt {5}}}\\{\frac {-2}{\sqrt {30}}}&{\frac {1}{\sqrt {5}}}\\{\frac {-5}{\sqrt {30}}}&0\end{pmatrix}} _{U_{2}}\underbrace {\begin{pmatrix}{\sqrt {6}}&0\\0&1\end{pmatrix}} _{\Sigma _{2}}\underbrace {\begin{pmatrix}{\frac {1}{\sqrt {5}}}&{\frac {-2}{\sqrt {5}}}\\{\frac {2}{\sqrt {5}}}&{\frac {1}{\sqrt {5}}}\end{pmatrix}} _{V^{*}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/abcfbe26988e4b2245accf94abc87aa7ac2ee271)
Singulärvärdesuppdelningen till en matris A beräknas typiskt i två steg. I det första steget reduceras A till en bidiagonal matris. Detta tar
flyttalsoperationer, om
.
Det andra steget går ut på att beräkna singulärvärdesuppdelningen till denna bidiagonala matris. Detta steg beräknas iterativt med en bestämd precision. Om denna precision antas konstant tar det andra steget
iterationer, som var kostar
flyttalsoperationer. Därmed är det första steget det dyrare, och den totala kostnaden är
flyttalsoperationer.
Man kan enkelt beräkna Moore-Penrose pseudoinvers, betecknat
nedan, till en matris A med hjälp av singulärvärdesuppdelning. Om A har singulärvärdesuppdelning enligt
fås Moore-Penrose pseudoinvers till A enligt nedan.
![{\displaystyle A^{\dagger }=V\Sigma ^{\dagger }U^{*}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d5acbc1aba33f538c6d69a4e8daba0f98cc27299)
Här beräknar man Σ† genom att först ta inversen av varje nollskillt singulärvärde i Σ, de singulärvärden som var 0 i Σ förblir 0 i Σ†, och sedan transponerar man resultatet. Moore-Penrose pseudoinvers används bland annat för att lösa linjära minstakvadratproblem.
Man kan enkelt bestämma rang samt de fyra fundamentala underrummen (värderummet och nollrummet till en given matris och matrisens hermiteska konjugat) till en matris A genom att titta på matrisens singulärvärdesuppdelning. Antag en singulärvärdesuppdelning enligt nedan, där
till
är samtliga nollskillda singulärvärden.
![{\displaystyle A_{(m,n)}=\underbrace {\begin{pmatrix}|&&|&|&&|\\u_{1}&\cdots &u_{r}&u_{r+1}&\cdots &u_{m}\\|&&|&|&&|\end{pmatrix}} _{m\times m}\underbrace {\begin{pmatrix}\sigma _{1}&&&&&\\&\sigma _{2}&&&&\\&&\ddots &&&\\&&&\sigma _{r}&&\\&&&&&\end{pmatrix}} _{m\times n}\underbrace {\begin{pmatrix}-&{\bar {v}}_{1}&-\\-&\vdots &-\\-&{\bar {v}}_{r}&-\\-&{\bar {v}}_{r+1}&-\\&\vdots &\\-&{\bar {v}}_{n}&-\end{pmatrix}} _{n\times n}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d51674f07c820a447662c98993684e994a0ca126)
Då fås följande:
![{\displaystyle \operatorname {rank} \,A=\dim(V(A))=r\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10f845b1fb5ad9e44f74a4ca9305657221cb41f2)
![{\displaystyle V(A)=N(A^{*})^{\perp }=\left[{\begin{pmatrix}|\\u_{1}\\|\end{pmatrix}},\,{\begin{matrix}\\\cdots \\\end{matrix}}\,,{\begin{pmatrix}|\\u_{r}\\|\end{pmatrix}}\right]\,\subset \,\mathbb {C} ^{m}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fa505d6002d838336cf846d8e92d41c6a56758a1)
![{\displaystyle V(A^{*})=N(A)^{\perp }=\left[{\begin{pmatrix}|\\v_{1}\\|\end{pmatrix}},\,{\begin{matrix}\\\cdots \\\end{matrix}}\,,{\begin{pmatrix}|\\v_{r}\\|\end{pmatrix}}\right]\,\subset \,\mathbb {C} ^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa78af06e2add4ce2898ed66eeb9285e094911c9)
![{\displaystyle N(A)=V(A^{*})^{\perp }=\left[{\begin{pmatrix}|\\v_{r+1}\\|\end{pmatrix}},\,{\begin{matrix}\\\cdots \\\end{matrix}}\,,{\begin{pmatrix}|\\v_{n}\\|\end{pmatrix}}\right]\,\subset \,\mathbb {C} ^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37408dbda633bebb3a4cf92c101e211527b99937)
![{\displaystyle N(A^{*})=V(A)^{\perp }=\left[{\begin{pmatrix}|\\u_{r+1}\\|\end{pmatrix}},\,{\begin{matrix}\\\cdots \\\end{matrix}}\,,{\begin{pmatrix}|\\u_{m}\\|\end{pmatrix}}\right]\,\subset \,\mathbb {C} ^{m}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/67cf2856b6413ce048179ccec8d3a8c27c282e8e)
En vanlig tillämpning av singulärvärdesuppdelning är att approximera en given matris med en annan liknande matris av lägre rang. Om man vill approximera en matris
av rang r med en matris
, som har rang
, där
, fås
med hjälp av singulärvärdesuppdelningen på summaform enligt nedan:
![{\displaystyle A\approx {\tilde {A}}=\sum _{i=1}^{R}\sigma _{i}{\boldsymbol {u}}_{i}{\boldsymbol {v}}_{i}^{*}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8f81e350eb18339bde49abbd0b7b7f16389511d)
I de flesta tillämpningar är felet viktigt, vi betecknar felet B enligt följande.
![{\displaystyle B=A-{\tilde {A}}=A-\sum _{i=1}^{R}\sigma _{i}{\boldsymbol {u}}_{i}{\boldsymbol {v}}_{i}^{*}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce2c154eed64cdcd606c2d9fc97247d9f27632cd)
Genom operatornorm eller frobeniusnorm av B fås felet vid approximationen
, dessa normer kan enkelt beräknas med hjälp av singulärvärdena enligt vad som visas nedan. Vilken av normerna som är bäst lämpad för feluppskattningen beror på tillämpning.
![{\displaystyle ||B||_{OP}=\sigma _{R+1}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d313c50928c531b0fcda375c603457dc1566dfb2)
![{\displaystyle ||B||_{F}={\sqrt {\sigma _{R+1}^{2}+\ldots +\sigma _{r}^{2}}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f98c06ae5bac21e0fbc0e267c374c8c63d5d8b7)
Denna metod för approximation används inom många tillämpningar, bland annat inom signalbehandlning. Om man till exempel har brus av storleksordningen
så kan man slänga bort termer som är små jämfört med bruset så att
ger en förbättrad signal.