Singuliere waarden ontbinding

Illustratie van de ontleding van de enkelvoudige waarde Uσv^⁎ van een echte 2 × 2 -matrix M.

• Bovenkant: De actie van M, aangegeven door het effect ervan op de eenheidsschijf D en de twee canonieke eenheidsvectoren e₁ en e₂.
• Links: De actie van V^⁎, een rotatie, op D, e₁, en e₂.
• Onderkant: De actie van Σ, een schaling door de enkelvoudige waarden σ₁ horizontaal en σ₂ verticaal.
• Rechts: De actie van U, nog een rotatie.

In lineaire algebra, de singuliere waarden ontbinding (SVD) is een factorisatie van een echt of complex Matrix. Het generaliseert de eigendecompositie van een vierkant normale matrix met een orthonormale eigenbasis voor iedereen ${\ displayStyle \ m \ maal n \}$ Matrix. Het is gerelateerd aan de polaire ontleding.

In het bijzonder de ontleding van de enkelvoudige waarde van een ${\ displayStyle \ m \ maal n \}$ complexe matrix M is een factorisatie van de vorm ${\ displayStyle \ \ Mathbf {m} = \ Mathbf {u \ sigma v^{*}} \,}$ waar U is een ${\ displayStyle \ m \ maal m \}$ complex eenheidsmatrix, ${\ DisplayStyle \ \ Mathbf {\ Sigma} \}$ is een ${\ displayStyle \ m \ maal n \}$ rechthoekige diagonale matrix met niet-negatieve reële getallen op de diagonaal, V is een ${\ displaystyle n \ maal n}$ complexe eenheidsmatrix, en ${\ DisplayStyle \ \ Mathbf {v^{*}} \}$ is de conjugaat transponeren van V. Een dergelijke ontleding bestaat altijd voor elke complexe matrix. Als M is echt dan U en V kan gegarandeerd echt zijn orthogonaal matrices; In dergelijke contexten wordt de SVD vaak aangegeven ${\ DisplayStyle \ \ Mathbf {u \ sigma v} ^{\ Mathsf {t}} \.}$

De diagonale inzendingen ${\ displaystyle \ \ sigma _ {i} = \ sigma _ {ii} \}$ van ${\ DisplayStyle \ \ Mathbf {\ Sigma} \}$ worden uniek bepaald door M en staan ​​bekend als de enkelvoudige waarden van M. Het aantal niet-nul enkelvoudige waarden is gelijk aan de rang van M. De kolommen van U en de kolommen van V worden links-singulaire vectoren en rechter-singulaire vectoren van genoemd M, respectievelijk. Ze vormen twee sets van orthonormale bases u₁, ..., u_m en v₁, ..., v_n , en als ze worden gesorteerd zodat de enkelvoudige waarden ${\ DisplayStyle \ \ Sigma _ {i} \}$ Met waarde nul bevinden zich allemaal in de hoogst genummerde kolommen (of rijen), kan de ontleding van de enkelvoudige waarde worden geschreven als ${\displaystyle \ \mathbf {M} =\sum _{i=1}^{r}\sigma _{i}\mathbf {u} _{i}\mathbf {v} _{i}^{*} \,}$ waar ${\ displaystyle \ r \ leq \ min \ {m, n \} \}$ is de rang van M.

De SVD is niet uniek. Het is altijd mogelijk om de ontleding te kiezen, zodat de enkelvoudige waarden ${\ DisplayStyle \ Sigma _ {ii}}$ zijn in dalende volgorde. In dit geval, ${\ DisplayStyle \ Mathbf {\ Sigma}}$ (maar niet U en V) wordt uniek bepaald door M.

De term verwijst soms naar de Compact SVD, een soortgelijke ontleding ${\ DisplayStyle \ \ Mathbf {M} = \ Mathbf {U \ Sigma V^{*}} \}$ waarin ${\ DisplayStyle \ \ Mathbf {\ Sigma} \}$ is vierkant diagonaal van grootte ${\ displaystyle r \ maal r}$, waar ${\ displaystyle \ r \ leq \ min \ {m, n \} \}$ is de rang van M, en heeft alleen de niet-nul enkelvoudige waarden. In deze variant, U is een ${\ DisplayStyle M \ Times R}$ semi-unitaire matrix en ${\ DisplayStyle \ \ Mathbf {v} \}$ is een ${\ displaystyle n \ maal r}$ semi-unitaire matrix, zoals dat ${\ displaystyle \ \ mathbf {u^{*} u} = \ mathbf {v^{*} v} = \ mathbf {i} _ {r} \.}$

Wiskundige toepassingen van de SVD omvatten het berekenen van de pseudoinverse, matrixbenadering en het bepalen van de rang, bereik, en nulruimte van een matrix. De SVD is ook uiterst nuttig op alle wetenschapsgebieden, engineering, en statistieken, zoals signaalverwerking, minst vierkanten het passen van gegevens, en procescontrole.

Intuïtieve interpretaties

Geanimeerde illustratie van de SVD van een 2D, echt schuifmatrix M. Eerst zien we de schijf in blauw samen met de twee Canonieke eenheidsvectoren. We zien dan de acties van M, die de schijf vervormt tot een Ovaal. De SVD ontleedt M in drie eenvoudige transformaties: een eerste rotatie V^⁎, a het schalen ${\ DisplayStyle \ Mathbf {\ Sigma}}$ langs de coördinaatassen en een laatste rotatie U. De lengte σ₁ en σ₂ van de semi-assen van de ellips zijn de enkelvoudige waarden van M, namelijk Σ_1,1 en Σ_2,2.

Visualisatie van de matrixvermenigvuldiging in ontleding van enkelvoudige waarde

Rotatie, coördinatenschaling en reflectie

In het speciale geval wanneer M is een m × m echt vierkante matrix, de matrices U en V^⁎ kan worden gekozen om echt te zijn m × m Matrices ook. In dat geval is "eenheid" hetzelfde als "orthogonaal". Vervolgens, interpreteren van zowel eenheidsmatrices als de diagonale matrix, hier samengevat als als A, als een lineaire transformatie x ↦ Bijl van de ruimte R^m, de matrices U en V^⁎ staan ​​voor rotatie of reflectie van de ruimte, terwijl ${\ DisplayStyle \ Mathbf {\ Sigma}}$ vertegenwoordigt de het schalen van elke coördinaat x_i door de factor σ_i. Aldus breekt de SVD -ontleding elke lineaire transformatie van R^m in een samenstelling van drie geometrisch transformaties: een rotatie of reflectie (V^⁎), gevolgd door een coördinaat per coördinaat het schalen (${\ DisplayStyle \ Mathbf {\ Sigma}}$), gevolgd door een andere rotatie of reflectie (U).

In het bijzonder als M heeft dan een positieve bepalende factor U en V^⁎ kan worden gekozen om beide rotaties te zijn met reflecties of beide rotaties zonder reflecties. Als de determinant negatief is, heeft precies een van hen een reflectie. Als de determinant nul is, kan elk onafhankelijk worden gekozen als van beide type.

Als de matrix M is echt maar niet vierkant, namelijk m×n met m ≠ n, het kan worden geïnterpreteerd als een lineaire transformatie van Rⁿ tot R^m. Dan U en V^⁎ kan worden gekozen als rotaties/reflecties van R^m en Rⁿ, respectievelijk; en ${\ DisplayStyle \ Mathbf {\ Sigma}}$, naast het schalen van de eerste ${\ DisplayStyle \ Min \ {M, N \}}$ Coördinaten breiden de vector ook uit met nullen, d.w.z. verwijdert achterstandscoördinaten, om te draaien Rⁿ naar binnen R^m.

Enkelvoudige waarden als semiaxen van een ellips of ellipsoïde

Zoals getoond in de figuur, de enkelvoudige waarden kan worden geïnterpreteerd als de grootte van de semiaxen van een Ovaal in 2d. Dit concept kan worden gegeneraliseerd n-dimensionaal Euclidische ruimte, met de enkelvoudige waarden van elke n × n vierkante matrix worden gezien als de omvang van de semiaxis van een n-dimensionaal ellipsoïde. Evenzo zijn de enkelvoudige waarden van alle m × n matrix kan worden gezien als de grootte van de semiaxis van een n-dimensionaal ellipsoïde in m-Dimensionale ruimte, bijvoorbeeld als een ellips in een (gekanteld) 2D -vlak in een 3D -ruimte. Singulaire waarden coderen de grootte van de semiaxis, terwijl enkelvoudige vectoren coderen voor de richting. Zien onderstaand voor verdere details.

De kolommen van U en V zijn orthonormale bases

Sinds U en V^⁎ zijn unitair, de kolommen van elk van hen vormen een set van orthonormale vectoren, die kan worden beschouwd als Basisvectoren. De matrix M brengt de basisvector toe V_i naar de uitgerekte eenheidsvector σ_i U_i. Door de definitie van een eenheidsmatrix geldt hetzelfde voor hun geconjugeerde transposes U^⁎ en V, behalve de geometrische interpretatie van de enkelvoudige waarden als stukken verloren gaat. Kortom, de kolommen van U, U^⁎, V, en V^⁎ zijn orthonormale bases. Wanneer de ${\ DisplayStyle \ Mathbf {M}}$ is een positief-semidefiniet Hermitiaanse matrix, U en V zijn beide gelijk aan de unitaire matrix die wordt gebruikt om diagonalisering ${\ DisplayStyle \ Mathbf {M}}$. Wanneer echter ${\ DisplayStyle \ Mathbf {M}}$ is niet positief-semidefiniet en Hermitian maar toch diagonaliseerbaar, zijn eigendecompositie en enkele ontleding van de waarde zijn verschillend.

Geometrische betekenis

Omdat U en V zijn unitair, we weten dat de kolommen U₁, ..., U_m van U leveren een orthonormale basis van K^m en de kolommen V₁, ..., V_n van V een orthonormale basis opleveren van Kⁿ (met betrekking tot de standaard scalaire producten op deze ruimtes).

De lineaire transformatie

${\ displaystyle t \ colon \ links \ {{\ begin {aligned} k^{n} & \ to k^{m} \\ x & \ mapsto \ mathbf {m} x \ end {aligned}} \ rechts.}$

heeft een bijzonder eenvoudige beschrijving met betrekking tot deze orthonormale bases: we hebben

${\ displaystyle t (\ mathbf {v} _ {i}) = \ sigma _ {i} \ mathbf {u} _ {i}, \ qquad i = 1, \ ldots, \ min (m, n),},}$

