Singulierewaardenontbinding
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c8/Singular_value_decomposition_visualisation.svg/260px-Singular_value_decomposition_visualisation.svg.png)
De singulierewaardenontbinding (SWO; Engels: singular value decomposition, SVD) is een belangrijk begrip uit de lineaire algebra en numerieke wiskunde. De singuliere waarden beschrijven eigenschappen van een willekeurige matrix, analoog aan de eigenwaarden van een vierkante matrix. De SWO wordt onder meer gebruikt bij de studie van lineaire afbeeldingen, het bepalen van normen van matrices, het berekenen van de veralgemeende inverse of pseudo-inverse van een willekeurige matrix en de kleinstekwadratenoplossing van een willekeurig stelsel van lineaire vergelijkingen.
Definitie
Stel is een reële -matrix van rang kan geschreven worden als het product van drie matrices:
waarin:
- een -orthogonale matrix is: ,
- een -orthogonale matrix: , en
- een -pseudo-diagonaalmatrix. De eerste elementen op de diagonaal zijn de singuliere waarden van , die we noteren als met ; alle andere elementen van zijn nul.
De kolommen van zijn de linker singuliere vectoren.
De kolommen van zijn de rechter singuliere vectoren.
De matrix is uniek; zijn dat echter niet.
Verband met eigenwaarden
De matrix is een reële -symmetrische matrix met dezelfde nulruimte als , en heeft dus ook rang Die kan worden ontbonden als:
waarin een orthogonale -matrix is en een -diagonaalmatrix van rang met de eigenwaarden van op de diagonaal. is positief semi-definiet en van de eigenwaarden zijn er van de strikt positief: ; de andere () zijn nul.
De singuliere waarden zijn de positieve vierkantswortels uit de strikt positieve eigenwaarden van :
Bepaling van de SWO
Het bovenstaande levert de volgende methode voor het bepalen van de singulierewaardenontbinding van een matrix :
- Bereken de vierkante matrix .
- Bepaal de eigenwaarden daarvan en rangschik die van groot naar klein. De positieve vierkantswortels ervan zijn de singuliere waarden in de matrix .
- Vind genormeerde eigenvectoren met lengte 1, voor elke eigenwaarde. Dit zijn de kolommen van de matrix .
- De eerste kolommen van kan men berekenen met:
- Deze kolommen vormen een orthonormaal stel. Ze kunnen aangevuld worden tot een orthonormaal stel van vectoren met de gram-schmidtmethode.
Rekenvoorbeeld
Gegeven de matrix
Hieruit volgt
De eigenwaarden van deze matrix volgen uit
Dit is de vierkantsvergelijking met als wortels de eigenwaarden .
De twee singuliere waarden van zijn dus:
De eigenvector behorend bij de grootste eigenwaarde, 12, volgt uit de matrixvergelijking
Hiervoor kunnen we kiezen (deze vector is nog niet genormeerd).
Voor de tweede eigenwaarde, 10, geldt analoog:
Hiervoor kunnen we kiezen; maar zou even goed zijn.
De matrix met als kolommen deze eigenvectoren:
moeten we nu herleiden naar een orthogonale matrix. Dat gebeurt met de gram-schmidtmethode toegepast op de kolomvectoren van deze matrix. In dit geval zijn de kolomvectoren reeds orthogonaal. Na normering krijgen we dus de matrix :
De eerste twee kolommen van zijn dan:
en
De derde kolom van wordt dan:
De volledige singulierewaardenontbinding van is ten slotte:
Numerieke berekening van de SWO
In de bovenstaande berekening werd de gram-schmidtmethode gebruikt bij de berekening van de eigenwaarden en eigenvectoren van de matrix . Voor computerberekeningen met beperkte nauwkeurigheid is de gram-schmidtmethode echter niet geschikt. Ze is niet numeriek stabiel; door de opeenstapeling van afrondingsfouten zijn de berekende vectoren niet meer orthogonaal. In de jaren 1960 ontwikkelden Gene Golub en medewerkers numeriek stabiele algoritmen voor de berekeningen van de singulierewaardenontbinding.[1]
Voor de berekening van eigenwaarden of singuliere waarden van grote ijle matrices is het iteratieve lanczos-algoritme (naar Cornelius Lanczos) geschikt. Dit algoritme wordt gebruikt in het softwarepakket SVDPACK.[2]
Toepassingen
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/08/SVD_Energy.svg/260px-SVD_Energy.svg.png)
SWO wordt veel gebruikt in de statistiek, signaalverwerking, patroonherkenning en verwante sectoren. Met singuliere waarden kan men een reductie verkrijgen in de dimensie van een probleem en een verkleining van de tijd om het op te lossen. Een voorbeeld is biometrische gezichtsherkenning: een foto of beeld van een gezicht wordt voorgesteld als een matrix van een aantal beeldelementen of pixels, naargelang de beeldresolutie. De belangrijkste kenmerken en verhoudingen van zo een beeld moeten dan vergeleken worden met die uit een database van bestaande personen om degene te vinden die er het meeste op lijkt. In plaats hiervoor de volledige beeldmatrix te gebruiken, kan men met een beperkt aantal singuliere waarden werken, die de structuur van de originele gegevens weergeven. Met een Hidden Markov Model kan dan de meest gelijkende kandidaat gezocht worden.[3]
SWO wordt ook gebruikt om ruis uit een reeks meetwaarden te verwijderen. Het energieverschil tussen het nuttig signaal en de ruis uit zich in de singuliere waarden van een matrix die uit de meetwaarden wordt opgebouwd. De grootste singuliere waarden zijn het meest representatief; de kleinere waarden zijn te wijten aan ruis en kan men door nul vervangen. Dan kan men een signaal zonder ruis reconstrueren.[4]
Bronnen
- Joos Vandewalle & Ronald Cools. Toegepaste algebra: Lineaire algebra en analytische meetkunde. Garant, Leuven/Apeldoorn, 1998. ISBN 9053507728
- Paul Larmuseau Voorbeeld van online SVD tool met recommender algoritm
- ↑ G. Golub, W. Kahan. "Calculating the singular values and pseudo-inverse of a matrix." J. SIAM Numer. Anal. Ser. B (1965), vol. 2 nr. 2, blz. 205-224.
- ↑ SVDPACK
- ↑ Anagha A. Shinde, Sachin D. Ruikar. "Face Recognition Using Singular Value Decomposition along with seven state HMM." IJCSNS International Journal of Computer Science and Network Security (2013), vol. 13 nr. 12, blz. 117
- ↑ Wenbin Zhang, Jiaxing Zhu, Yanping Su, Yasong Pu. "A New Signal De-noising Method Based on Energy Difference Spectrum of Singular Value." Information Technology Journal (2013), vol. 12 nr. 19, blz. 5206-5210; DOI:10.3923/itj.2013.5206.5210