Descompunerea unei valori singulare

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 5 ianuarie 2022; verificările necesită 8 modificări .

Descompunerea valorii singulare este un anumit tip de descompunere a unei matrice dreptunghiulare , care este utilizat pe scară largă, datorită interpretării sale geometrice vizuale, în rezolvarea multor probleme aplicate. O reformulare a descompunerii valorii singulare, așa-numita descompunere Schmidt , are aplicații în teoria informației cuantice , cum ar fi în încheiere .

Descompunerea valorii singulare a unei matrice permite calcularea valorilor singulare ale unei matrice date, precum și vectorii singulari stânga și dreapta ai matricei : $M$ $M$

vectorii singulari stângi ai matricei sunt vectorii proprii ai matricei ; $M$ $MM^{{*}}$
vectorii singulari de dreapta ai matricei sunt vectorii proprii ai matricei . $M$ $M^{{*}}M$

Unde este matricea conjugată Hermitiană la matrice , pentru o matrice reală . $M^{*}$ $M$ $M^{*}=M^{T)$

Valorile singulare ale unei matrice nu trebuie confundate cu valorile proprii ale aceleiași matrice.

Descompunerea valorii singulare este utilă în calcularea rangului unei matrice , a nucleului unei matrice și a pseudoinversului unei matrice .

Descompunerea valorii singulare este, de asemenea, utilizată pentru a aproxima matrice prin matrice de un anumit rang.

Definiție

Fie ca matricea de ordine să fie formată din elemente din câmp , unde este fie câmpul numerelor reale, fie câmpul numerelor complexe . $M$ $m\ori n$ $K$ $K$

Numere singulare și vectori singulari

Un număr real nenegativ se numește valoare singulară a matricei atunci când există doi vectori de lungime unitară și astfel încât: $\sigma$ $M$ $u\în K^{m}$ $v\în K^{n}$

Mv=\sigma u,

și

M^{*}u=\sigma v.

Astfel de vectori se numesc, respectiv, vector singular stânga și vector singular drept corespunzător numărului singular . $u$ $v$ $\sigma$

Descompunerea matricei

Descompunerea valorii singulare a matricei de ordine este descompunerea următoarei forme $M$ $m\ori n$

M=U\Sigma V^{*},

unde este o matrice de dimensiune cu elemente nenegative, în care elementele aflate pe diagonala principală sunt numere singulare (și toate elementele care nu se află pe diagonala principală sunt zero), iar matricele (de ordin ) și (de ordin ) sunt două matrice unitare , formate din vectori singulari stânga și respectiv dreapta (a este matricea conjugat-transpusă k ). $\Sigma$ $m\ori n$ $U$ $m$ $V$ $n$ $V^*$ $V$

Exemplu

Fie dată matricea:

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

Una dintre descompunerea de valoare singulară a acestei matrice este descompunerea , unde matricele și sunt următoarele: $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&rt {&5\\sq&rt }}&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}},

deoarece matricele și sunt unitare ( și , unde este matricea de identitate ), și este o matrice diagonală dreptunghiulară , adică dacă . $U$ $V$ $UU^{*}=I$ $VV^{*}=I$ $eu$ $\Sigma$ $\Sigma _{{ij}}=0$ $eu \neq j$

Sensul geometric

Fie asociată matricei cu un operator liniar . Descompunerea valorii singulare poate fi reformulată în termeni geometrici. Un operator liniar care mapează elementele spațiale în sine poate fi reprezentat ca operatori liniari executați succesiv de rotație și întindere. Prin urmare, componentele descompunerii valorii singulare arată clar schimbări geometrice atunci când un operator liniar mapează un set de vectori dintr-un spațiu vectorial în sine sau într-un spațiu vectorial de altă dimensiune [1] . $A$ $\mathbb {R} ^{n}$ $A$