waar σ_i is de i-th diagonale toegang van ${\ DisplayStyle \ Mathbf {\ Sigma}}$, en T(V_i) = 0 voor i > min (m,n).

De geometrische inhoud van de SVD -stelling kan dus als volgt worden samengevat: voor elke lineaire kaart T: Kⁿ → K^m men kan orthonormale bases van Kⁿ en K^m zoals dat T wijst de i-th Basis vector van Kⁿ naar een niet-negatief veelvoud van de i-th Basis vector van K^men stuurt de linksbasisvectoren naar nul. Met betrekking tot deze bases, de kaart T wordt daarom weergegeven door een diagonale matrix met niet-negatieve echte diagonale inzendingen.

Overweeg de bol om een ​​meer visuele smaak van enkelvoudige waarden en SVD -factorisatie te krijgen - althans bij het werken aan echte vectorruimtes - overweeg S van straal één in Rⁿ. De lineaire kaart T brengt deze bol toe aan een ellipsoïde in R^m. Niet-nul enkelvoudige waarden zijn gewoon de lengte van de semi-assen van deze ellipsoïde. Vooral wanneer n = m, en alle enkelvoudige waarden zijn verschillend en niet-nul, de SVD van de lineaire kaart T kan gemakkelijk worden geanalyseerd als een opeenvolging van drie opeenvolgende bewegingen: overweeg de ellipsoïde T(S) en specifiek zijn assen; Overweeg dan de aanwijzingen in Rⁿ verstuurd door T op deze assen. Deze aanwijzingen zijn toevallig wederzijds orthogonaal. Pas eerst een isometrie toe V^⁎ deze aanwijzingen naar de coördinaatassen van sturen Rⁿ. Breng bij een tweede stap een endomorfisme D Diagonaliseerd langs de coördinaatassen en strekken of krimpen in elke richting, met behulp van de semi-assen lengtes van T(S) als rekcoëfficiënten. De compositie D ∘ V^⁎ stuurt vervolgens de unit-sphere naar een ellipsoïde isometrisch naar T(S). Pas een isometrie toe om de derde en laatste stap te definiëren U aan deze ellipsoïde om te verkrijgen T(S). Zoals gemakkelijk kan worden gecontroleerd, de compositie U ∘ D ∘ V^⁎ valt samen met T.

Voorbeeld

Houd rekening met de 4 × 5 Matrix

${\ DisplayStyle \ Mathbf {m} = {\ begin {bMatrix} 1 & 0 & 0 & 0 & 2 \\ 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 AD$

Een enkele dekpositie van deze matrix wordt gegeven door Uσv^⁎

${\ displayStyle {\ begin {uitgelijnd} \ mathbf {u} & = {\ begin {bMatrix} \ color {green} 0 & \ color {blauw} -1 & \ color {cyan} 0 & \ color {emerald} 0 \\\ kleur {groen} -1 & \ color {blauw} 0 & \ color {cyan} 0 & \ color {Emerald} 0 \\\ color {green} 0 & \ color {blauw} 0 & \ color {cyan} 0 & \ color {Emerald}- 1 \\\ color {green} 0 & \ color {blauw} 0 & \ color {cyan} -1 & \ color {Emerald} 0 \ end {bMatrix}} \\ [6pt] {\ boldsymbol {\ sigma}} & = { \begin{bmatrix}3&0&0&0&\color {Gray}{\mathit {0}}\\0&{\sqrt {5}}&0&0&\color {Gray}{\mathit {0}}\\0&0&2&0&\color {Gray}{ \mathit {0}}\\0&0&0&\color {Red}\mathbf {0} &\color {Gray}{\mathit {0}}\end{bmatrix}}\\[6pt]\mathbf {V} ^{ *} & = {\ begin {bMatrix} \ color {violet} 0 & \ color {violet} 0 & \ color {violet} -1 & \ color {violet} 0 & \ color {violet} 0 \\ {plum}-{ \ sqrt {0.2}} & \ color {plum} 0 & \ color {plum} 0 & \ color {plum} 0 & \ color {plum}-{\ sqrt {0.8}}} \\ color {magenta} 0 & {magenta } -1 & \ color {magenta} 0 & \ color {magenta} 0 & \ color {magenta} 0 \\\ color {orchid} 0 & \ color {orchid} 0 & \ color {orchid} 0 & \ color {orchid} 1 & \ color { Orchid} 0 \\\ color {purple}-{\ Sqrt {0.8}} & \ Color {Purple} 0 & \ Color {Purple} 0 & \ Color {Purple} 0 & \ Color {Purple} {\ Sqrt {0.2}} \ End {BMatrix}} \ end}}}}}}}}}}}}}}}}}}}}$

De schaalmatrix ${\ DisplayStyle \ Mathbf {\ Sigma}}$ is nul buiten de diagonale (grijze cursief) en één diagonaal element is nul (rood vet). Bovendien, omdat de matrices U en V^⁎ zijn eenheid, vermenigvuldigen met hun respectieve conjugaat -transposeert identiteitsmatrices, zoals hieronder getoond. In dit geval, omdat U en V^⁎ worden echt gewaardeerd, elk is een orthogonale matrix.

