Singulierewaardenontbinding
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.

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.

Toepassingen

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.

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.

Bronnen
 Toegepaste algebra: Lineaire algebra en analytische meetkunde. Garant, Leuven/Apeldoorn, 1998. ISBN 9053507728
 Voorbeeld van online SVD tool met recommender algoritm

Lineaire algebra
Matrix
Numerieke wiskunde