Pentru o reprezentare mai vizuală, luați în considerare o sferă cu raza unitară în spațiu . Maparea liniilor mapează această sferă la un elipsoid de spațiu . Atunci valorile singulare diferite de zero ale diagonalei matricei sunt lungimile semi- axelor acestui elipsoid. În cazul în care și toate valorile singulare sunt diferite și diferite de zero, descompunerea valorii singulare a unei mapări liniare poate fi ușor analizată ca o consecință a trei acțiuni: luați în considerare un elipsoid și axele sale; apoi luați în considerare direcțiile în care maparea se mapează la aceste axe. Aceste direcții sunt ortogonale. În primul rând, aplicăm izometria prin maparea acestor direcții la axele de coordonate . Al doilea pas este aplicarea unui endomorfism diagonalizat de-a lungul axelor de coordonate și extinderea/contractarea acestor direcții, folosind lungimile semiaxelor ca factori de întindere. Produsul mapează apoi sfera unității pe un elipsoid izometric . Pentru a determina ultimul pas , pur și simplu aplicați izometria acestui elipsoid pentru a-l converti în . După cum puteți verifica cu ușurință, produsul este același cu . $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$

Aplicații

Matrice pseudo-inversa

Descompunerea valorii singulare poate fi utilizată pentru a găsi matrici pseudoinverse , care se aplică, în special, metodei celor mai mici pătrate .

Dacă , atunci matricea pseudo-inversa față de aceasta se găsește prin formula: $M=U\Sigma V^{*}$

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

unde este pseudoinversul matricei , obținut din aceasta prin înlocuirea fiecărui element diagonal cu inversul său: și transpunerea. $\Sigma ^{{-1}}$ $\Sigma$ $\sigma$ ${\sigma}^{-1)$

Aproximare printr-o matrice de rang inferior

În unele probleme practice, este necesar să se aproximeze o matrice dată cu o altă matrice cu un rang predeterminat . Este cunoscută următoarea teoremă, care uneori este numită teorema Eckart -Yang. [2] $M$ $M_{k}$ $k$

Dacă cerem ca o astfel de aproximare să fie cea mai bună în sensul că norma euclidiană a diferenței matricelor și este minimă, sub constrângerea , atunci rezultă că cea mai bună astfel de matrice este obținută din descompunerea valorii singulare a matricei. matrice prin formula: $M$ $M_{k}$ ${\mbox{rank}}(M_{k})=k$ $M_{k}$ $M$

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

unde este matricea în care toate elementele diagonale sunt înlocuite cu zerouri, cu excepția celor mai mari elemente. $\Sigma _{k}$ $\Sigma$ $k$

Dacă elementele matricei sunt ordonate în ordine necrescătoare, atunci expresia pentru matrice poate fi rescrisă în următoarea formă: $\Sigma$ $M_{k}$

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

unde matricele , și sunt obținute din matricele corespunzătoare în descompunerea valorii singulare a matricei prin tăierea la exact primele coloane. $Regatul Unit$ $\Sigma _{k}$ $V_{k}$ $M$ $k$

Astfel, se poate observa că prin aproximarea matricei cu o matrice de rang inferior, se efectuează un fel de compresie a informațiilor conținute în : matricea de dimensiuni este înlocuită cu matrice de dimensiuni mai mici și și o matrice diagonală cu elemente. În acest caz, compresia are loc cu pierderi - doar cea mai semnificativă parte a matricei este păstrată în aproximare . $M$ $M$ $M$ $m\ori n$ $m \time k$ $k \times n$ $k$ $M$

În mare parte datorită acestei proprietăți, descompunerea valorilor singulare își găsește o aplicație practică largă: în compresia datelor, procesarea semnalului, metode iterative numerice de lucru cu matrice, analiza componentelor principale , analiza semantică latentă și alte domenii.

Versiune prescurtată

Pentru o matrice de ordin , dacă este necesar să se aproximeze printr-o matrice de rang mai mic decât , se folosește adesea o reprezentare de descompunere compactă [3] : $M$ $m\ori n$ $r$ $n$

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

Sunt calculate doar coloanele și rândurile . Restul coloanelor și rândurilor nu sunt calculate. Acest lucru economisește multă memorie atunci când . $r$ $U$ $r$ $V^*$ $U$ $V^*$ $r\ll n$