${\ DisplayStyle {\ begin {uitgelijnd} \ mathbf {u} \ mathbf {u} ^{*} & = {\ begin {bMatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 AF {I} _{4}\\[6pt]\mathbf {V} \mathbf {V} ^{*}&={\begin{bmatrix}1&0&0&0&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\end{ bMatrix}} = \ mathbf {i} _ {5} \ end {uitgelijnd}}}$

Deze specifieke ontleding van enkele waarde is niet uniek. Kiezen ${\ DisplayStyle \ Mathbf {v}}$ zoals dat

${\ DisplayStyle \ Mathbf {v} ^{*} = {\ begin {bMatrix} \ color {violet} 0 & \ color {violet} 1 & \ color {violet} 0 & \ color {violet} 0 & \ color {violet \ 0 \ \\ color {plum} 0 & \ color {plum} 0 & \ color {plum} 1 & \ color {plum} 0 & \ color {plum} 0 \\\ color {magenta} {\ sqrt {0.2}} & \ color {magenta {magenta } 0 & \ color {magenta} 0 & \ color {magenta} 0 & \ color {magenta} {\ sqrt {0.8}} \\\ color {orchid} {\ sqrt {0.4}} & \ color {orchid} 0 & \ \ color {orchid} 0 & \ \ color {orchida Orchid} 0 & \ color {orchid} {\ sqrt {0.5}} & \ color {orchid}-{\ sqrt {0.1}}}} \\\ color {purple}-{\ sqrt {0.4}} & \ color {purple} 0 & \ color {purple} 0 & \ color {purple} {\ sqrt {0.5}} & \ color {purple} {\ sqrt {0.1}} \ end {bMatrix}}}$

is ook een geldige ontleding van enkelvoudige waarde.

SVD en spectrale ontleding

Enkelvoudige waarden, enkelvoudige vectoren en hun relatie tot de SVD

Een niet-negatief reëel aantal σ is een enkelvoudige waarde voor M Als en alleen als er een eenheidslengte vectoren bestaan ${\ DisplayStyle \ Mathbf {u}}$ in K^m en ${\ DisplayStyle \ Mathbf {v}}$ in Kⁿ zoals dat

${\ displayStyle \ Mathbf {mv} = \ sigma \ mathbf {u} \, {\ text {en}} \ mathbf {m} ^{*} \ mathbf {u} = \ sigma \ mathbf {v}.}.}.$

De vectoren ${\ DisplayStyle \ Mathbf {u}}$ en ${\ DisplayStyle \ Mathbf {v}}$ worden genoemd links-singulair en rechts-singulaire vectoren voor σ, respectievelijk.

In elke ontleding van een enkelvoudige waarde

${\ displaystyle \ mathbf {m} = \ mathbf {u} {\ boldsymbol {\ sigma}} \ mathbf {v} ^{*}}$

de diagonale inzendingen van ${\ DisplayStyle \ Mathbf {\ Sigma}}$ zijn gelijk aan de enkelvoudige waarden van M. De eerste p = min (m, n) kolommen van U en V zijn respectievelijk linker- en rechter-singulaire vectoren voor de overeenkomstige enkelvoudige waarden. Bijgevolg impliceert de bovenstaande stelling dat:

• Een m × n Matrix M heeft maximaal p verschillende enkelvoudige waarden.
• Het is altijd mogelijk om een eenheidsbasis U voor K^m met een subset van basisvectoren die de links-singulaire vectoren van elke enkelvoudige waarde van overspannen M.
• Het is altijd mogelijk om een ​​eenheidsbasis te vinden V voor Kⁿ met een subset van basisvectoren die de rechter-singulaire vectoren van elke enkelvoudige waarde van overspannen M.

Een enkelvoudige waarde waarvoor we twee linkse vectoren links (of rechts) kunnen vinden die lineair onafhankelijk zijn, wordt genoemd ontaarden. Als ${\ DisplayStyle \ Mathbf {u} _ {1}}$ en ${\ DisplayStyle \ Mathbf {u} _ {2}}$ zijn twee links-singulaire vectoren die beide overeenkomen met de enkelvoudige waarde σ, dan is elke genormaliseerde lineaire combinatie van de twee vectoren ook een links-singulaire vector die overeenkomt met de enkelvoudige waarde σ. De vergelijkbare verklaring geldt voor rechts-singulaire vectoren. Het aantal onafhankelijke linker- en rechter-singulaire vectoren valt samen en deze enkelvoudige vectoren verschijnen in dezelfde kolommen van U en V overeenkomend met diagonale elementen van ${\ DisplayStyle \ Mathbf {\ Sigma}}$ allemaal met dezelfde waarde σ.

Als uitzondering omvatten de linker- en rechter-singulaire vectoren van enkelvoudige waarde 0 alle eenheidsvectoren in de kernel en Cokernel, respectievelijk van M, die door de Rank -nullity stelling kan niet dezelfde dimensie zijn als m ≠ n. Zelfs als alle enkelvoudige waarden niet nul zijn, als m > n dan is de cokernel niet -triviaal, in welk geval U is opgevuld met m − n Orthogonale vectoren van de Cokernel. Omgekeerd, als m < n, dan V wordt opgevuld door n − m Orthogonale vectoren van de kernel. Als de enkelvoudige waarde van 0 echter bestaat, zijn de extra kolommen van U of V verschijnt al als links of rechter-singulaire vectoren.

Niet-gedegenereerde enkelvoudige waarden hebben altijd unieke linker- en rechter-singulaire vectoren, tot vermenigvuldiging door een eenheidsfase-factor e^iφ (voor het echte geval tot een teken). Bijgevolg, als alle enkelvoudige waarden van een vierkante matrix M zijn niet-gedegenereerde en niet-nul, dan is de ontleding van de enkelvoudige waarde uniek, tot vermenigvuldiging van een kolom van U door een eenheidsfase-factor en gelijktijdige vermenigvuldiging van de overeenkomstige kolom van V door dezelfde eenheidsfase-factor. Over het algemeen is de SVD uniek tot willekeurige eenheidstransformaties die uniform worden toegepast op de kolomvectoren van beide U en V overspant de subruimten van elke enkelvoudige waarde, en tot willekeurige unitaire transformaties op vectoren van U en V respectievelijk de kernel en cokernel overspannen van M.

Relatie met de ontleding van eigenwaarde

De ontleding van de enkelvoudige waarde is zeer algemeen in de zin dat deze op elke zin kan worden toegepast m × n matrix, terwijl eigenwaarde ontleding kan alleen worden toegepast op diagonaliseerbare matrices. Desondanks zijn de twee ontledingen gerelateerd.

Gegeven een SVD van M, zoals hierboven beschreven, zijn de volgende twee relaties gelden:

${\ displayStyle {\ begin {uitgelijnd} \ mathbf {m} ^{*} \ mathbf {m} & = \ mathbf {v} {\ boldsymbol {\ sigma}} ^{*} \ mathbf {u} ^{** } \, \ mathbf {u} {\ boldsymbol {\ sigma}} \ mathbf {v} ^{*} = \ mathbf {v} ({\ boldsymbol {\ sigma}} ^{*} {\ \ \ \ \ \ \ \ \ \ \ \ boldsymbole }})\mathbf {V} ^{*}\\\mathbf {M} \mathbf {M} ^{*}&=\mathbf {U} {\boldsymbol {\Sigma }}\mathbf {V} ^{ *} \, \ mathbf {v} {\ boldsymbol {\ sigma}} ^{*} \ mathbf {u} ^{*} = \ mathbf {u} ({\ boldsymbol {\ sigma}} {\ boldsymbol {\ \ boldsymbolbol { Sigma}} ^{*}) \ Mathbf {u} ^{*} \ end {uitgelijnd}}}$

De rechterkant van deze relaties beschrijven de ontledingen van de eigenwaarde van de linkerkant. Vervolgens:

• De kolommen van V (rechts-singulaire vectoren) zijn eigenvectoren van M^⁎M.
• De kolommen van U (links-singulaire vectoren) zijn eigenvectoren van Mm^⁎.
• De niet-nul elementen van ${\ DisplayStyle \ Mathbf {\ Sigma}}$ (niet-nul enkelvoudige waarden) zijn de vierkante wortels van de niet-nul eigenwaarden van M^⁎M of Mm^⁎.

In het speciale geval dat M is een normale matrix, die per definitie vierkant moet zijn, de spectrale stelling zegt dat het kan eenheid diagonaliseerd een basis gebruiken van eigenvectoren, zodat het kan worden geschreven M = Udu^⁎ voor een eenheidsmatrix U en een diagonale matrix D met complexe elementen σ_i langs de diagonaal. Wanneer M is Positief semi-definitief, σ_i zal niet-negatieve reële getallen zijn, zodat de ontleding M = Udu^⁎ is ook een ontleding van enkele waarde. Anders kan het worden herschikt als een SVD door de fase te verplaatsen e^iφ van elke σ_i tot zijn overeenkomstige V_i of U_i. De natuurlijke verbinding van de SVD met niet-normale matrices is via de polaire ontleding stelling: M = SR, waar S = Uσu^⁎ is positief semidefiniet en normaal, en R = UV^⁎ is eenheid.

Dus, behalve voor positieve semi-definitieve matrices, de eigenwaarde-ontleding en SVD van M, terwijl gerelateerd, verschillen: de ontleding van eigenwaarde is M = Udu⁻¹, waar U is niet noodzakelijk eenheid en D is niet noodzakelijkerwijs positief semi-definitief, terwijl de SVD dat is M = Uσv^⁎, waar ${\ DisplayStyle \ Mathbf {\ Sigma}}$ is diagonaal en positief semi-definitief, en U en V zijn eenheidsmatrices die niet noodzakelijkerwijs gerelateerd zijn, behalve via de matrix M. Terwijl alleen niet-defectief vierkante matrices hebben een eigenwaarde -ontleding, elke ${\ displaystyle m \ maal n}$ Matrix heeft een SVD.

Toepassingen van de SVD

Pseudoinverse

De ontleding van de enkelvoudige waarde kan worden gebruikt voor het berekenen van de pseudoinverse van een matrix. (Verschillende auteurs gebruiken verschillende notatie voor de pseudoinverse; hier gebruiken we ^†.) Inderdaad, de pseudoinverse van de matrix M met een ontleding van een enkelvoudige waarde M = Uσv^⁎ is

M^† = V Σ^† U^⁎

waar Σ^† is de pseudoinverse van Σ, die wordt gevormd door elke niet-nul diagonale invoer te vervangen door zijn wederkerig en het omzetten van de resulterende matrix. De pseudoinverse is een manier om op te lossen Lineaire kleinste vierkanten problemen.

Homogene lineaire vergelijkingen oplossen

Een set van Homogene lineaire vergelijkingen kan worden geschreven als Bijl = 0 voor een matrix A en vector x. Een typische situatie is dat A is bekend en een niet-nul x moet worden bepaald die voldoet aan de vergelijking. Zo'n x hoort bij A's nulruimte en wordt soms een (rechter) nulvector van genoemd A. De vector x kan worden gekenmerkt als een rechter-singulaire vector die overeenkomt met een enkelvoudige waarde van A dat is nul. Deze observatie betekent dat als A is een vierkante matrix en heeft geen enkele enkelvoudige waarde, de vergelijking heeft geen niet-nul x als een oplossing. Het betekent ook dat als er verschillende verdwijnende enkelvoudige waarden zijn, elke lineaire combinatie van de bijbehorende rechter-singulaire vectoren een geldige oplossing is. Analoog aan de definitie van een (rechter) nulvector, een niet-nul x bevredigend x^⁎A = 0, met x^⁎ het aangeven van het geconjugeerde transponeren van xwordt een linker nul vector van genoemd A.

Totaal minimalisatie van de kleinste kwadraten

A Totaal kleinste vierkanten Probleem zoekt de vector x die de 2-norm van een vector Bijl onder de beperking ||x|| = 1. De oplossing blijkt de rechtermantelige vector van te zijn A overeenkomend met de kleinste enkelvoudige waarde.

Bereik, nulruimte en rang

Een andere toepassing van de SVD is dat deze een expliciete weergave van de bereik en nulruimte van een matrix M. De rechter-singulaire vectoren die overeenkomen met het verdwijnen van enkelvoudige waarden van M overspannen de nulruimte van M en de links-singulaire vectoren die overeenkomen met de niet-nul enkelvoudige waarden van M overspannen het bereik van M. Bijvoorbeeld in het bovenstaande voorbeeld De nulruimte wordt overgebracht door de laatste twee rijen van V^⁎ en het bereik wordt overgebracht door de eerste drie kolommen van U.

Als gevolg hiervan, de rang van M is gelijk aan het aantal niet-nul enkelvoudige waarden dat hetzelfde is als het aantal niet-nul diagonale elementen ${\ DisplayStyle \ Mathbf {\ Sigma}}$. In numerieke lineaire algebra kunnen de enkelvoudige waarden worden gebruikt om de effectieve rang van een matrix, zoals Afrondingsfout Kan leiden tot kleine maar niet-nul enkelvoudige waarden in een rangdeficiënte matrix. Enkele waarden die verder gaan dan een significante opening wordt verondersteld numeriek equivalent te zijn aan nul.

Lage matrixbenadering

Sommige praktische toepassingen moeten het probleem oplossen benadering een matrix M met een andere matrix ${\ DisplayStyle {\ tilde {\ Mathbf {m}}}}$, Gezegd te zijn afgekapt, die een specifieke rang heeft r. In het geval dat de benadering is gebaseerd op het minimaliseren van de Frobenius Norm van het verschil tussen M en ${\ DisplayStyle {\ tilde {\ Mathbf {m}}}}$ onder de beperking dat ${\ DisplayStyle \ OperatorName {rank} \ left ({\ tilde {\ mathbf {m}}} \ rechts) = r}$, het blijkt dat de oplossing wordt gegeven door de SVD van M, namelijk

${\ displayStyle {\ tilde {\ mathbf {m}}} = \ mathbf {u} {\ tilde {\ boldsymbol {\ sigma}}} \ mathbf {v} ^{*},},},},},},},},},},},},},},}$

waar ${\ DisplayStyle {\ tilde {\ boldsymbol {\ sigma}}}}$ is dezelfde matrix als ${\ DisplayStyle \ Mathbf {\ Sigma}}$ behalve dat het alleen de r Grootste enkelvoudige waarden (de andere enkelvoudige waarden worden vervangen door nul). Dit staat bekend als de Eckart - Young Stelling, zoals het werd bewezen door die twee auteurs in 1936 (hoewel het later bekend was geweest bij eerdere auteurs; zie Stewart 1993).

Scheidbare modellen

De SVD kan worden beschouwd als het ontbinden van een matrix in een gewogen, geordende som van scheidbare matrices. Met scheidbaar bedoelen we dat een matrix A kan worden geschreven als een buitenste product van twee vectoren A = u ⊗ v, of, in coördinaten, ${\ displaystyle a_ {ij} = u_ {i} v_ {j}}$. In het bijzonder de matrix M kan worden afgebroken als

${\ displayStyle \ Mathbf {m} = \ sum _ {i} \ Mathbf {a} _ {i} = \ sum _ {i} \ sigma _ {i} \ mathbf {u} _ {i} \ otimes \ otimes \ otimes \ otimes {V} _ {i}.}$

Hier U_i en V_i zijn de i-th kolommen van de overeenkomstige SVD -matrices, σ_i zijn de geordende enkelvoudige waarden, en elk A_i is scheidbaar. De SVD kan worden gebruikt om de ontleding van een beeldverwerkingsfilter te vinden in scheidbare horizontale en verticale filters. Merk op dat het aantal niet-nul σ_i is precies de rang van de matrix.

Scheidbare modellen ontstaan ​​vaak in biologische systemen en de SVD -factorisatie is nuttig om dergelijke systemen te analyseren. Sommige visuele velden V1 eenvoudige cellen kunnen bijvoorbeeld goed worden beschreven^[1] door een Gabor -filter In het ruimtedomein vermenigvuldigd met een modulatiefunctie in het tijdsdomein. Aldus, gegeven een lineair filter geëvalueerd door bijvoorbeeld bijvoorbeeld, omgekeerde correlatie, men kan de twee ruimtelijke afmetingen herschikken in een dimensie, waardoor een tweedimensionaal filter (ruimte, tijd) kan worden opgeleverd die kan worden ontleed via SVD. De eerste kolom van U In de SVD -factorisatie is dan een Gabor terwijl de eerste kolom van V vertegenwoordigt de tijdmodulatie (of vice versa). Men kan dan een index van scheidbaarheid definiëren

${\ displayStyle \ alpha = {\ frac {\ sigma _ {1}^{2}} {\ sum _ {i} \ sigma _ {i}^{2}}},}$

dat is de fractie van het vermogen in de matrix M die wordt verklaard door de eerste scheidbare matrix in de ontleding.^[2]

Dichtstbijzijnde orthogonale matrix

Het is mogelijk om de SVD van een vierkante matrix te gebruiken A het bepalen van orthogonale matrix O dichtst bij A. De nabijheid van fit wordt gemeten door de Frobenius Norm van O − A. De oplossing is het product UV^⁎.^[3] Dit is intuïtief logisch omdat een orthogonale matrix de ontleding zou hebben UIV^⁎ waar I is de identiteitsmatrix, dus dat als A = Uσv^⁎ Dan het product A = UV^⁎ komt neer op het vervangen van de enkelvoudige waarden door die. Gelijkwaardig, de oplossing is de unitaire matrix R = UV^⁎ van de polaire ontleding M = RP = P'R in beide volgorde van stretch en rotatie, zoals hierboven beschreven.

Een soortgelijk probleem, met interessante toepassingen in vormanalyse, is de Orthogonaal Procrustes -probleem, die bestaat uit het vinden van een orthogonale matrix O die het dichtst in kaart brengen A tot B. Specifiek,

${\ DisplayStyle \ Mathbf {O} = {\ Underset {\ OMEGA} {\ OperatorName {Argmin}}}}} \ | \ Mathbf {A} {\ Boldsymbol {\ OMEGA}}-\ MATHBF {B} \ | _ {f } \ quad {\ text {onderworpen aan}} \ quad {\ boldsymbol {\ oMega}}^{\ textsf {t}} {\ boldsymbol {\ omega}} = \ mathbf},},},},},},},},},},}$

waar ${\ DisplayStyle \ | \ CDOT \ | _ {f}}$ geeft de Frobenius -norm aan.

Dit probleem is gelijk aan het vinden van de dichtstbijzijnde orthogonale matrix voor een bepaalde matrix M = A^TB.

Het KABSCH -algoritme

De Kabsch -algoritme (genaamd Wahba's probleem in andere velden) gebruikt SVD om de optimale rotatie te berekenen (met betrekking tot de minimalisatie van de minste kwadraten) die een reeks punten uitlijnt met een overeenkomstige set punten. Het wordt onder andere gebruikt om de structuren van moleculen te vergelijken.

Signaalverwerking

De SVD en Pseudoinverse zijn met succes toegepast op signaalverwerking,^[4] afbeelding verwerken en Big Data (bijv. In genomische signaalverwerking).^[5][6][7][8]

Andere voorbeelden

De SVD wordt ook uitgebreid toegepast op de studie van lineair omgekeerde problemen en is nuttig bij de analyse van regularisatiemethoden zoals die van Tikhonov. Het wordt veel gebruikt in statistieken, waar het verband houdt Hoofdcomponentanalyse en naar Correspondentieanalyse, en in signaalverwerking en patroonherkenning. Het wordt ook gebruikt in alleen-uitvoer modale analyse, waar de niet-geschalen modus vormt kan worden bepaald uit de enkelvoudige vectoren. Nog een ander gebruik is latente semantische indexering bij tekstverwerking van natuurlijke taal.

Over het algemeen is er numerieke berekening met lineaire of gelineariseerde systemen, er is een universele constante die de regelmaat of singulariteit van een probleem kenmerkt, het "conditienummer" van het systeem is ${\ displaystyle \ kappa: = \ sigma _ {\ text {max}}/\ sigma _ {\ text {min}}}$. Het regelt vaak het foutenpercentage of convergentiepercentage van een bepaald computationele schema op dergelijke systemen.^[9][10]

De SVD speelt ook een cruciale rol op het gebied van kwantuminformatie, in een vorm die vaak wordt genoemd als de Schmidt -ontleding. Hierdoor worden toestanden van twee kwantumsystemen van nature ontleed, waardoor ze een noodzakelijke en voldoende voorwaarde bieden om te zijn verstrikt: als de rang van de ${\ DisplayStyle \ Mathbf {\ Sigma}}$ Matrix is ​​groter dan één.

Eén toepassing van SVD op vrij grote matrices is in Numerieke weersvoorspelling, waar Lanczos -methoden worden gebruikt om de meest lineair snel groeiende weinig verstoringen te schatten tot de centrale numerieke weersvoorspelling gedurende een bepaalde initiële voorwaartse tijdsperiode; d.w.z. de enkelvoudige vectoren die overeenkomen met de grootste enkelvoudige waarden van de gelineariseerde propagator voor het globale weer gedurende die tijdsinterval. De output enkelvoudige vectoren in dit geval zijn hele weersystemen. Deze verstoringen worden vervolgens door het volledige niet -lineaire model geleid om een ensemble -voorspelling, het geven van grip op een deel van de onzekerheid die moet worden toegestaan ​​rond de huidige centrale voorspelling.

SVD is ook toegepast op verminderde ordermodellering. Het doel van verminderde ordermodellering is om het aantal vrijheidsgraden te verminderen in een complex systeem dat moet worden gemodelleerd. SVD was gekoppeld aan Radiale basisfuncties om oplossingen te interpoleren op driedimensionale onstabiele stromingsproblemen.^[11]

Interessant is dat SVD is gebruikt om zwaartekrachtgolfvormmodellering te verbeteren door de op de grond gebaseerde zwaartekrachtinterferometer Aligo.^[12] SVD kan helpen om de nauwkeurigheid en snelheid van golfvormgeneratie te vergroten ter ondersteuning van zoekopdrachten van zwaartekrachtgolven en het bijwerken van twee verschillende golfvormmodellen.

Enkelvoudige waarde ontleding wordt gebruikt in Aanbevelingssystemen Om de itembeoordelingen van mensen te voorspellen.^[13] Gedistribueerde algoritmen zijn ontwikkeld om de SVD op clusters van grondstoffenmachines te berekenen.^[14]

SVD met een lage rang is toegepast voor hotspot-detectie van ruimtelijke gegevens met toepassing op ziekte uitbraak detectie.^[15] Een combinatie van SVD en SVD van hogere orde is ook toegepast voor realtime gebeurtenisdetectie van complexe gegevensstromen (multivariate gegevens met ruimte- en tijdafmetingen) in Ziektebewaking.^[16]

Bestaande bewijzen

Een eigenwaarde λ van een matrix M wordt gekenmerkt door de algebraïsche relatie Mu = λu. Wanneer M is Hermitiaans, er is ook een variatiekarakterisering beschikbaar. Laten M wees echt n × n symmetrische matrix. Definiëren

${\ displayStyle {\ begin {cases} f: \ mathbb {r} ^{n} \ to \ mathbb {r} \\ f: \ mathbf {x} \ mapsto \ mathbf {x} ^{\ textsf {t} } \ mathbf {m} \ mathbf {x} \ end {cases}}}$

Door de extreme waarde stelling, deze continue functie bereikt bij sommigen een maximum u Wanneer beperkt tot de eenheidsfeer {||x|| = 1}. Door de Lagrange -vermenigvuldigers stelling, u Noodzakelijk voldoet

${\ displaystyle \ nabla \ mathbf {u} ^{\ textsf {t}} \ mathbf {m} \ mathbf {u} -\ lambda \ cdot \ nabla \ mathbf {u} ^\ \ {\ tekst {u} = 0}$

Voor een reëel nummer λ. Het Nabla -symbool, ∇, is de del operator (differentiatie met betrekking tot x). Met behulp van de symmetrie van M we verkrijgen

${\ displaystyle \ nabla \ mathbf {x} ^{\ textsf {t}} \ mathbf {m} \ mathbf {x} -\ lambda \ cdot \ nabla \ mathbf {x} ^\ \ {t}}}}}}}}}}}} \ mathbf {x} = 2 (\ mathbf {m} -\ lambda \ mathbf {i}) \ mathbf {x}.}$

Daarom Mu = λu, dus u is een eenheid lengte eigenvector van M. Voor elke eigenheid van eenheidslengte v van M zijn eigenwaarde is f(v), dus λ is de grootste eigenwaarde van M. Dezelfde berekening uitgevoerd op de orthogonale aanvulling van u Geeft de volgende grootste eigenwaarde enzovoort. De complexe Hermitiaanse zaak is vergelijkbaar; daar f(x) = x* M x is een echt gewaardeerde functie van 2n Echte variabelen.

Enkelvoudige waarden zijn vergelijkbaar omdat ze algebraïsch kunnen worden beschreven of uit variatieprincipes. Hoewel, in tegenstelling tot de eigenwaarde, hermiticiteit of symmetrie, van M is niet langer vereist.

Deze sectie geeft deze twee argumenten voor het bestaan ​​van ontleding van een enkelvoudige waarde.

Gebaseerd op de spectrale stelling

Laten ${\ DisplayStyle \ Mathbf {M}}$ Boon m × n Complexe matrix. Sinds ${\ DisplayStyle \ Mathbf {M} ^{*} \ Mathbf {M}}$ is positief semi-definitief en Hermitian, door de spectrale stelling, er bestaat een n × n eenheidsmatrix ${\ DisplayStyle \ Mathbf {v}}$ zoals dat

${\ DisplayStyle \ Mathbf {v} ^{*} \ Mathbf {m} ^{*} \ Mathbf {m} \ Mathbf {v} = {\ bar {\ Mathbf {d}} = {\ start} \ mathbf {d} & 0 \\ 0 & 0 \ end {bMatrix}},}$