Să dăm un exemplu, să presupunem că acesta este numărul de utilizatori, dintre care fiecare a pus o parte din evaluările pentru filme, al căror număr total va fi notat cu , apoi matricea (foarte rar, deoarece fiecare utilizator a evaluat doar o mică parte din filme) vor fi notate și au o dimensiune suficient de mare . $m$ $n$ $M$ $[m\times n]$

Dacă vrem să lucrăm cu o matrice de dimensiuni mai mici, trebuie să calculăm descompunerea valorii singulare:

$M=U\Sigma V^{*}$ în acest caz, matricea , așa cum am menționat mai devreme, este diagonală. După aceea, dacă vrem să salvăm doar informații, atunci trebuie să luăm , astfel încât suma pătratelor primelor elemente să fie din suma totală a tuturor pătratelor elementelor diagonale . $\Sigma$ $90\%$ $r$ $\Sigma$ $90\%$ $\Sigma$

Deci obținem dimensiunea (luând coloanele), dimensiunea și c . Apoi, în loc de o matrice, putem manipula o matrice de dimensiuni inferioare , care este adesea interpretată ca o matrice a evaluărilor utilizatorilor în funcție de categoria de film. $U$ $[m\times r]$ $r$ $\Sigma$ $[r\times r]$ $V^*$ $[r\times n]$ $M$ $M'=U\Sigma$ $[m\times r]$

Implementări software

Algoritmii numerici pentru găsirea descompunerii valorii singulare sunt încorporați în multe pachete matematice. De exemplu, în sistemele MATLAB și GNU Octave , acesta poate fi găsit cu comanda

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

SVD este inclus în lista metodelor de bază a multor biblioteci matematice, inclusiv a celor distribuite gratuit.
De exemplu, există implementări

Din biblioteca științifică GNU (GSL):

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

În cadrul ROOT, dezvoltat la CERN și utilizat pe scară largă în comunitatea științifică:

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

În Biblioteca Intel® Math Kernel (Intel® MKL).

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

În biblioteca numpy pentru algebra liniară în Python:

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

În biblioteca de învățare automată a tensorflow:

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

Și alții

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

Vezi și

Note

↑ Descompunerea valorii singulare pe wiki Recunoaștere . Consultat la 8 noiembrie 2009. Arhivat din original la 26 mai 2012. (nedefinit)
↑ Eckart, C. și Young, G. Aproximarea unei matrice cu o alta de rang inferior. Psychometrica, 1936, 1, 211-218.
↑ Peter Harrington. Învățarea automată în acțiune . - Insula Adăpostului, 2012. - P. 280 . — ISBN 9781617290183 .

Literatură

William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. 2.6 Descompunerea valorii singulare // Rețete numerice în C. - ediția a II-a. — Cambridge: Cambridge University Press. - ISBN 0-521-43108-5 .

Link -uri

Articole

Articol despre descompunerea valorii singulare pe machinelearning.ru
Articol despre MathWorld și un exemplu de utilizare pentru compresia imaginii. (Engleză)

Prelegeri on-line

Prelegere despre descompunerea valorii singulare în contextul analizei componentelor principale , Universitatea Heidelberg, prof. Fred Hamprecht

Vectori și matrici

Vectori

Noțiuni de bază	Vector în geometrie Bază Baza ortogonala Coordonatele vectoriale Coliniaritate Ortogonalitatea Dependență liniară Spațiu coloane
Tipuri de vectori	Vector unitar Vector axial vector izotrop Normal Coliniaritate Vector zero Vector rază Vector propriu
Operații pe vectori	Produs scalar produs vectorial produs mixt Produs pseudoscalar Produs dublu cruce
Tipuri de spațiu	spațiu vectorial spatiu afin Spațiul euclidian Spațiul pseudo-euclidian Spațiu normat Spațiul Minkowski

matrici

Noțiuni de bază	Înmulțirea matricei Matrice transpusă Matricea conjugată hermitiană Matricea simetrică matrice inversă Valoare proprie Polinom caracteristic al unei matrice
Matrici speciale	Matrice de identitate Matrice zero Matricea diagonală matricea lambda
Descompuneri de matrice	descompunerea LU Descompunerea Cholesky Descompunerea QR Descompunerea LUP descompunerea unei valori singulare Descompunerea spectrală a unei matrice

Alte