waar ${\ DisplayStyle \ Mathbf {d}}$ is diagonaal en positief definitief, van dimensie ${\ DisplayStyle \ ell \ Times \ ell}$, met ${\ DisplayStyle \ ell}$ het aantal niet-nul eigenwaarden van ${\ DisplayStyle \ Mathbf {M} ^{*} \ Mathbf {M}}$ (waarvan kan worden aangetoond dat het verifieert ${\ DisplayStyle \ ell \ leq \ min (n, m)}$). Let daar op ${\ DisplayStyle \ Mathbf {v}}$ is hier per definitie een matrix wiens ${\ displaystyle i}$-de kolom is de ${\ displaystyle i}$-de eigenvector van ${\ DisplayStyle \ Mathbf {M} ^{*} \ Mathbf {M}}$, overeenkomend met de eigenwaarde ${\ displaystyle {\ bar {\ mathbf {d}}} _ {ii}}$. Bovendien, de ${\ displaystyle j}$-de kolom van ${\ DisplayStyle \ Mathbf {v}}$, voor ${\ DisplayStyle J> \ ell}$is een eigenvector van ${\ DisplayStyle \ Mathbf {M} ^{*} \ Mathbf {M}}$ met eigenwaarde ${\ displaystyle {\ bar {\ mathbf {d}}} _ {jj} = 0}$. Dit kan worden uitgedrukt door te schrijven ${\ DisplayStyle \ Mathbf {v}}$ net zo ${\ DisplayStyle \ Mathbf {v} = {\ begin {BMatrix} \ Mathbf {v} _ {1} & \ Mathbf {v} _ {2} \ end {bMatrix}}}$, waar de kolommen van ${\ DisplayStyle \ Mathbf {v} _ {1}}$ en ${\ DisplayStyle \ Mathbf {v} _ {2}}$ Daarom bevatten de eigenvectoren van ${\ DisplayStyle \ Mathbf {M} ^{*} \ Mathbf {M}}$ overeenkomend met respectievelijk niet-nul en nul eigenwaarden. Met behulp van dit herschrijven van ${\ DisplayStyle \ Mathbf {v}}$, de vergelijking wordt:

${\displaystyle {\begin{bmatrix}\mathbf {V} _{1}^{*}\\\mathbf {V} _{2}^{*}\end{bmatrix}}\mathbf {M} ^{ *} \ mathbf {m} {\ begin {bMatrix} \ mathbf {v} _ {1} & \ mathbf {v} _ {2} \ end {bMatrix}} = {\ begin {bMatrix} \ mathbf {v} _ {1}^{*} \ Mathbf {m}^{*} \ Mathbf {m} \ Mathbf {v} _ {1} & \ Mathbf {v} _ {1}^{*} \ Mathbf {m} ^{*} \ mathbf {m} \ mathbf {v} _ {2} \\\ mathbf {v} _ {2} ^{*} \ mathbf {m} ^{*} \ mathbf {m} \ mathbf { V} _ {1} & \ mathbf {v} _ {2} ^{*} \ mathbf {m} ^{*} \ mathbf {m} \ mathbf {v} _ {2} \ end {bMatrix}} = {\ begin {bMatrix} \ Mathbf {d} & 0 \\ 0 & 0 \ end {bMatrix}}.}$

Dit betekent dat

${\ displayStyle \ Mathbf {v} _ {1} ^{*} \ Mathbf {m} ^{*} \ Mathbf {m} \ Mathbf {v} _ {1} = \ Mathbf {d}, \ quadbf \ quadbf \ quadbf \ quadbf \ quadbf \ quadbf \ quadbf \ quadbf \ quadbf \ quadbf {V} _ {2} ^{*} \ Mathbf {m} ^{*} \ Mathbf {m} \ Mathbf {v} _ {1} = \ Mathbf {0}.}$

Bovendien houdt de tweede vergelijking in ${\ DisplayStyle \ Mathbf {M} \ Mathbf {v} _ {2} = \ Mathbf {0}}$.^[17] Ten slotte de eenheid van ${\ DisplayStyle \ Mathbf {v}}$ vertaalt, in termen van ${\ DisplayStyle \ Mathbf {v} _ {1}}$ en ${\ DisplayStyle \ Mathbf {v} _ {2}}$, in de volgende voorwaarden:

${\ displayStyle {\ begin {uitgelijnd} \ mathbf {v} _ {1}^{*} \ mathbf {v} _ {1} & = \ mathbf {i} _ {1}, \\\ mathbf {v} _ {2}^{*} \ Mathbf {v} _ {2} & = \ Mathbf {i} _ {2}, \\\ Mathbf {v} _ {1} \ Mathbf {v} _ {1}^ {*}+\ mathbf {v} _ {2} \ mathbf {v} _ {2}^{*} & = \ mathbf {i} _ {12}, \ end {uitlijnd}}}$

waarbij de subscripts op de identiteitsmatrices worden gebruikt om op te merken dat ze van verschillende dimensies zijn.

Laten we nu definiëren

${\ displaystyle \ mathbf {u} _ {1} = \ mathbf {m} \ mathbf {v} _ {1} \ mathbf {d} ^{-{\ frac {1} {2}}}.}.}.}.}.}.$

Dan,

${\ displayStyle \ Mathbf {u} _ {1} \ Mathbf {d} ^{\ frac {1} {2}} \ Mathbf {v} _ {1} ^{*} = \ mathbf {m} \ mathbf {m} \ mathbf {m} \ mathbf {m} \ mathbf {m} au V} _ {1} \ Mathbf {d} ^{-{\ frac {1} {2}}} \ mathbf {d} ^{\ frac {1} {2}} \ Mathbf {v} _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ {1} ^{*} = \ mathbf {m} (\ mathbf {i} -\ mathbf {v} _ {2} \ mathbf {v} _ {2}^{*}) = \ mathbf {m} -(\ mathbffff} -(\ mathbff {M} \ mathbf {v} _ {2}) \ mathbf {v} _ {2}^{*} = \ mathbf {m},}$

sinds ${\ DisplayStyle \ Mathbf {M} \ Mathbf {v} _ {2} = \ Mathbf {0}.}$ Dit kan ook worden gezien als onmiddellijk gevolg van het feit dat ${\ DisplayStyle \ Mathbf {M} \ Mathbf {v} _ {1} \ Mathbf {v} _ {1}^{*} = \ Mathbf {m}}$. Dit is gelijk aan de waarneming dat als ${\ displayStyle \ {{\ boldsymbol {v}} _ {i} \} _ {i = 1}^{\ ell}}$ is de set van eigenvectoren van ${\ DisplayStyle \ Mathbf {M} ^{*} \ Mathbf {M}}$ overeenkomend met niet-vuizige eigenwaarden ${\ displaystyle \ {\ lambda _ {i} \} _ {i = 1}^{\ ell}}$, dan ${\ displaystyle \ {\ mathbf {m} {\ boldsymbol {v}} _ {i} \} _ {i = 1}^{\ ell}}$ is een set orthogonale vectoren, en ${\displaystyle \{\lambda _{i}^{-1/2}\mathbf {M} {\boldsymbol {v}}_{i}\}_{i=1}^{\ell }}$ is een (over het algemeen niet complete) set van ortonormaal vectoren. Dit komt overeen met het hierboven gebruikte matrixformalisme ${\ DisplayStyle \ Mathbf {v} _ {1}}$ de matrix waarvan de kolommen zijn ${\ displayStyle \ {{\ boldsymbol {v}} _ {i} \} _ {i = 1}^{\ ell}}$, met ${\ DisplayStyle \ Mathbf {v} _ {2}}$ de matrix waarvan de kolommen de eigenvectoren van zijn ${\ DisplayStyle \ Mathbf {M} ^{*} \ Mathbf {M}}$ met verdwijnende eigenwaarde, en ${\ DisplayStyle \ Mathbf {u} _ {1}}$ de matrix waarvan de kolommen de vectoren zijn ${\displaystyle \{\lambda _{i}^{-1/2}\mathbf {M} {\boldsymbol {v}}_{i}\}_{i=1}^{\ell }}$.

We zien dat dit bijna het gewenste resultaat is, behalve dat ${\ DisplayStyle \ Mathbf {u} _ {1}}$ en ${\ DisplayStyle \ Mathbf {v} _ {1}}$ zijn in het algemeen niet eenheid, omdat ze misschien niet vierkant zijn. We weten echter wel dat het aantal rijen van ${\ DisplayStyle \ Mathbf {u} _ {1}}$ is niet kleiner dan het aantal kolommen, omdat de afmetingen van ${\ DisplayStyle \ Mathbf {d}}$ is niet groter dan ${\ displaystyle m}$ en ${\ displaystyle n}$. Ook sinds

${\ displaystyle \ mathbf {u} _ {1} ^{*} \ mathbf {u} _ {1} = \ mathbf {d} ^{-{\ frac {1}}}}}} \ mathbf {v} _ {1} ^{*} \ Mathbf {m} ^{*} \ Mathbf {m} \ Mathbf {v} _ {1} \ Mathbf {d} ^{-{\ frac {1}}}}} = \ mathbf {d} ^{-{\ frac {1} {2}}} \ mathbf {d} \ mathbf {d} ^{-{\ frac {1} {2}}} = \ mathbf {i_ {i_ {i_ {i_ {i_ {i_ {i_ {i_ {I_ 1}},}$

de kolommen erin ${\ DisplayStyle \ Mathbf {u} _ {1}}$ zijn orthonormaal en kunnen worden uitgebreid tot een orthonormale basis. Dit betekent dat we kunnen kiezen ${\ DisplayStyle \ Mathbf {u} _ {2}}$ zoals dat ${\ DisplayStyle \ Mathbf {u} = {\ begin {BMatrix} \ Mathbf {u} _ {1} & \ Mathbf {u} _ {2} \ end {bMatrix}}}$ is eenheid.

Voor V₁ we hebben al V₂ om het eenheid te maken. Definieer nu

${\ DisplayStyle {\ boldsymbol {\ sigma}} = {\ begin {bMatrix} {\ begin {bMatrix} \ mathbf {d} ^{\ frac {1} {2}} & 0 \ \} & 0 \ \ \ eind \\ 0 \ end {bMatrix}},}$

waar extra nulrijen worden toegevoegd of verwijderd Om het aantal nulrijen te maken gelijk aan het aantal kolommen van U₂en dus de algehele dimensies van ${\ DisplayStyle {\ boldsymbol {\ sigma}}}$ gelijk aan ${\ displaystyle m \ maal n}$. Dan

${\displaystyle {\begin{bmatrix}\mathbf {U} _{1}&\mathbf {U} _{2}\end{bmatrix}}{\begin{bmatrix}{\begin{bmatrix}\mathbf {} D^{\ frac {1} {2}} & 0 \\ 0 & 0 \ end {bMatrix}} \\ 0 \ end {bMatrix}} {\ begin {bMatrix} \ mathbf {v} _ {1} & \ mathbf {1} & \ mathbf { V} _{2}\end{bmatrix}}^{*}={\begin{bmatrix}\mathbf {U} _{1}&\mathbf {U} _{2}\end{bmatrix}}{\ begin {bMatrix} \ mathbf {d} ^{\ frac {1} {2}} \ mathbf {v} _ {1} ^{*} \\ 0 \ end {bMatrix}} = \ mathbf {u} _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ {u 1} \ mathbf {d} ^{\ frac {1} {2}} \ mathbf {v} _ {1} ^{*} = \ mathbf {m},}$

wat het gewenste resultaat is:

${\ displaystyle \ mathbf {m} = \ mathbf {u} {\ boldsymbol {\ sigma}} \ mathbf {v} ^{*}.}$

Merk op dat het argument kan beginnen met diagonalisering Mm^⁎ liever dan M^⁎M (Dit laat dat direct zien Mm^⁎ en M^⁎M hebben dezelfde niet-nul eigenwaarden).

Gebaseerd op variatiekarakterisering

De enkelvoudige waarden kunnen ook worden gekenmerkt als de maxima van u^TMV, beschouwd als een functie van u en v, over bepaalde subruimten. De enkelvoudige vectoren zijn de waarden van u en v waar deze maxima worden bereikt.

Laten M duiden een m × n Matrix met echte inzendingen. Laten S^k−1 Wees de eenheid ${\ displaystyle (k-1)}$-Sphere in ${\ DisplayStyle \ Mathbb {r} ^{k}}$en definiëren ${\ displaystyle \ sigma (\ mathbf {u}, \ mathbf {v}) = \ mathbf {u} ^{\ textsf {t}} \ mathbf {m} \ mathbf {v}, \ \ mathbf In S^{M-1}, \ Mathbf {v} \ in S^{n-1}.}$

Overweeg de functie σ beperkt tot S^m−1 × Sⁿ⁻¹. Sinds beide S^m−1 en Sⁿ⁻¹ zijn compact Sets, hun Product is ook compact. Bovendien, sindsdien σ is continu, het bereikt een grootste waarde voor ten minste één paar vectoren u ∈ S^m−1 en v ∈ Sⁿ⁻¹. Deze grootste waarde wordt aangegeven σ₁ en de bijbehorende vectoren worden aangegeven u₁ en v₁. Sinds σ₁ is de grootste waarde van σ(u, v) het moet niet-negatief zijn. Als het negatief was, verandert het teken van een van beide u₁ of v₁ zou het positief en daarom groter maken.

Uitspraak. u₁, v₁ zijn links- en rechter-singulaire vectoren van M met overeenkomstige enkelvoudige waarde σ₁.

Een bewijs. Vergelijkbaar met het geval van de eigenwaarden, door veronderstelling, voldoen de twee vectoren aan de Lagrange -vermenigvuldigingsvergelijking:

${\ displaystyle \ nabla \ sigma = \ nabla \ mathbf {u} ^{\ textsf {t}} \ mathbf {m} \ mathbf {v} -\ lambda _ {1} \ cdot \ nabla \ nabla \ nabla \ nabla \ nabla \ nabla \ nabla \ nabla \ nabla \ nabla {\ textsf {t}} \ mathbf {u} -\ lambda _ {2} \ cdot \ nabla \ mathbf {v} ^{\ textsf {t}} \ mathbf {v}}$

Na wat algebra wordt dit

${\ displayStyle {\ begin {uitgelijnd} \ mathbf {m} \ mathbf {v} _ {1} & = 2 \ lambda _ {1} \ mathbf {u} _ {1} +0 \\\ mathbf {m} ^{\ textsf {t}} \ mathbf {u} _ {1} & = 0+2 \ lambda _ {2} \ mathbf {v} _ {1} \ end {uitlijnd}}}$

De eerste vergelijking van links vermenigvuldigen met ${\ DisplayStyle \ Mathbf {u} _ {1}^{\ textsf {t}}}$ en de tweede vergelijking van links door ${\ DisplayStyle \ Mathbf {v} _ {1}^{\ textsf {t}}}$ en nemen ||u|| = ||v|| = 1 Rekening houdend met

${\ displayStyle \ sigma _ {1} = 2 \ lambda _ {1} = 2 \ lambda _ {2}.}$

Dit aansluiten op het paar vergelijkingen hierboven, hebben we

${\displaystyle {\begin{aligned}\mathbf {M} \mathbf {v} _{1}&=\sigma _{1}\mathbf {u} _{1}\\\mathbf {M} ^{\ textsf {t}} \ mathbf {u} _ {1} & = \ sigma _ {1} \ mathbf {v} _ {1} \ end {uitgelijnd}}}$

Dit bewijst de verklaring.

Meer enkelvoudige vectoren en enkelvoudige waarden kunnen worden gevonden door te maximaliseren σ(u, v) Over genormaliseerd u, v die orthogonaal zijn u₁ en v₁, respectievelijk.

De doorgang van echt naar complex is vergelijkbaar met de eigenwaarde.

Het berekenen van de SVD

De ontleding van de enkelvoudige waarde kan worden berekend met behulp van de volgende waarnemingen:

• De links-singulaire vectoren van M zijn een set van ortonormaal eigenvectoren van Mm^⁎.
• De rechter-singulaire vectoren van M zijn een reeks orthonormale eigenvectoren van M^⁎M.
• De niet-nul enkelvoudige waarden van M (gevonden op de diagonale inzendingen van ${\ DisplayStyle \ Mathbf {\ Sigma}}$) zijn de vierkante wortels van de niet-nul eigenwaarden van beide M^⁎M en Mm^⁎.

Numerieke benadering

De SVD van een matrix M wordt meestal berekend door een tweestapsprocedure. In de eerste stap wordt de matrix gereduceerd tot een bidiagonale matrix. Dit neemt O(Mn²) Floating-Point Operations (FLOP), ervan uitgaande m ≥ n. De tweede stap is om de SVD van de bidiagonale matrix te berekenen. Deze stap kan alleen worden gedaan met een iteratieve methode (zoals bij eigenwaarde -algoritmen). In de praktijk volstaat het echter om de SVD tot een bepaalde precisie te berekenen, zoals de machine -epsilon. Als deze precisie als constant wordt beschouwd, neemt de tweede stap O (n) iteraties, elk kosten o (n) flops. De eerste stap is dus duurder en de totale kosten zijn O (Mn²) flops (Trefethen & Bau III 1997, Lezing 31).

De eerste stap kan worden gedaan met behulp van Reflecties van huishoudelijken Voor een kostprijs van 4Mn²- 4n³/3 flops, ervan uitgaande dat alleen de enkelvoudige waarden nodig zijn en niet de enkelvoudige vectoren. Als m is veel groter dan n dan is het voordelig om eerst de matrix te verminderen M naar een driehoekige matrix met de QR -ontleding en gebruik vervolgens reflecties van huishoudelijke naam om de matrix verder te verminderen tot bidiagonale vorm; De gecombineerde kosten zijn 2Mn²+ 2n³ flops (Trefethen & Bau III 1997, Lezing 31).

De tweede stap kan worden gedaan door een variant van de QR -algoritme voor de berekening van eigenwaarden, die voor het eerst werd beschreven door Golub & Kahan (1965). De Lapack Subroutine DBDSQR^[18] Implementeert deze iteratieve methode, met enkele wijzigingen om de zaak te dekken waar de enkelvoudige waarden erg klein zijn (Demmel & Kahan 1990). Samen met een eerste stap met behulp van de reflecties van huishoudelijke naam en, indien van toepassing, QR -ontleding, vormt dit de DGESVD^[19] Routine voor de berekening van de ontleding van de enkelvoudige waarde.

Hetzelfde algoritme wordt geïmplementeerd in de GNU wetenschappelijke bibliotheek (GSL). De GSL biedt ook een alternatieve methode die een eenzijdige Jacobi-orthogonalisatie gebruikt in stap 2 (GSL Team 2007). Deze methode berekent de SVD van de bidiagonale matrix door een reeks van 2 × 2 SVD -problemen op te lossen, vergelijkbaar met hoe de Jacobi EigenValue -algoritme Lost een reeks van 2 × 2 eigenwaarde -methoden op (Golub & Van Loan 1996, §8.6.3). Nog een andere methode voor stap 2 gebruikt het idee van Divide-and-Conquer EigenValue-algoritmen (Trefethen & Bau III 1997, Lezing 31).

Er is een alternatieve manier die niet expliciet de EigenValue -ontleding gebruikt.^[20] Meestal het enkelvoudige waardeprobleem van een matrix M wordt omgezet in een equivalent symmetrisch eigenwaardeprobleem zoals M m^⁎, M^⁎M, of

${\ displayStyle {\ begin {bMatrix} \ mathbf {o} & \ mathbf {m} \\\ mathbf {m} ^{*} & \ mathbf {o} \ end {bMatrix}}.}.}.$

De benaderingen die EigenValue -ontledingen gebruiken, zijn gebaseerd op de QR -algoritme, wat goed ontwikkeld is om stabiel en snel te zijn. Merk op dat de enkelvoudige waarden reële en rechts- en linkse vectoren zijn, zijn niet vereist om gelijkenisstransformaties te vormen. Men kan iteratief afwisselen tussen de QR -ontleding en de LQ -ontleding Om de echte diagonaal te vinden Hermitische matrices. De QR -ontleding geeft M ⇒ Q r en de LQ -ontleding van R geeft R ⇒ L P^⁎. Dus bij elke iteratie hebben we dat M ⇒ Q L P^⁎, update M ⇐ L en herhaal de orthogonalisaties. Eventueel,^{[verduidelijking nodig]} Deze iteratie tussen QR -ontleding en LQ -ontleding produceert linker- en rechtse unitaire enkelvoudige matrices. Deze benadering kan niet gemakkelijk worden versneld, zoals het QR -algoritme kan met spectrale verschuivingen of deflatie. Dit komt omdat de shift -methode niet gemakkelijk kan worden gedefinieerd zonder gebruik te maken van gelijkenisstransformaties. Deze iteratieve aanpak is echter heel eenvoudig te implementeren, dus is een goede keuze als snelheid niet uitmaakt. Deze methode biedt ook inzicht in hoe puur orthogonale/unitaire transformaties de SVD kunnen verkrijgen.

Analytisch resultaat van 2 × 2 SVD

De enkelvoudige waarden van een 2 × 2 -matrix kunnen analytisch worden gevonden. Laat de matrix zijn${\ DisplayStyle \ Mathbf {m} = z_ {0} \ Mathbf {i}+z_ {1} \ sigma _ {1}+z_ {2} \ sigma _ {2}+z_ {3} \ sigma _ _ {3 }}$

waar ${\ DisplayStyle Z_ {i} \ in \ Mathbb {c}}$ zijn complexe getallen die de matrix parametreren, I is de identiteitsmatrix, en ${\ DisplayStyle \ Sigma _ {i}}$ duiden op de Pauli Matrices. Dan worden de twee enkelvoudige waarden gegeven door

${\ displayStyle {\ begin {uitgelijnd} \ sigma _ {\ pm} & = {\ sqrt {| z_ {0} |^{2}+| z_ {1} |^{2}+| z_ {2} | ^{2}+| z_ {3} |^{2} \ pm {\ sqrt {(| z_ {0} |^{2}+| z_ {1} |^{2}+| z_ {2} | ^{2}+| z_ {3} |^{2})^{2}-| z_ {0}^{2} -z_ {1}^{2} -z_ {2}^{2} -z_ {3}^{2} |^{2}}}}}} \\ & = {\ sqrt {| z_ {0} |^{2}+| z_ {1} |^{2}+| z_ {2 } |^{2}+| z_ {3} |^{2} \ pm 2 {\ sqrt {(\ operatorName {re} z_ {0} z_ {1}^{*})^{2}+(\ OperatorName {re} Z_ {0} Z_ {2}^{*})^{2}+(\ OperatorName {re} Z_ {0} Z_ {3}^{*})^{2}+(\ OperatorName {{\ operatorName { Im} z_ {1} z_ {2}^{*})^{2}+(\ operatorName {im} z_ {2} z_ {3}^{*})^{2}+(\ operatorame {im} z_ {3} z_ {1}^{*})^{2}}}}}} \ end {uitgelijnd}}}$

Verminderde SVD's

Visualisatie van gereduceerde SVD -varianten. Van boven naar beneden: 1: volledige SVD, 2: dunne svd (verwijder kolommen van u niet overeenkomend met rijen van v*), 3: compacte svd (verwijder een defense enkelvoudige waarden en bijbehorende kolommen/rijen in u en v*), 4 : Afgeknotte SVD (houd alleen de grootste t enkelvoudige waarden en bijbehorende kolommen/rijen in U en V*)

In toepassingen is het vrij ongebruikelijk voor de volledige SVD, inclusief een volledige unitaire ontleding van de nulruimte van de matrix, te vereist. In plaats daarvan is het vaak voldoende (evenals sneller en economischer voor opslag) om een ​​gereduceerde versie van de SVD te berekenen. Het volgende kan worden onderscheiden voor een m×n Matrix M van rang r:

Dunne svd

De dunne, of economie-size, SVD van een matrix M is gegeven door^[21]

${\ displaystyle \ mathbf {m} = \ mathbf {u} _ {k} {\ boldsymbol {\ sigma}} _ {k} \ mathbf {v} _ {k}^{*},},}$

waar

${\ DisplayStyle K = \ OperatorName {min} (M, N)}$,

de matrices U_k en V_k bevatten alleen de eerste k kolommen van U en Ven σ_k Bevat alleen de eerste k enkelvoudige waarden van σ. De matrix U_k is dus m×k, Σ_k is k×k diagonaal, en V_k* is k×n.

De dunne SVD gebruikt aanzienlijk minder ruimte- en berekeningstijd als k≪ Max (m, n). De eerste fase in de berekening is meestal een QR -ontleding van M, wat in dit geval een aanzienlijk snellere berekening kan opleveren.

Compact SVD

${\ displaystyle \ mathbf {m} = \ mathbf {u} _ {r} {\ boldsymbol {\ sigma}} _ {r} \ mathbf {v} _ {r}^}^{}}}$

Alleen de r kolomvectoren van U en r rijvectoren van V* overeenkomend met de niet-nul enkelvoudige waarden σ_r worden berekend. De resterende vectoren van U en V* worden niet berekend. Dit is sneller en economischer dan de dunne SVD als r≪ min (m, n). De matrix U_r is dus m×r, Σ_r is r×r diagonaal, en V_r* is r×n.

Afgeknotte SVD

In veel toepassingen het nummer r van de niet-nul enkelvoudige waarden is groot, waardoor zelfs de compacte SVD onpraktisch is om te berekenen. In dergelijke gevallen moeten de kleinste enkelvoudige waarden mogelijk worden afgekapt om alleen te berekenen t≪r Niet-nul enkelvoudige waarden. De afgeknotte SVD is niet langer een exacte ontleding van de oorspronkelijke matrix M, maar biedt eerder het optimale Lage matrixbenadering ${\ DisplayStyle {\ tilde {\ Mathbf {m}}}}$ door elke matrix van een vaste rangt

${\ DisplayStyle {\ tilde {\ Mathbf {m}}} = \ Mathbf {u} _ {t} {\ boldsymbol {\ sigma}} _ {t} \ mathbf {v} _}^{*}}}^{*}}$,

waar matrix U_t is m×t, Σ_t is t×t diagonaal, en V_t* is t×n. Alleen de t kolomvectoren van U en t rijvectoren van V* overeenkomend met de t Grootste enkelvoudige waarden σ_t worden berekend. Dit kan veel sneller en economischer zijn dan de compacte SVD als t≪r, maar vereist een compleet andere toolset van numerieke oplossers.

In toepassingen die een benadering vereisen voor de Moore - penrose omgekeerd van de matrix M, de kleinste enkelvoudige waarden van M zijn interessant, die uitdagender zijn om te berekenen in vergelijking met de grootste.

Afgeknotte SVD is werkzaam latente semantische indexering.^[22]

Normen

KY -fannormen

De som van de k grootste enkelvoudige waarden van M is een matrixnorm, de KY Fan k-norm van M.^[23]

De eerste van de KY-fannormen, de KY-fan 1-norm, is hetzelfde als de Operatornorm van M als een lineaire operator met betrekking tot de Euclidische normen van K^m en Kⁿ. Met andere woorden, de KY Fan 1-Norm is de operatornorm die wordt geïnduceerd door de standaard ℓ² Euclidisch binnenproduct. Om deze reden wordt het ook de operator 2-norm genoemd. Men kan gemakkelijk de relatie tussen de KY-fan 1-norm- en enkelvoudige waarden verifiëren. Het is over het algemeen waar voor een begrensde operator M Op (mogelijk oneindig-dimensionale) Hilbert-ruimtes

${\ DisplayStyle \ | \ Mathbf {M} \ | = \ | \ Mathbf {M} ^{*} \ Mathbf {m} \ | ^{\ frac {1} {2}}}}$

Maar in de Matrix -zaak ((M* m)^1/2 is een normale matrix, dus ||M* m||^1/2 is de grootste eigenwaarde van (M* m)^1/2, d.w.z. de grootste enkelvoudige waarde van M.

De laatste van de KY -fannormen, de som van alle enkelvoudige waarden, is de Trace -norm (ook bekend als de 'nucleaire norm'), gedefinieerd door ||M|| = Tr [(M* m)^1/2] (de eigenwaarden van M* m zijn de vierkanten van de enkelvoudige waarden).

Hilbert - Schmidt Norm

De enkelvoudige waarden zijn gerelateerd aan een andere norm op de ruimte van operators. Houd rekening met de Hilbert - Schmidt innerlijk product op de n × n matrices, gedefinieerd door

${\ DisplayStyle \ Langle \ Mathbf {M}, \ Mathbf {n} \ Rangle = \ OperatorName {Tr} \ Left (\ Mathbf {n} ^{*} \ Mathbf {m} \ rechts).}.}.}.$

Dus de geïnduceerde norm is

${\displaystyle \|\mathbf {M} \|={\sqrt {\langle \mathbf {M} ,\mathbf {M} \rangle }}={\sqrt {\operatorname {tr} \left(\mathbf { M} ^{*} \ Mathbf {m} \ rechts)}}.}$

Omdat het spoor invariant is onder eenheidsequivalentie, laat dit zien

${\ displaystyle \ | \ mathbf {m} \ | = {\ sqrt {\ sum _ {i} \ sigma _ {i}^{2}}}}}$

waar σ_i zijn de enkelvoudige waarden van M. Dit wordt de Frobenius Norm, Schatten 2-norm, of Hilbert - Schmidt Norm van M. Directe berekening laat zien dat de Frobenius -norm van M = (m_IJ) valt samen met:

${\ displaystyle {\ sqrt {\ sum _ {ij} | m_ {ij} |^{2}}}.}.$

Bovendien zijn de Frobenius -norm en de trace -norm (de nucleaire norm) speciale gevallen van de Schattennorm.

Variaties en generalisaties

Modus-k vertegenwoordiging

${\ displayStyle m = uSV^{\ textsf {t}}}$ kan worden weergegeven met behulp van modus-k vermenigvuldiging matrix ${\ DisplayStyle S}$ toepassen ${\ DisplayStyle \ Times _ {1} u}$ dan ${\ DisplayStyle \ Times _ {2} v}$ op het resultaat; dat is ${\ DisplayStyle m = S \ Times _ {1} u \ Times _ {2} v}$.^[24]

Tensor SVD

Er bestaan ​​twee soorten tensor-ontledingen, die de SVD generaliseren naar multi-way arrays. Een van hen ontleedt een tensor in een som van rang-1-tensoren, die een genoemd wordt Tensor ranglijst. Het tweede type ontleding berekent de orthonormale subruimten die verband houden met de verschillende factoren die in het tensorproduct verschijnen van vectorruimtes waarin de tensor leeft. Deze ontleding wordt in de literatuur aangeduid als de SVD van hogere orde (Hosvd) of Tucker3/Tuckerm. In aanvulling, Multilinear Principal Component Analysis in Multilinear Subspace Learning omvat dezelfde wiskundige bewerkingen als Tucker -ontleding, worden gebruikt in een andere context van dimensionaliteitsvermindering.

Schaalinvariante SVD

De enkelvoudige waarden van een matrix A zijn uniek gedefinieerd en zijn invariant met betrekking tot linker en/of rechter unitaire transformaties van A. Met andere woorden, de enkelvoudige waarden van UAV, voor Unitary U en V, zijn gelijk aan de enkelvoudige waarden van A. Dit is een belangrijke eigenschap voor toepassingen waarin het nodig is om Euclidische afstanden en invariantie met betrekking tot rotaties te behouden.

De schaalinvariante SVD, of Si-SVD,^[25] is analoog aan de conventionele SVD, behalve dat de unieke beperkte enkelvoudige waarden invariant zijn met betrekking tot diagonale transformaties van A. Met andere woorden, de enkelvoudige waarden van Dae, voor omkeerbare diagonale matrices D en E, zijn gelijk aan de enkelvoudige waarden van A. Dit is een belangrijke eigenschap voor toepassingen waarvoor invariantie aan de keuze van eenheden op variabelen (bijv. Metrische versus imperiale eenheden) nodig is.

Hogere orde SVD van functies (HOSVD)

Tensor Product (TP) modeltransformatie numeriek de Hosvd van functies. Bezoek voor meer informatie:

• Tensor productmodel transformatie
• HOSVD-gebaseerde canonieke vorm van TP-functies en QLPV-modellen
• TP -modeltransformatie in de controletheorie

Begrensde operators op Hilbert -ruimtes

De factorisatie M = Uσv^⁎ kan worden uitgebreid tot een begrensde operator M Op een scheidbare Hilbert -ruimte H. Namelijk voor elke begrensde operator M, er bestaan ​​een Gedeeltelijke isometrie U, een eenheid V, een maatruimte (X,,μ), en een niet-negatief meetbaar f zoals dat

${\ DisplayStyle \ Mathbf {m} = \ Mathbf {u} t_ {f} \ Mathbf {v} ^{*}}$

waar ${\ displaystyle t_ {f}}$ is de vermenigvuldiging door f Aan L²(X, μ).

Dit kan worden aangetoond door het lineaire algebraïsche argument voor het matriciale geval hierboven na te bootsen. VT_fV* is de unieke positieve vierkantswortel van M*m, zoals gegeven door de Borel functionele calculus voor zelfbeschermingsoperators. De reden waarom U Niet hoeven te zijn, is dat, in tegenstelling tot het eindige-dimensionale geval, gegeven een isometrie U₁ met niet -triviale kernel, een geschikt U₂ mag dat niet zo vinden

${\ displayStyle {\ begin {bMatrix} u_ {1} \\ u_ {2} \ end {bMatrix}}}$

is een unitaire operator.

Wat matrices betreft, is de enkelvoudige waarde -factorisatie gelijk aan de polaire ontleding Voor operators: we kunnen gewoon schrijven

${\ DisplayStyle \ Mathbf {m} = \ Mathbf {u} \ Mathbf {v} ^{*} \ cdot \ Mathbf {v} t_ {f} \ Mathbf {v} ^{*}}$

en merk dat op U v* is nog steeds een gedeeltelijke isometrie terwijl VT_fV* is positief.

Enkelvoudige waarden en compacte operators

Het idee van enkelvoudige waarden en linker/rechter-singulaire vectoren kan worden uitgebreid compacte operator op Hilbert Space omdat ze een discreet spectrum hebben. Als T is compact, elke niet-nul λ In zijn spectrum is een eigenwaarde. Bovendien kan een compacte zelfvoorzieningsoperator worden gediagonaliseerd door zijn eigenvectoren. Als M is compact, zo is M^⁎M. Het diagonalisatieresultaat toepassen, het unitaire beeld van zijn positieve vierkantswortel T_f  heeft een set orthonormale eigenvectoren {e_i} overeenkomend met strikt positieve eigenwaarden {σ_i}. Voor enige ψ ∈ H,,

${\ displaystyle \ mathbf {m} \ psi = \ mathbf {u} t_ {f} \ mathbf {v} ^{*} \ psi = \ sum _ {i} \ left \ langle \ mathbf {u} t_ {f } \ mathbf {v} ^{*} \ psi, \ mathbf {u} e_ {i} \ right \ rangle \ mathbf {u} e_ {i} = \ sum _ {i} \ sigma _ _ {i} \ links \ langle \ psi, \ mathbf {v} e_ {i} \ right \ rangle \ mathbf {u} e_ {i},}$

waar de serie convergeert in de normtopologie op H. Merk op hoe dit lijkt op de uitdrukking uit het eindige-dimensionale geval. σ_i worden de enkelvoudige waarden van M. {Ue_i} (Resp. {Ve_i}) kunnen worden beschouwd als de links-singulaire (resp. rechter-singular) vectoren van M.

Compacte operators op een Hilbert -ruimte zijn de sluiting van Eindige range operators in de uniforme operatortopologie. De bovenstaande serie -uitdrukking geeft een expliciete dergelijke weergave. Een onmiddellijk gevolg hiervan is:

Stelling. M is compact als en alleen als M^⁎M is compact.

Geschiedenis

De ontleding van de enkelvoudige waarde werd oorspronkelijk ontwikkeld door differentiële geometers, die wilden bepalen of een echte bilineaire vorm kan gelijk worden gemaakt aan een ander door onafhankelijke orthogonale transformaties van de twee ruimtes waarop het werkt. Eugenio Beltrami en Camille Jordan onafhankelijk ontdekt, respectievelijk in 1873 en 1874, dat de enkelvoudige waarden van de bilineaire vormen, vertegenwoordigd als een matrix, vormen een complete set van invarianten voor bilineaire vormen onder orthogonale substituties. James Joseph Sylvester Aangekomen ook bij de ontleding van de enkelvoudige waarde voor echte vierkante matrices in 1889, blijkbaar onafhankelijk van zowel Beltrami als Jordanië. Sylvester noemde de enkelvoudige waarden de Canonieke multiplicatoren van de matrix A. De vierde wiskundige die de ontleding van de enkelvoudige waarde onafhankelijk is ontdekt, is Autonne in 1915, die er via de polaire ontleding. Het eerste bewijs van de ontleding van de enkelvoudige waarde voor rechthoekige en complexe matrices lijkt te zijn Carl Eckart en Gale J. Young in 1936;^[26] Ze zagen het als een generalisatie van de Hoofdas transformatie voor Hermitische matrices.

In 1907, Erhard Schmidt gedefinieerd een analoog van enkelvoudige waarden voor integrale operators (die compact zijn, onder zwakke technische veronderstellingen); Het lijkt erop dat hij zich niet bewust was van het parallelle werk over enkelvoudige waarden van eindige matrices. Deze theorie werd verder ontwikkeld door Émile Picard in 1910, die de eerste is die de cijfers noemt ${\ DisplayStyle \ Sigma _ {k}}$ enkelvoudige waarden (of in het Frans, Valeurs singulières).

Praktische methoden voor het berekenen van de SVD -datum terug naar Kogbetliantz in 1954-1955 en Hestenes in 1958,^[27] Lijken nauw op de Jacobi EigenValue -algoritme, die vliegtuigrotaties gebruikt of Givens rotaties. Deze werden echter vervangen door de methode van Gene Golub en William Kahan Gepubliceerd in 1965,^[28] die gebruikt Transformaties van huishoudenaar of reflecties. In 1970, Golub en Christian Reinsch^[29] publiceerde een variant van het Golub/Kahan-algoritme dat nog steeds degene is die vandaag het meest wordt gebruikt.

Zie ook

Aantekeningen

Referenties

• Banerjee, Sudipto; Roy, Anindya (2014), Lineaire algebra- en matrixanalyse voor statistieken, Teksten in Statistical Science (1e ed.), Chapman en Hall/CRC, ISBN 978-1420095388
• Chicco, D; Masseroli, M (2015). "Softwaresuite voor voorspelling van gen- en eiwit annotatie en zoekopdracht". IEEE/ACM -transacties op computationele biologie en bioinformatica. 12 (4): 837–843. doen:10.1109/tcbb.2014.2382127. HDL:11311/959408. Pmid 26357324. S2CID 14714823.
• Trefethen, Lloyd N.; Bau III, David (1997). Numerieke lineaire algebra. Philadelphia: Society for Industrial and Applied Mathematics. ISBN 978-0-89871-361-9.
• Demmel, James; Kahan, William (1990). "Nauwkeurige enkelvoudige waarden van bidiagonale matrices". Siam Journal on Scientific and Statistical Computing. 11 (5): 873–912. Citeseerx 10.1.1.48.3740. doen:10.1137/0911052.
• Golub, Gene H.; Kahan, William (1965). "Het berekenen van de enkelvoudige waarden en pseudo-omgekeerde van een matrix". Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis. 2 (2): 205–224. Bibcode:1965sjna .... 2..205G. doen:10.1137/0702016. Jstor 2949777.
• Golub, Gene H.; Van lening, Charles F. (1996). Matrixberekeningen (3e ed.). Johns Hopkins. ISBN 978-0-8018-5414-9.
• GSL Team (2007). "§14.4 Ontleding van enkelvoudige waarde". GNU wetenschappelijke bibliotheek. Referentiehandleiding.
• Halldor, Bjornsson en Venegas, Silvia A. (1997). "Een handleiding voor EOF- en SVD -analyses van klimaatgegevens". McGill University, CCGCR Report No. 97-1, Montréal, Québec, 52pp.
• Hansen, P. C. (1987). "De afgeknotte SVD als een methode voor regularisatie". BEETJE. 27 (4): 534–553. doen:10.1007/BF01937276. S2CID 37591557.
• Horn, Roger A.; Johnson, Charles R. (1985). "Sectie 7.3". Matrixanalyse. Cambridge University Press. ISBN 978-0-521-38632-6.
• Horn, Roger A.; Johnson, Charles R. (1991). "Hoofdstuk 3". Onderwerpen in matrixanalyse. Cambridge University Press. ISBN 978-0-521-46713-1.
• Samet, H. (2006). Funderingen van multidimensionale en metrische gegevensstructuren. Morgan Kaufmann. ISBN 978-0-12-369446-1.
• Strang G. (1998). "Sectie 6.7". Inleiding tot lineaire algebra (3e ed.). Wellesley-Cambridge Press. ISBN 978-0-9614088-5-5.
• Stewart, G. W. (1993). "Over de vroege geschiedenis van de ontleding van de enkelvoudige waarde". Siam Review. 35 (4): 551–566. Citeseerx 10.1.1.23.1831. doen:10.1137/1035134. HDL:1903/566. Jstor 2132388.
• Wall, Michael E.; Rechtsteiner, Andreas; Rocha, Luis M. (2003). "Singular Value Decomposition en Principal Component Analysis". In D.P. Berrar; W. Dubitzky; M. Granzow (Eds.). Een praktische benadering van microarray -gegevensanalyse. Norwell, MA: Kluwer. pp. 91-109.
• Druk, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sectie 2.6", Numerieke recepten: The Art of Scientific Computing (3e ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8

Externe links

• Online SVD -calculator