Szinguláris érték felbontás

A matematika , a módszer a lineáris algebra , hogy lebomlására szinguláris értékek (vagy SVD , a angol szinguláris érték dekompozíció ) egy mátrix fontos eszköze faktorizáció tényleges téglalap alakú vagy komplex mátrixok. Alkalmazásai a jelfeldolgozástól a statisztikákig , beleértve a meteorológiát is .

A spektrális tétel kimondja, hogy egy normális mátrixot lehet diagonalizálható egy ortonormáiis bázis a sajátvektor . Láthatjuk a szinguláris értékbontást, mint a spektrális tétel általánosítását tetszőleges mátrixokra, amelyek nem feltétlenül négyzetesek.

Matematikai kontextus

A tétel állítása

Legyen $M$ olyan m × n mátrix, amelynek együtthatói a K mezőhöz tartoznak , ahol K = ℝ vagy K = ℂ . Ekkor létezik a forma faktorizálása :

M = U \ Sigma V ^ {*} \, \!

a $U$ egy egységes mátrix m × m a K , $Σ$ egy m × n mátrix , amelynek diagonáiis együtthatók pozitívak vagy nulla valós számok, és az összes többi nulla, és $V *$ jelentése a szomszédos mátrix a $V$ , egységes mátrix n × n a K . Ezt nevezzük az $M$ szinguláris értékbontásának faktorálásával .

A mátrix $V$ tartalmaz egy sor alap vektorok ortonormális a K n , az úgynevezett „input” vagy „elemzés”;
Az $U$ mátrix tartalmazza a K m ortonormális alapvektorainak halmazát , az úgynevezett „kimeneti” vektorokat ;
A $Σ$ mátrix átlós együtthatóiban tartalmazza az $M$ mátrix egyes értékeit , ezek megfelelnek a sajátértékek gyökereinek . $M ^ {*} M$
Általános szokás az $Σ i , i$ értékek csökkenő sorrendbe rendezése. Ekkor a $Σ$ mátrixot $M$ egyedülálló módon határozza meg (de $U$ és $V$ nem).

Létezés

A mátrix λ sajátértékét az M u = λ u összefüggés jellemzi . Ha $M$ jelentése hermitikus másik különböző jellemzése lehetséges. Legyen $M$ valós szimmetrikus n × n mátrix . Az f : R n → R értéket úgy állítjuk be , hogy f ( x ) = x T M x . Ez a függvény folyamatos, és eléri a maximumot egy bizonyos u vektorban, amikor a zárt egységgömbre korlátozódik {|| x || ≤ 1}. Szerint a Lagrange multiplikátor-tétel , u kielégíti:

\ nabla f = \ nabla \; x ^ {T} Mx = \ lambda \ cdot \ nabla \; x ^ {T} x.

Könnyen megmutatjuk, hogy a fenti összefüggés megadja $M u = λ u értéket$ . Így $λ$ az $M$ legnagyobb sajátértéke . Ugyanez a műveleteket ortogonális kiegészítője az u , így a második legnagyobb érték, és így tovább. Az esetben, ha a Hermite-komplex mátrix hasonló, a F ( x ) = x * M x , a funkciója a 2 n változók valós értékeket.

Az egyes értékek hasonlóak, mivel algebrailag vagy variációs elvek alapján írhatók le. Másrészt, a sajátértékek esetétől eltérően, az $M$ hermiticitására és szimmetriájára már nincs szükség.

Bizonyítás algebra használatával

Legyen $M$ komplex m × n mátrix . Ekkor M * M pozitív félhatározott, ezért remete. A spektrális tétel szerint létezik az n oldal négyzetes egységmátrixa , amelyet V-nek jelölünk , így:

V ^ {*} M ^ {*} MV = {\ kezdete {pmatrix} D & 0 \\ 0 és 0 \ end {pmatrix}}

ahol D átlós, pozitív határozott , sőt r rangsorolja azt az $M-et$ . V megfelelő megírásával :

{\ begin {pmatrix} V_ {1} ^ {*} \\ V_ {2} ^ {*} \ end {pmatrix}} M ^ {*} M {\ begin {pmatrix} V_ {1} & V_ {2 } \ end {pmatrix}} = {\ begin {pmatrix} V_ {1} ^ {*} M ^ {*} MV_ {1} és V_ {1} ^ {*} M ^ {*} MV_ {2} \ \ V_ {2} ^ {*} M ^ {*} MV_ {1} és V_ {2} ^ {*} M ^ {*} MV_ {2} \ end {pmatrix}} = {\ begin {pmatrix} D & 0 \\ 0 és 0 \ end {pmatrix}}.

a V 1 n × r mátrix rang R és V 2 n × mátrix (NR) .

Így V * 1 M * MV 1 = D és MV 2 = 0. Beállítottuk:

U_ {1} = D ^ {{- 1/2}} V_ {1} ^ {*} M ^ {*}.

Tehát van:

U_ {1} MV_ {1} = D ^ {{1/2}}. \,

Láthatjuk, hogy ez majdnem a várt eredmény, csakhogy az $U 1$ részleges izometriával rendelkező r × m mátrix ( $U$ $1$ $U$ $*$ $1$ $=$ $I$ ). A bizonyítás kitöltéséhez az $U$ $1-$ et kitöltjük, hogy egységes legyen. Az egyik olyan $U$ $2-t$ választ , amely egységes. Egy számítás azt mutatja, hogy: ${\ begin {pmatrix} U_ {1} \\ U_ {2} \ end {pmatrix}}$

{\ begin {pmatrix} U_ {1} \\ U_ {2} \ end {pmatrix}} M {\ begin {pmatrix} V_ {1} & V_ {2} \ end {pmatrix}} = {\ begin {pmatrix } D ^ {{1/2}} és 0 \\ 0 és 0 \ vége {pmatrix}},

Valóban, az MV 2 = 0 értéket használjuk, és ezt azért látjuk, mert és ahogyan az egységes ${\ displaystyle U_ {2} MV_ {1} = U_ {2} U_ {1} ^ {\ tőr} U_ {1} MV_ {1} = 0 \,}$ ${\ displaystyle U_ {1} ^ {\ tőr} U_ {1} = I \,}$ ${\ displaystyle U_ {2} U_ {1} ^ {\ tőr} = 0 \,}$ ${\ begin {pmatrix} U_ {1} \\ U_ {2} \ end {pmatrix}}$

amely megfelel a várt eredménynek, figyelembe véve az U számára a szomszédos mátrixot . ${\ begin {pmatrix} U_ {1} \\ U_ {2} \ end {pmatrix}}$

Az igazolást úgy is elkezdhettük, hogy $M$ $*$ $M$ helyett diagonalizáltuk az $MM *$ -t, és akkor közvetlenül megmutattuk volna, hogy az $MM$ $*$ és $M$ $*$ $M$ azonos nulla nulla sajátértékekkel rendelkeznek.

Egyéb jellemzés

A szinguláris értékek is jellemezhető, mint a maximális értékek a u T Mv , tekinthető függvényében u és v , mint különösen altér. Az egyes vektorok azok az u és v értékek, amelyekre ezek a maximumok elértek.

Legyen M valós m × n mátrix . Legyen S m –1 és S n –1 az R m és az R n egységvektorainak halmaza (a 2. norma szerint) . Beállítottuk a függvényt:

\ sigma (u, v) = u ^ {{T}} Mv \,

az u ∈ S m –1 és v ∈ S n –1 vektorokhoz .

Úgy véljük, a funkció σ korlátozódik S m -1 × S n -1 . Mivel az S m –1 és az S n –1 is kompakt halmaz , ezért a termékük is kompakt. Sőt, mivel σ folyamatos, akkor eléri a maximumát legalább egy u ∈ S m –1 és v ∈ S n –1 vektorpár esetében . Ezt a maximumot σ 1 , a megfelelő vektorokat pedig u 1 és v 1 jelöljük . Mivel σ 1 az σ ( u , v ) legnagyobb értéke , ezért pozitív: ha negatív lenne, akkor az u 1 vagy v 1 előjelének megváltoztatásával pozitívvá tennénk - és ennélfogva nagyobbá.

A Lemma - u 1 és v 1 az σ 1-hez társított $M$ bal és jobb oldali egyes vektora .

Bizonyítás - A sajátértékek esetében feltételezve, hogy a két vektor megfelel a Lagrange-egyenletnek :

\ nabla \ sigma = \ nabla \; u ^ {T} Mv = \ lambda _ {1} \ cdot \ nabla \; u ^ {T} u = \ lambda _ {2} \ cdot \ nabla \; v ^ { tévé

Megmutatjuk, hogy ez:

Mv _ {{1}} = 2 \ lambda _ {{1}} u _ {{1}} + 0

, és

M ^ {{T}} u _ {{1}} = 0 + 2 \ lambda _ {{2}} v _ {{1}}

Ha a bal oldali első egyenletet megszorozzuk u-valT
1, a másodikat pedig balra vT
1, azáltal , hogy: $\ balra | \ balra | u _ {{1}} \ jobbra | \ jobbra | _ {2} = \ balra | \ balra | v _ {{1}} \ jobbra | \ jobbra | _ {2} = 1$

u _ {{1}} ^ {{T}} Mv _ {{1}} = \ sigma _ {{1}} = 2 \ lambda _ {{1}}

v _ {{1}} ^ {{T}} M ^ {{T}} u _ {{1}} = \ sigma _ {{1}} = 2 \ lambda _ {{2}}

Így σ 1 = 2 λ 1 = 2 λ 2 . Tehát van:

Mv _ {{1}} = \ sigma _ {{1}} u _ {{1}} \,

, És hasonlóképpen ,.

M ^ {{T}} u _ {{1}} = \ sigma _ {{1}} v _ {{1}} \,

Más szinguláris vektorok és szinguláris értékek úgy érhetők el, hogy maximalizáljuk az σ ( u , v ) értéket u , v felett , amelyek merőlegesek u 1-re és v 1 -re.

Ugyanígy lehet kezelni a komplex mátrixok esetét is.

Szinguláris értékek és egyes vektorok

Hívjuk szinguláris érték az $M$ bármely négyzetgyöke egy sajátértéke $M * M$ , más szóval minden pozitív valós σ, hogy létezik egy egységvektor u a K m és egy egységnyi vektor v a K n kielégíti:

{\ displaystyle M ^ {*} u = \ sigma v \ quad {\ textrm {és}} \ quad Mv = \ sigma u \, \!}

A vektorok u és v nevezik a bal szinguláris vektorok és a megfelelő szinguláris vektorok a σ, ill.

Bármilyen bontásban egyes számokban,

M = U \ Sigma V ^ {{*}} \, \!

a Σ átlós együtthatói megegyeznek az $M$ egyes értékeivel . Az $U$ és V oszlopai a megfelelő egyes számok bal és jobb oldali vektorai.

Ezért a fenti tétel kimondja, hogy:

Az m × n típusú $M$ mátrixnak legalább egy és legfeljebb p = min ( m , n ) elkülönülő egyes értéke van;
Mindig lehet találni egy egység alapján a K m alkotják a szinguláris vektorok balra $M$ ;
Mindig lehetséges megtalálni a K n egységalapját , amely az $M-$ től jobbra eső egyes számú vektorokból áll ;

Degeneráltnak mondjuk azt az egyes értéket, amelynek bal oldalán (illetve a jobb oldalon) két szinguláris vektort találhatunk .

A nem degenerált szinguláris értékeknek bal és jobb oldalon mindig van egyetlen szinguláris vektoruk, fáziseltolódásig, azaz az e i φ alak tényezőjével való szorzásig (valós számok esetén közeli előjelig) ). Következésképpen, ha az $M$ összes szinguláris értéke nem degenerált és nem nulla, akkor szinguláris értékekre bomlása egyedülálló az $U$ oszlop és a megfelelő $V$ oszlop ugyanazzal a fáziseltolással való szorzásakor .

A degenerált egyes értékeknek definíció szerint több egyes vektoruk van. Továbbá, ha u 1 és u 2 két bal szinguláris vektorok, amelyek megfelelnek az azonos szinguláris érték σ, akkor minden egység kapott vektorból lineáris kombinációja a két vektor is egy bal szinguláris vektort σ. Ugyanez vonatkozik a jobb oldali egyes vektorokra is. Tehát, ha $M-$ nek degenerált szinguláris értékei vannak, akkor szinguláris értékekre bomlása nem egyedi.

Példa

Legyen a mátrix:

M = {\ kezdődik {pmatrix} 1 & 0 & 0 & 0 & 2 \\ 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 & 0 \ end {pmatrix}}

Az $M$ szinguláris értékbontása ekkor:

{\ displaystyle U = {\ elején {pmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & -1 \\ 1 & 0 & 0 & 0 \ end {pmatrix }}, \ quad \ Sigma = {\ kezdődik {pmatrix} 4 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \ end {pmatrix}}, \ quad \ Sigma = {\ begin {pmatrix} 4 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \ end {pmatrix}}} 236 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \ end {pmatrix}}, \ quad V ^ {\ ast} = {\ begin {pmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 {,} 447 & 0 & 0 & 0 & 0 & 0 {,} 894 \\ 0 & 0 & 0 - 1 & 0 & 0 & 1 & 0 & 0 \\ 0 {,} 447 & 0 & 0 & 0 & 0 0 {,} 894 \\ 0 & 0 & 0 - 1 és 0 {,} 894 & 0 & 0 & 0 & 0 {,} 447 \ end {pmatrix}}}

(a nem egész értékek valójában közelítések 10–3-on belül : és ) Így: ${\ displaystyle 2 {,} 236 \ simeq {\ sqrt {5}} {,} \ 0 {,} 447 \ simeq 1 / {\ sqrt {5}}}$ ${\ displaystyle \ 0 {,} 894 \ simeq 2 / {\ sqrt {5}}}$

{\ displaystyle {\ begin {pmatrix} 1 & 0 & 0 & 0 & 2 \\ 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 & 0 0 \ end {pmatrix}} = {\ begin {pmatrix} 0 & 0 & 1 & 0 \\ 0 & 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 \ cdot {\ begin {pmatrix} 4 & 0 & 0 & 0 & 0 \ \ 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & {\ sqrt {5}} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \ end {pmatrix}} \ cdot {\ begin { pmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 \ 1 & 0 & 0 & 0 \\ 0 & 0 \ 1 & 0 & 0 & 0 \\ 0 & 0 \\ sqrt {5}} & 0 & 0 & 0 & 2 / {\ sqrt {5}} \\ 0 & 0 & 0 & 1 & 0 \\ - 2 / {\ sqrt {5}} & 0 & 0 & 0 & 1 / {\ sqrt {5}} \ end {pmatrix}}}

Ellenőrizzük, hogy a $Σ$ csak $átlóján$ van-e nulla érték. Továbbá, amint azt az alábbiakban, megszorozzuk az $U$ és $V *$ mátrixok által átültetett , megkapjuk az identitás mátrix:

{\ begin {pmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & -1 \\ 1 & 0 & 0 & 0 \ end {pmatrix}} \ cdot { \ begin {pmatrix} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & -1at & 0 \ end {pmatrix}} \ cdot {\ kezdet {pmatrix} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & -1at & 0 \ end {pmatrix}} = {\ begin { pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \ end {pmatrix}}

És hasonlóképpen:

{\ displaystyle {\ begin {pmatrix} 0 & 0 & 1 / {\ sqrt {5}} & 0 & -2 / {\ sqrt {5}} \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 2 / {\ sqrt {5}} és 0 & 1 / {\ sqrt {5}} \ end {pmatrix} } \ cdot {\ begin {pmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 1 / {\ sqrt {5}} & 0 & 0 & 0 & 2 / { \ sqrt {5}} \\ 0 & 0 & 0 & 1 & 0 \ \ -2 / {\ sqrt {5}} & 0 & 0 & 0 & 1 / {\ sqrt {5}} \ end {pmatrix} } = {\ kezdődik {pmatrix} 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 & 0 \\ 0 & 0 & 0 & 0 & 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 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0}}}

Kapcsolódás a sajátérték bomlásához

Az egyes értékbontás nagyon általános, abban az értelemben, hogy bármely m × n téglalap alakú mátrixra vonatkozik . A sajátérték-bontás viszont csak bizonyos négyzetmátrixok esetén működik . Ha azonban mindkettő meghatározva van, akkor kapcsolatban állnak egymással.

Pozitív félhatározott $M$ hermitikus mátrix esetén, vagyis az összes sajátérték pozitív valós, akkor az egyes értékek és az egyes vektorok megfelelnek az $M$ sajátértékeinek és sajátvektorainak :

{\ displaystyle M = U \ Sigma V ^ {*} \,}

Általánosságban elmondható, hogy az $M$ egyedi értékbontása esetén :

M ^ {{*}} M = V \ Sigma ^ {{*}} U ^ {{*}} \, U \ Sigma V ^ {{*}} = V (\ Sigma ^ {{*}} \ Sigma ) V ^ {{*}} \,

és

MM ^ {{*}} = U \ Sigma V ^ {{*}} \, V \ Sigma ^ {{*}} U ^ {{*}} = U (\ Sigma \ Sigma ^ {{*}}) U ^ {{*}} \,

E kapcsolatok jobb oldala a bal oldal sajátérték-bontását írja le. Tehát az egyes $M-$ értékek, amelyek nem nulla értékek, modulusának négyzete megegyezik az $M * M$ és az $MM *$ megfelelő nulla érték nélküli sajátértékének modulusával . Ezenkívül az $U$ oszlopok (a szinguláris vektorok balra) a sajátvektorai , a V oszlopai pedig (a jobb oldali szinguláris vektorok) a tiszta $M$ $*$ $M$ vektorok . $MM ^ {{*}}$

Geometriai értelmezés

Mivel $U$ és V egységesek, tudjuk, hogy az oszlopok u 1 , ..., u m a $U$ képezik ortonormális alapján K m , és az oszlopok v 1 , ..., v n a V alkotnak ortonormált alapján K n (ezeken a tereken lévő skaláris szorzathoz képest).

A T : K n → K m lineáris transzformáció , amely minden egyes x vektorhoz társítja Mx-et , viszonylag egyszerű kifejezéssel rendelkezik ezekben az ortonormális bázisokban: T ( v i ) = σ i u i , i = 1, ..., min ( m , n ), ahol σ i a i i- edik átlós együtthatója, és T ( v i ) = 0 i > min ( m , n ) esetén.

A szinguláris értékbontási tétel geometriai tartalma a következőképpen foglalható össze: bármely lineáris T térképhez : K n → K m , találhatunk K n számára ortonormális és K m ortonormális alapot úgy, hogy T asszociáljon az i - th alapján vektor a K n pozitív többszöröse a i -edik alapján vektor K m , a fennmaradó vektorokat, amelyek a keret 0. ezekben az alapanyagokban, az alkalmazás T így képviseli egy diagonális mátrix , amelynek együtthatók valósak pozitív.

Statisztikai értelmezés

Ez a bontás értelmezhető egy adatsor statisztikai vizsgálatának szellemében is . Ezután az $U$ fő oszlopai a vizsgálati halmaz trendjeit képviselik (az $U$ vektorai a halmaz „legnagyobb variációs irányait” képviselik). A Σ átlós értékei ekkor analógak az „ energiával ” vagy „reprezentativitással”, amelyek súlyozzák ezeket a viselkedéseket; a statisztikai halmaz rendezésével annál gyorsabban csökkennek.

Megfontolhatjuk például adatbányászat szempontjából , hogy az egész „fontos” információja az, amely markánsabb szerkezetet mutat. Ezután a $Σ$ átlójának egy bizonyos indexen kívüli törlésével , majd a kezdő mátrix rekonstruálásával szűrt adatokat kapunk, amelyek a kezdő halmaz domináns információját képviselik. Ezzel egyenértékűnek tekinthető egy bizonyos küszöbértéknél alacsonyabb energia nulladat.

Így az SVD lehetővé teszi egy empirikus modell felépítését , anélkül, hogy elméletet alapozna meg , annál pontosabban, ahogy a kifejezéseket beillesztik.

Az is lehetséges, hogy az első adatsor egyes vektorainak bázisát felhasználva rekonstruáljunk egy másik adathalmazt kisebb-nagyobb pontossággal, a kettő közötti hasonlóság meghatározása érdekében. Ennek az elvnek megfelelően alakultak ki arcbontási, felismerési és rekonstrukciós rendszerek.

A módszer hatékonysága különösen attól függ, hogy az információt hogyan mutatják be neki. Egy arc példájánál , ha egy fénykép különféle képpontjainak fényességét naivan használjuk az egyes vektorok bázisának felépítésére, akkor nehéz lesz ugyanazt az arcot kissé eltérő pózban rekonstruálni (vagy ha a arc változott): a pixelek változtak - néha nagyon -, de az implicit információk (azaz az arc) nem. Ezekben az alkalmazási területeken előnyös az adatok térbeli feldolgozása, ezért hozzáadunk egy 3D-s felismerési rendszert, amely lehetővé teszi a megfigyelt variációk "magyarázatát" az összekapcsolásukkal és az ismert adatokkal való összekapcsolását.

Történelem

A szinguláris értékbontást eredetileg a differenciálgeometriát tanulmányozó matematikusok fejlesztették ki , és meg akarták állapítani, hogy az egyik valós bilináris forma megegyezhet-e a másikkal a két érintett tér független ortogonális transzformációival.

Eugenio Beltrami és Camille Jordan 1873-ban, illetve 1874-ben egymástól függetlenül fedezték fel, hogy a mátrix formában ábrázolt bilinear formák egyes értékei az inverziók teljes készletét alkotják az ortogonális szubsztitúciót végző bilinear formák számára.

James Joseph Sylvestert is érdekelte a négyzet alakú valós mátrixok 1889-es egyedi értékbontása, nyilvánvalóan Beltrami és Jordan munkájától függetlenül. Sylvester az egyes értékeknek egy A- mátrix "kanonikus szorzóinak" nevét adta .

A bomlás felfedezésének eredete a negyedik matematikus, Autonne, 1915-ben . Ezt az eredményt poláris bomlás útján éri el.

A négyszögletes és összetett mátrixok egyedi értékbontásának első bizonyítékát Eckart és Young tulajdonítja, 1936-ban.

1907-ben Erhard Schmidt meghatározta az integrált operátorok egyes értékeinek analógját (amelyek bizonyos körülmények között kompaktak ); úgy tűnik, hogy nem ismerte a véges dimenziós mátrixok egyesértékeinek párhuzamos munkáját . Ezt az elméletet Émile Picard francia matematikus fejlesztette tovább 1910-ben, aki az általa megjegyzett modern "egyes értékek" kifejezés eredete . $\ sigma _ {k}$

1965 előtt nem volt ismert hatékony módszer a bomlás kiszámítására. Gene H. Golub és William Kahan abban az évben javaslatot tett egy első algoritmusra, majd 1970-ben Golub és Christian Reinsch közzétette a Golub-Kahan algoritmus egy változatát, amely a mai napig a legszélesebb körben használatos.

Ennek a bontásnak a két, három vagy N dimenzióra történő általánosítása továbbra is aktív kutatás tárgya, mivel számos területen kiemelkedő érdeklődésnek bizonyul.

Változatok

SVD / ICA

Általános gyakorlat, hogy a szinguláris értékbontás eredményeit összekapcsolják a független komponenselemzés (vagy ICA) eredményeivel. A kettő kombinációját használó algoritmusokat általában SVD / ICA- nak hívják . Valójában a független komponensekben végzett elemzés figyelembe veszi azokat a sorrendeket, amelyek nagyobbak vagy egyenlőek mint 2, és amelyeket az egyes számok bomlása elhanyagol.

Általános bontás

A módszer a generalizált szinguláris érték felbontás , vagy GSVD , kiterjeszti a koncepció a szinguláris érték dekompozíció alkalmazásával kvadratikus félig szabványok és alkalmazza a lineáris rendszerek .

Ha egy m × n méretű A mátrixot és egy valós vagy komplex p × n méretű B mátrixot adunk meg, általános bomlásuk:

A = U \ Sigma _ {1} [0, R] Q ^ {{*}}

és

B = V \ Sigma _ {2} [0, R] Q ^ {{*}}

a $U$ , $V$ és $Q$ a egységes mátrixok és $R$ egy felső háromszög mátrix, nonsingular, négyzet r × r , kiválasztásával $r \leq n$ a rangot az $[ A * , B * ]$ .

Ezenkívül $Σ 1$ és $Σ 2$ m × r, illetve p × r mátrix , nulla mindenhol, kivéve főátlójukat, amely az $α i$ és $β i$ valósokat tartalmazza , így:

{\ displaystyle 0 \ leq \ alpha _ {i}, \ beta _ {i} \ leq 1 \ quad {\ textrm {et}} \ quad \ alpha _ {i} ^ {2} + \ beta _ {i} ^ {2} = 1}

A kapcsolatok analógak az egyes értékekkel. A konkrét, de fontos esetben, ha $B$ jelentése tér és invertálható, ezek azok a szinguláris értékek, $U$ és $V$ ezután a szinguláris vektorok a mátrix $AB$ $-1$ . $\ sigma _ {i} = \ alfa _ {i} / \ beta _ {i}$

2D bomlás

Lehetséges kiterjeszteni a szinguláris értékbontás fogalmát komplex mátrixokra, vagy ezzel egyenértékű módon a 2D vektorokból álló mátrixokra. A számítás közel áll az egyszerű szinguláris értékbontáshoz. A bomlásról egyes számokban 2D vagy 2DSVD beszélünk .

Ami az egyszerű esetet illeti, vannak speciális algoritmusok, amelyek közelítik az alacsony rangú mátrixok halmazát, például időjárási képek vagy térképek.

Legyen $X = ( x 1 , ..., x n )$ valós számok halmaza (azaz 1D vektorok). A szinguláris értékbontáshoz megalkotjuk a kovariancia mátrixot és a Gram mátrixot:

{\ displaystyle F = XX ^ {T} \, \ G = X ^ {T} X}

Ezután kiszámítjuk sajátvektoraikat $U = ( u 1 , ..., u n )$ és $V = ( v 1 , ..., v n )$ . Mivel : $VV ^ {T} = I, UU ^ {T} = I$

X = UU ^ {T} XVV ^ {T} = U (U ^ {T} XV) V ^ {T} = U \ Sigma V ^ {T}

Az $U$ és $V$ csak a K fő sajátvektorainak megtartásával , ezáltal az $X$ mátrix alacsony sorrendű közelítésének megszerzésével . A 2DSVD algoritmusokhoz 2D mátrixokkal dolgozunk, vagyis mátrixok halmazával $($ $X$ $1$ $, ...,$ $X$ $n$ $)$ . Megalkotjuk a sor-és oszlop-oszlop kovariancia mátrixokat :

{\ displaystyle F = \ sum _ {i} X_ {i} X_ {i} ^ {T} \, \ G = \ sum _ {i} X_ {i} ^ {T} X_ {i}}

Ehhez ugyanúgy jár el, mint a vektorbontás, és kiszámítja saját $U$ és $V$ vektorukat . Megközelítjük az $X i-t$ :

X_ {i} = UU ^ {T} X_ {i} VV ^ {T} = U (U ^ {T} X_ {i} V) V ^ {T} = UM_ {i} V ^ {T}

a szinguláris értékekre történő bontással azonos módszerrel.

Így a $( X 1 , ..., X n )$ közelítést kapjuk a függvény alapján :

J = \ összeg _ {i} \ balra | X_ {i} -LM_ {i} R ^ {T} \ jobbra | ^ {2}

A 2DSVD algoritmusokat főleg a tömörítésben és a képábrázolásban használják . Az SVD használata a képtömörítéshez azonban optimálisnak bizonyult a DCT- hez képest , különösen azért, mert a képadatok mellett maga a transzformáció továbbítása is kötelező. Szerepe a tömörítés területén valójában marginális.

3D bomlás

A kibontott mátrixok használatának mérlegelésével kiterjeszthetjük a szinguláris értékek bontását háromdimenziós esetekre vagy 3DSVD-re . Ilyen algoritmusokat használnak a szeizmológiában , a meteorológiában és az akusztikában , ahol gyakran szükséges a 3D (vagy 2D időjárástól függő) adatok elemzése.

Csökkent bomlások

A felhasználások során meglehetősen ritka, hogy a szinguláris értékbontás teljes formáját kell használni, beleértve a teljes magbontást egység formában. Valójában általános, gyorsabb és memória szempontjából olcsóbb az SVD kisebb verzióinak használata. A következő bontások érvényesek az r rangú m × n mátrixokra .

SVD "rendben"

M = U_ {n} \ Sigma _ {n} V ^ {{*}} \,

Csak az n oszlop vektorok $U$ megfelelő sorvektorait a V * számítjuk. Az $U$ fennmaradó oszlopvektorait nem számoljuk, ami nagy mennyiségű számítást takarít meg, ha . A mátrix U n tehát m × n , Σ n jelentése diagonális n × n és V jelentése n × n . $m \ gg n$

Az első lépés a számítás egy „finom” SVD a QR bomlása M , amely lehet optimalizálni az . $m \ gg n$

"Kompakt" SVD

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

Csak az R oszlop vektorok $U$ és az R sorvektorait a V * megfelelő a nem zéró szinguláris értékek Σ r számítjuk. Gyorsabban kapunk eredményt, mint a „finom” SVD-vel, ha . Az U r mátrix tehát m × r , Σ r átlós r × r és V r * r × n . $n \ gg r$

SVD "csonka"

{\ tilde {M}} = U_ {t} \ Sigma _ {t} V_ {t} ^ {*}

Csak a T oszlop vektorok $U$ , és a t sorvektorait a V * megfelelő t legnagyobb szinguláris értékek Σ r számítjuk. Még gyorsabb számítás, mint a "kompakt" SVD . Az U t mátrix tehát m × t , Σ t átlós t × t és V t * t × n . $r \ gg t$

Ez a „csonka” bontás azonban már nem az eredeti M mátrix pontos lebontása , hanem a kapott mátrix ,, az M legjobb közelítése, amelyet egy t rangú mátrix hoz létre , az R euklideszi normáinak alárendelt operátor normáihoz. n és R m . ${\ tilde {M}}$

Szabványok

Ky rajongói szabványok

Az összeg a k legnagyobb szinguláris értékeinek H egy szabvány a vektortér mátrixok, az úgynevezett normál Ky Fan vagy szabványos k az M .

A Ky ventilátor normák közül az első, a Ky ventilátor 1. norma megegyezik az M, mint lineáris operátor operátor normájával , a K m és K n euklideszi normák szerint . Más szóval, Ky Fan norma 1 a operátornorma által indukált euklideszi belső termék szabvány L 2 . Emiatt operátor 2-nek is nevezik. Könnyen ellenőrizhető a Ky Fan 1-es norma és az egyes számok közötti kapcsolat. Ez általában igaz egy korlátozott M operátorra egy (potenciálisan végtelen) Hilbert tér felett:

\ | M \ | = \ | M ^ {*} M \ | ^ {{{\ frac {1} {2}}}}.

Mindazonáltal, abban az esetben, mátrixok, ( M * M ) ½ egy normális mátrix , így || M * M || ½ az ( M * M ) ½ legnagyobb sajátértéke , tehát az M legnagyobb egyesértéke .

Ky Fan utolsó normája, amely megegyezik az összes egyes érték összegével, a || által meghatározott nyomnorm M || = Tr ( M * M ) ½ .

Figyelembe vesszük az n sorrendű mátrixok algebrájában meghatározott lineáris formát :

u_ {X}: Y \ - {{\ rm {Tr}}} (^ {t} YX)

Figyelembe vesszük a mátrixok spektrális normáját , és a kettős normát az alábbiak szerint definiáljuk : $\ | \ \ | _ {2}$ $u_ {X}$

\ | u_ {X} \ | = \ sup _ {{\ | Y \ | _ {2} = 1}} | {{\ rm {Tr}}} (^ {t} YX) |

Ezután könnyen ellenőrizhető, hogy ez a kettős norma valójában X fent meghatározott nyoma normája . Sőt, ez a norma algebrai norma.

Hilbert-Schmidt szabvány

Az egyes értékek az operátorok terének másik normájához kapcsolódnak. Hilbert - Schmidt skaláris szorzatát vesszük figyelembe az n × n mátrixokon , amelyet < M , N > = Tr N * M határoz meg . Ekkor az indukált norma || M || = < M, M > ½ = (Tr M * M ) ½ . Mivel a nyom hasonlósági invariáns, ez azt jelenti, hogy:

\ | M \ | = \ balra (\ sum s_ {i} ^ {2} \ jobbra) ^ {{{\ frac {1} {2}}}}

ahol s i H egyesértékei . Ez az úgynevezett Frobenius norma , szabványos 2 Schatten vagy szabványos Hilbert-Schmidt a M . Azt is megmutatjuk, hogy ha:

\, M = (m _ {{ij}})

akkor ez a norma egybeesik:

{\ biggl (} \ sum _ {{ij}} | m _ {{ij}} | ^ {2} {\ biggr)} ^ {{{{\ frac {1} {2}}}}

Korlátozott operátorok a Hilbert-tereken

A $H = U Σ V *$ faktorizáció meghosszabbítható, mint korlátozott M operátor a Hilbert H téren . Általában bármely korlátozott M operátor esetében létezik $U$ részleges izometria , V egységvektor , mérési tér (X, μ) és pozitív mérhető f , amely:

\; M = UT_ {f} V ^ {*},

ahol a szorzás f on L 2 ( X , μ ). $T_ {f}$

Ez a mátrixesethez használt lineáris algebra argumentumon dolgozva mutatható ki . VT f V * az egyedi pozitív gyökere M * M , által adott funkcionális elemzése a Borel , az önadjungált operátorok. Az oka annak, hogy az $U-nak$ nem kell egységesnek lennie, összefügg azzal a ténnyel, hogy a véges dimenziós esettől eltérően, ha egy U 1 izometriát egy nem triviális maggal adunk meg , akkor egy U 2 izometria létezik, amely:

{\ begin {pmatrix} U_ {1} \\ U_ {2} \ end {pmatrix}}

egységes operátor.

Mivel a mátrixok esetében az egyedi értékbontás egyenértékű az operátorok poláris felbontásával, ezt átírhatjuk a következő formában:

M = UV ^ {*} \ cdot VT_ {f} V ^ {*}

és vegye észre, hogy az UV * még mindig részleges izometria, amíg a VT f V * pozitív.

Egyedülálló értékek és kompakt operátorok

Kiterjeszteni a fogalom egyes érték és egyedülálló vektorok esetében szereplők , meg kell korlátozni magunkat kompakt operátorok a Hilbert terek . Felidézünk néhány hasznos tulajdonságot:

Kompakt szereplők Banach , és ezért Hilbert terek , van egy diszkrét spektrum ;
Ha T kompakt, akkor nem nulla spektrumának összes λ értéke sajátérték;
A kompakt önadjektív operátort sajátvektorai átlósíthatják;
Ha M kompakt, akkor M * M is.

Használata diagonalizáció, az egység kép a pozitív négyzetgyökét M , jele T F , van egy ortonormáiis család sajátvektorok { e i }, megfelelő szigorúan pozitív sajátértékei { σ i }. Minden ψ ∈ H ,

\; M \ psi = UT_ {f} V ^ {*} \ psi = \ sum _ {i} \ langle UT_ {f} V ^ {*} \ psi, Ue_ {i} \ rangle Ue_ {i} = \ összeg _ {i} \ sigma _ {i} \ langle \ psi, Ve_ {i} \ rangle Ue_ {i},

amikor a sorozat konvergál általában a H . Észrevesszük, hogy ez a kifejezés a véges dimenzió esetében közel áll ahhoz.

Az σ i- t H- nek egyes értékeinek nevezzük . Az { U e i } és a { V e i } analóg a balra és jobbra eső egyes számú vektorokkal, M-rel .

Használ

Az ál-inverz kiszámítása

A szinguláris értékekben történő bontás lehetővé teszi egy mátrix ál-inverzének kiszámítását . Valóban, a pszeudo-inverzét mátrix M ismerve annak felbontása szinguláris értékek $M = U Σ V *$ , adja meg:

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

ahol Σ + a p ál inverzje, ahol bármely nem nulla együtthatót inverzére cserélünk. Maga az ál-inverz megoldja a legkisebb négyzetek módszert .

Kép, rang és mag

A szinguláris értékbontás másik felhasználása a kép és az M mátrix magjának explicit ábrázolása . Jobb szinguláris vektorok megfelelő nulla szinguláris értékeinek M generál a nucleus M . A bal oldali szinguláris vektorok, amelyek az M nem nulla szinguláris értékeinek felelnek meg, létrehozzák a képét.

Ezért a rangsorban az M száma megegyezik az nem nulla szinguláris értékeinek M . Ezenkívül az M , $M * M$ és az $MM *$ rangja megegyezik. $M * M$ és $MM *$ ugyanazok a nullától eltérő sajátértékek.

A lineáris algebrában numerikusan meg lehet jósolni a mátrix tényleges rangját, mivel a kerekítési hibák egyébként kicsi, de nem nulla értékeket generálhatnak, torzítva a mátrix rangjának kiszámítását.

Mátrix-közelítések, Eckart Young tétele

Néhány gyakorlati alkalmazásokat kell, hogy megoldja a problémát a közelítő mátrixok $M$ egy mátrix , amelynek adott rangot egyenlő r . Abban az esetben, ha megpróbáljuk minimalizálni az spektrumnorma (vagy a Frobenius) értelmében vett távolságot az $M$ között, és miközben megtartjuk , megjegyezzük, hogy a megoldás az $M$ szinguláris értékekben való bomlása , vagyis : ${\ tilde {M}}$ ${\ tilde {M}}$ ${\ mbox {rg}} ({\ tilde {M}}) = r$

{\ tilde {M}} = U {\ tilde {\ Sigma}} V ^ {*}

A egyenlő $Σ$ , kivéve, hogy az csupán a legnagyobb szinguláris értékek, a többi tagot helyébe 0. Itt a bizonyíték: ${\ tilde {\ Sigma}}$ $r$

Demonstráció

Az egyszerűség kedvéért csak négyzetmátrixokra korlátozódunk. A hármas normaszimbólum a spektrális norma képviseletére szolgál. Elsőként Eckart Young tételét igazoljuk a spektrális normára. Az általánosság elvesztése nélkül feltételezhetjük, hogy A átlós mátrix, ezért $U$ és V az identitásmátrix. Ezért $A = Σ értéket$ adunk meg . A diagonális feltételei A jelöljük $σ i$ . Csökkenő sorrendbe vannak rendezve. Így van

\ sigma _ {1} \ geq \ sigma _ {2} \ geq \ ldots \ geq \ sigma _ {n}

Bármely r rangú B mátrixot figyelembe vesszük . Úgy véljük, a vektor altér E az által generált vektorokkal $($ $e$ $1$ $, ...,$ $e$ $r$ $+1$ $)$ , ahol minden egyes $e$ $i$ az a vektor, $(0, ..., 0,1,0, ..., 0)$ nem nulla rangot i . Ennek a vektoros altérnek dimenziója r +1. Mivel a B mátrix r rangú , B magja n - r rangú . Egyszerű dimenzió-érveléssel E és B magja metszéspontja nem nulla. E kereszteződéshez tartozó normalizált x vektort tekintünk . Meghatározzuk Akkor van ${\ mathbb {R}} ^ {n}$ $x = \ sum _ {{i = 1}} ^ {{r + 1}} x_ {i} e_ {i}$

{\ displaystyle (AB) x = Ax-0 = \ Sigma x = \ sum _ {i = 1} ^ {r + 1} \ sigma _ {i} x_ {i} e_ {i}.}

Mivel az $e i$ vektorok ortogonálisak és normalizálódnak, megkapjuk:

\ | (AB) x \ | ^ {2} = \ sum _ {{i = 1}} ^ {{r + 1}} \ sigma _ {i} ^ {2} x_ {i} ^ {2} \ geq \ sigma _ {{r + 1}} ^ {2} \ szor 1.

A spektrális norma meghatározása alapján az ember arra következtet, hogy bármi is legyen a B mátrix , van

| \ | AB \ || \ geq \ sigma _ {{r + 1}}

A bizonyítást választással zárjuk le . n aztán könnyen megfigyeli azt . ${\ displaystyle B = \ Sigma '= {\ rm {diag}} (\ sigma _ {1}, \ ldots, \ sigma _ {r}, 0, \ ldots, 0)}$ $| \ | AB \ || = \ sigma _ {{r + 1}}$

Tehát $B = Σ '$ az a rang r mátrix, amely minimalizálja az A - B spektrális normáját .

A Frobenius-norma bizonyítását illetően ugyanazokat a jelöléseket tartjuk fenn, és ezt észrevesszük

| \ | \ \ || \ leq \ | \ \ | _ {F}

A bizonyítás ekkor hasonló.

Így az r rang mátrixa az $M$ legjobb közelítése a Frobenius (vagy spektrális) norma értelmében, amikor . Ezenkívül egyes értékei megegyeznek az $M$ első legnagyobb r - $jével$ . ${\ tilde M}$ $\ sigma _ {i} = s_ {i} \ quad (i = 1, \ cdots, r)$

Alkalmazás az automatikus nyelvfeldolgozáshoz

A szinguláris értékbontás egyik fő alkalmazása a természetes nyelv feldolgozásában a látens szemantikai elemzés (LSA vagy, angol látens szemantikai elemzés ), a vektor-szemantika módszere . Ennek a folyamatnak az a célja, hogy elemezze a dokumentumok halmaza és az azokban található kifejezések vagy kifejezések közötti kapcsolatokat azáltal, hogy létrehozza a különböző elemek közös fogalmait.

1988-ban szabadalmaztatta, látens szemantikai indexelésnek (LSI) is nevezik. Itt van ennek az algoritmusnak az elve rövid leírása.

Először egy mátrixot állítanak össze, amely a kifejezések különböző előfordulásait (előre meghatározott szótárból vagy dokumentumrészletekből) jeleníti meg, a dokumentumok függvényében. Vegyünk például három irodalmi művet:

1. dokumentum: "Szeretem a Wikipédiát"
2. dokumentum: "Szeretem a csokoládét"
3. dokumentum: "Utálom a csokoládét"

Ekkor az ezekhez a dokumentumokhoz társított M mátrix a következő lesz:

	én	én	rajong	gyűlölt	a	Wikipédia	csokoládé
1. dokumentum	1	0	1	0	0	1	0
2. dokumentum	1	0	1	0	1	0	1
3. dokumentum	0	1	0	1	1	0	1

Végül egyes szavakat radikálisra vagy egyenértékű szóra redukálhatunk, sőt elhanyagolhatunk bizonyos kifejezéseket, amelyek túl rövidek ahhoz, hogy jelentésük legyen; a mátrix ekkor tartalmaz I , imádok , utálok , Wikipédiát , csokoládét . Az együtthatók (itt 1 vagy 0) általában nem számítanak számot, hanem a dokumentumban előforduló kifejezés előfordulásainak számával arányos értékek, a tf ( kifejezés gyakorisága ) súlyozásáról beszélünk . Más súlyozás, például az idf ( inverz dokumentum gyakorisága vagy TF-IDF ) is érintett lehet.

Ekkor M formájú lesz:

{\ begin {matrix} és {\ textbf {term}} _ {j} \\ & \ downarrow \\ {\ textbf {document}} _ {i} ^ {T} \ rightarrow & {\ begin {pmatrix} x_ {{1,1}} és \ pontok & x _ {{1, n}} \\\ vdots & \ ddots & \ vdots \\ x _ {{m, 1}} és \ pontok és x _ {{m , n}} \ \\ end {pmatrix}} \ end {matrix}}

Dolgozhatunk M transzpozíciójával is , amelyet N jelöl . Ekkor az N sorvektorai megfelelnek egy adott kifejezésnek, és hozzáférést biztosítanak az egyes dokumentumokhoz tartozó "kapcsolatukhoz":

{\ textbf {term}} _ {i} ^ {T} = {\ begin {bmatrix} x _ {{i, 1}} & \ dots & x _ {{i, n}} \ end {bmatrix}}

Ugyanígy az N mátrix oszlopa egy adott dokumentumot képvisel, és hozzáférést biztosít az egyes terminusokhoz való viszonyához:

{\ textbf {document}} _ {j} = {\ begin {bmatrix} x _ {{1, j}} \\\ vdots \\ x _ {{m, j}} \ end {bmatrix}}

Két dokumentum feltételei közötti összefüggést skaláris szorzatuk végrehajtásával érhetjük el . A szorzat kiszámításával kapott szimmetrikus mátrix mind ezeket a ponttermékeket tartalmazza. Az S $($ $i$ $,$ $p$ $)$ indexű eleme a következő terméket tartalmazza: $S = NN ^ {T}$

S _ {{i, p}} = {\ textbf {term}} _ {i} ^ {T} {\ textbf {term}} _ {p} = {\ textbf {term}} _ {p} ^ { T} {\ textbf {term}} _ {i}

Hasonlóképpen, a szimmetrikus mátrix az összes dokumentum között a ponttermékeket tartalmazza, amely megadja a korrelációt a kifejezések szerint: $Z = N ^ {T} N$

Z _ {{j, q}} = {\ textbf {dokumentum}} _ {j} ^ {T} {\ textbf {dokumentum}} _ {q} = {\ textbf {dokumentum}} _ {q} ^ { T} {\ textbf {dokumentum}} _ {j}

Az egyik most kiszámítja az $N$ mátrix szinguláris bontását , amely a következő mátrixokat adja:

M = U \ Sigma V ^ {T}

Ekkor a korrelációs mátrixok a következők lesznek:

{\ begin {mátrix} S & = & (U \ Sigma V ^ {T}) (U \ Sigma V ^ {T}) ^ {T} = (U \ Sigma V ^ {T}) (V ^ {{ T ^ {T}}} \ Sigma ^ {T} U ^ {T}) = U \ Sigma V ^ {T} V \ Sigma ^ {T} U ^ {T} = U \ Sigma \ Sigma ^ {T} U ^ {T} \\ Z & = & (U \ Sigma V ^ {T}) ^ {T} (U \ Sigma V ^ {T}) = (V ^ {{T ^ {T}}} \ Sigma ^ {T} U ^ {T}) (U \ Sigma V ^ {T}) = V \ Sigma ^ {T} U ^ {T} U \ Sigma V ^ {T} = V \ Sigma ^ {T} \ Sigma V ^ {T} \ end {mátrix}}

A mátrix $U$ tartalmazza sajátvektorai a S , a mátrix V tartalmazza azokat a Z . Ezután:

{\ begin {matrix} & ({\ textbf {document}} _ {j}) &&&&&&& (\ widehat {{\ textbf {document}} _ {j})} \\ & \ downarrow &&&&&&& \ downarrow \\ ({ \ textbf {term}} _ {i} ^ {T}) \ rightarrow & {\ begin {pmatrix} x _ {{1,1}} & \ dots & x _ {{1, n}} \\\\ \ vdots & \ ddots & \ vdots \\\\ x _ {{m, 1}} & \ dots & x _ {{m, n}} \\\ end {pmatrix}} & = & (\ widehat {{ \ textbf {term}} _ {i}} ^ {T}) \ rightarrow & {\ begin {pmatrix} {\ begin {bmatrix} \, \\\, \\ {\ textbf {u}} _ {1} \\\, \\ \, \ end {bmatrix}} \ dots {\ begin {bmatrix} \, \\\, \\ {\ textbf {u}} _ {l} \\\, \\\, \ end {bmatrix}} \ end {pmatrix}} & \ cdot & {\ begin {pmatrix} \ sigma _ {1} & \ dots & 0 \\\ vdots & \ ddots & \ vdots \\ 0 & \ dots & \ sigma _ {l} \\\ end {pmatrix}} & \ cdot & {\ begin {pmatrix} {\ begin {bmatrix} && {\ textbf {v}} _ {1} && \ end {bmatrix}} \\ \ vdots \\ {\ begin {bmatrix} && {\ textbf {v}} _ {l} && \ end {bmatrix}} \ end {pmatrix}} \\ & M &&& U && \ Sigma && V ^ {T} \ end {mátrix}}

Ezután a szinguláris értékek kiválaszthatók a mátrix tetszőleges k rangú „közelítésének” megszerzéséhez , amely lehetővé teszi az adatok többé-kevésbé pontos elemzését. $\ sigma _ {1}, \ dots, \ sigma _ {l}$

Inverz kinematika

A robotikában az inverz kinematika problémája , amely lényegében abban rejlik, hogy "hogyan kell elmozdulni egy pont eléréséig" tudható meg, szinguláris értékekre bontva.

A probléma megállapítása

Mondhatjuk - ez egy nagyon általános modellt - a robot álló csuklós kar, indexelt i , alkotó szög θ i közöttük, egy síkban. Jelölje X a vektor képviselő a helyzet a „vége” ez a lánc a karok, amelyek a gyakorlatban egy bilincs , egy tűt , egy mágnes ... A probléma az lesz, hogy határozza meg a vektort Θ , amely tartalmazza az összes θ i , így X egyenlő egy adott X 0 értékkel .

Felbontás

Az X jakobiusát az alábbiak szerint definiáljuk :

{\ displaystyle J = {\ frac {\ részleges {\ textbf {X}}} {\ részleges \ mathbf {\ Theta}}}}

Ezután:

{\ displaystyle {\ dot {\ textbf {X}}} = J {\ dot {\ mathbf {\ Theta}}}}

Ha J jelentése invertálható (ami a gyakorlatban mindig ez a helyzet), akkor elérhetik a származék θ :

{\ displaystyle {\ dot {\ mathbf {\ Theta}}} = J ^ {- 1} {\ dot {\ textbf {X}}}}

Ha J nem invertálható, akkor is használhatjuk az ál-inverz fogalmat . Ennek ellenére a használata nem garantálja az algoritmus konvergenciáját, ezért szükséges, hogy a jakobiusz nulla legyen a csökkentett számú pontban. Megjegyezve $( U , Σ , V )$ a szinguláris érték felbontás a J , az inverz (a pszeudo-inverz, ha J jelentése nem invertálható) a J adja meg:

J ^ {{- 1}} = V \ Sigma ^ {{- 1}} U ^ {T} \,

(visszafordítható eset);

J ^ {{+}} = V \ Sigma ^ {{+}} U ^ {T} \,

(ál-invertálható eset).

Megemlítettük Σ + a nem nulla egyes szám inverzét tartalmazó átlós mátrixot. A következőkben, a jelölést J -1 utalnak megkülönböztetés nélkül az inverz vagy pszeudo-inverzét J .

A J oszlopvektorainak kiszámítása a következőképpen hajtható végre:

Jelölje X i a helyzet a közös i ;
E z-vel jelöljük az egységvektort az ízület forgástengelyével megegyező irányban;

Szóval . $J_ {i} = {\ textbf {e}} _ {z} \ ék \ bal ({\ textbf {X}} _ {0} - {\ textbf {X}} \ jobb)$

Ezután diszkretizálhatjuk az egyenletet azáltal, hogy feltesszük:

\ Delta {\ textbf {X}} = {\ textbf {X}} _ {0} - {\ textbf {X}}

{\ displaystyle \ Delta \ mathbf {\ Theta} = J ^ {- 1} \ Delta {\ textbf {X}}}

És ha minden iterációnál hozzáadunk Δ Θ- t Θ-hez , majd Δ X és Δ Θ újraszámításával fokozatosan elérjük a kívánt megoldást.

Egyéb felbontás

A Δ Θ megszerzésére egyébként J szinguláris értékbontását is lehet használni :

{\ displaystyle \ Delta \ mathbf {\ Theta} = J ^ {- 1} \ Delta {\ textbf {X}}}

Ha balra egymás után szorozzuk J-vel, majd átültetjük, és végül J T J egyesérték-bontását használjuk , akkor:

{\ displaystyle J \ Delta \ mathbf {\ Theta} = \ Delta {\ textbf {X}}}

{\ displaystyle J ^ {T} J \ Delta \ mathbf {\ Theta} = J ^ {T} \ Delta {\ textbf {X}}}

{\ displaystyle V \ Sigma ^ {2} V ^ {T} \ Delta \ mathbf {\ Theta} = J ^ {T} \ Delta {\ textbf {X}}}

Vagy zárva:

{\ displaystyle \ Delta \ mathbf {\ Theta} = \ balra (V \ Sigma ^ {- 2} V ^ {T} J ^ {T} \ jobbra) \ Delta {\ textbf {X}}}

Egyéb példák

A szinguláris értékbontás gyakori alkalmazása a jel két további altérre osztása, például egy "jel" és egy zaj altérre . Az egyes számokban történő bontást sokat használják a mátrixok inverziójának tanulmányozásában, nagyon praktikusak a szabályozás módszereiben . Széles körben használják statisztikákban , jelfeldolgozásban , minták felismerésében és a természetes nyelvek számítógépes feldolgozásában is.

A meteorológiában ezen algoritmuson keresztül nagy mátrixok vannak lebontva, például a Lanczos algoritmus esetében.

A geológiai és szeizmikus vizsgálat , amelynek gyakran köze van a zajos adatokhoz, szintén felhasználja ezt a bomlást és annak többdimenziós változatait a kapott spektrumok "tisztításához". Bizonyos számú ismert minta alapján egyes algoritmusok egyes számbontás révén dekonvolúciót hajthatnak végre egy adatkészleten.

Az egyes számokat is automatikusan használják . Lehetővé teszik az átviteli függvény erősítési elvének általánosítását egy több bemenetű, több kimeneti rendszerre . A szinguláris értékeket használjuk a számításban a norma H ∞ fejlesztésére egy érdekében H ∞ .

Az SVD kiszámítása

A mátrix egyedi értékekre történő bontásának explicit, analitikus kiszámítása általában nehéz. Speciális algoritmusokat használnak, különösen az alkalmazásokban.

A LAPACK könyvtár DGESVD eljárása jelenlegi megközelítést javasol a mátrix szinguláris értékekre történő bontásának kiszámításához. Ha a mátrixnak több sora van, mint oszlopának, akkor először QR-bontást hajtanak végre . Az R tényezőt ezután kétirányú alakúra csökkentjük . Ehhez Householder transzformációkat felváltva hajthatunk végre az oszlopokon és a mátrix sorain. Ezután a szinguláris értékeket és a szinguláris vektorokat a DBDSQR eljárással kétirányú QR típusú iteráció végrehajtásával találjuk meg.

A GNU Tudományos Könyvtára három lehetőséget kínál: a Golub-Reinsch algoritmust, a módosított Golub-Reinsch algoritmust (gyorsabb a mátrixoknál, ahol sokkal több a sor, mint az oszlop) és a Jacobi ortogonalizációt.

Megjegyzések és hivatkozások

(en) Ez a cikk részben vagy egészben a Wikipedia angol nyelvű cikkéből származik, „ Egyedüli értékek bomlása ” címmel ( lásd a szerzők listáját ) .

(in) Muller Magaia, Herbst: " Szinguláris értékbontás, sajátfelületek és 3D rekonstrukciók ", 2004.
(in) GW Stewart: "A lebomló debütáló egyes értékek története" , Marylandi Egyetem, 1992.
L. Autonne "On hypohermitiennes mátrixok, és az egységes mátrixok" 1915-ben.
E. Schmidt, " Zur Theorie der linearen und nichtlinearen Integralgleichungen ", 1907.
GH Golub, W. Kahan, " A mátrix egyesértékeinek és peusoinverseinek kiszámítása ", 1965.
GH Golub, C. Reinsch: „ Szinguláris értékbontás és legkisebb négyzetek megoldása ”, 1970.
Az sem ritka, hogy ellenezzük őket, mivel ellentmondásos eredményeket adhatnak. Ebben a témában az EEG-k témájában angol nyelven olvasható : Drozd, Husar, Nowakowski, Henning: „ A kiváltott potenciálok detektálása SVD- és ICA-alapú statisztikai modellekkel , Engineering in Medicine and Biology Magazine, IEEE, 2005.
Sven Ole Aase, John Håkon Husøy és P. Waldemar, „ Az SVD-alapú képkódoló rendszerek kritikája ”, IEEE áramkörökről és rendszerekről szóló nemzetközi szimpózium ,1999
(in) A szabadalmi bejelentés Scott Deerwester, Susan Dumais, George Furnas, Richard Harshman, Thomas Landauer, Karen Lochbaum és Lynn Streeter.
Forráskód (FORTRAN 77).
Forráskód (FORTRAN 77).
Az SVD-t lásd a GSL kézikönyvében .

Lásd is

Források

Eugenio Beltrami, Sulle funzioni bilineari, Giornale di matematiche, pp. 1873. 98–106. [1]
Camille Jordan, Emlékirat a bilináris formákról, Journal of pure and alkalmazott matematika, második sorozat, 19., pp. 1874. 35–54. [2]
Camille Jordan, A bilináris formák csökkentéséről, Heti jelentések a Tudományos Akadémia üléseiről, 78, pp. 1874. 614–617. [3]
Camille Jordan, esszé az n- dimenziós geometriáról , a matematikai társadalom közlönye, 3, pp. 1875. 103–174. [4]
James Joseph Sylvester, A lineáris-lineáris forma biontogonális redukciójáról kanonikus formájára, Heti jelentések a Tudományos Akadémia üléseiről, 108., pp. 651–653, 1889. [5]
Émile Picard, Néhány megjegyzés az első típusú integrált egyenletekről és a matematikai fizika bizonyos problémáiról, Heti beszámolók az Académie des sciences üléseiről, 148, pp. 1563–1568, 1909. [6]
Émile Picard, Az első típusú integrálegyenletekre vonatkozó általános tételről és a matematikai fizika néhány problémájáról Rendiconti del circolo matematico de Palermo, 29 (1), pp. 1910. 79–97. [7]

Bibliográfia

(en) Hervé Abdi , „Szinguláris értékbontás (SVD) és általánosított egyesérték-bomlás (GSVD)” , a Mérés és statisztika enciklopédiájában , Thousand Oaks, Sage Publications,2007, 907-912 o. ( ISBN 978-1-4129-1611-0 , online olvasás )
(en) James Demmel és W. Kahan , „ A kétoldalas mátrixok pontos pontos értéke ” , SIAM Journal on Scientific and Statistical Computing , vol. 11, n o 5,1990, P. 873-912 ( ISSN 0196-5204 , OCLC 4633509299 , online olvasás , hozzáférés : 2014. október 8. )
(en) Gene H. Golub és Charles F. Van Loan , Matrix computations , Baltimore, Johns Hopkins University Press , coll. "Johns Hopkins matematikatudományi tanulmányok",1996, 3 e . , 694 p. ( ISBN 978-0-8018-5413-2 )
(en) Carl Eckart és Gale Young , „ Az egyik mátrix közelítése egy alacsonyabb rangú mátrixhoz ” , Psychometrika , vol. 1, n o 3,1936. szeptember, P. 211-218 ( ISSN 0090-7499 , online olvasás , hozzáférés : 2014. október 8. )
(en) Halldor Bjornsson és Silvia A. Venegas , „ A kézikönyv az éghajlati adatok EOF és SVD elemzéséhez ” , CCGCR jelentés , Montreal, McGill University, vol. 97, n o 1,1997. február( online olvasás , konzultáció 2014. október 8-án )
(en) Per Christian Hansen , „ A csonka SVD mint a szabályozás módszere ” , BIT , vol. 27,1987, P. 34–553 ( online olvasás , hozzáférés: 2014. október 8. )
(en) Roger A. Horn és Charles R. Johnson , „A sarki forma és az egyes értékek bomlása” , Matrix elemzés , Cambridge, Cambridge University Press,1985( ISBN 978-0-521-30586-0 ) , p. 411-427
(en) Roger A. Horn és Charles R. Johnson , „3. fejezet - Egyes értékek egyenlőtlenségei” , a mátrixelemzés témaköreiben , Cambridge, Cambridge University Press,1994( ISBN 978-0-521-46713-1 , online olvasás ) , p. 134-238
en) Gilbert Strang , Bevezetés a lineáris algebrába , Wellesley, Wellesley-Cambridge Press,1993, 472 p. ( ISBN 978-0-9614088-5-5 )
(en) Chris Ding és Jieping Ye , „ Kétdimenziós szinguláris értékbontás (2DSVD) a 2D-s térképekhez és képekhez ” , Proc. SIAM Nemzetközi Konf. Data Mining , vol. 5,2004. október 3, P. 32–43 ( online olvasás , konzultáció 2014. október 8-án )
(en) Jieping Ye , „ Low-rank közelítések általános mátrixok , ” Machine Learning , vol. 61,2005. június 9, P. 167-191 ( ISSN 1573-0565 , online olvasás , konzultáció 2014. október 8. )
de) Günter Gramlich , Anwendungen der linearen Algebra: mit MATLAB; mit 68 Beispielen und 41 Aufgaben , Lipcse, Carl-Hanser-Verl., koll. "Mathematik-Studienhilfen",2004, 179 o. ( ISBN 978-3-446-22655-5 )

Kapcsolódó cikkek

Külső linkek

Végrehajtások

(en) Az ALGLIB a LAPACK adaptációját kínálja különböző nyelveken;
(en) “ : Java SVD library ” ( Archívum • Wikiwix • Archive.is • Google • Mit kell tenni? ) (hozzáférés : 2013. november 6. ) ;
(en) Opencv : képelemző könyvtár C / C ++ nyelven;
(en) Eigen : lineáris algebrai könyvtár C ++ nyelven;
en) PROPACK : SVD számítási program;
en) Java szkript az SVD kiszámításához;
(en) SVDPACK : ANSI FORTRAN 77 könyvtár, amely 4 iteratív SVD megvalósítást kínál;
(en) SVDLIBC : az SVDPACK adaptálása C-ben;
( fr ) A BlueBit egy .NET könyvtárat kínál, amely képes kiszámítani az SVD-t.
Az SVD kiszámítása a Python nyelvhez :
- (en) NumPy : valós vagy összetett mátrixokat kezel
- (en) SciPy : valós vagy összetett mátrixokat kezel
- (en) Gensim , végrehajtása alapján numpy : lehetővé teszi, hogy a csonka SVD a gyér mátrixok nagyobb RAM
- (en) sparsesvd : burkoló az SVDLIBC köré
- (en) SVD-Python : tiszta Pythonban, a GNU GPL alatt.

Tanfolyamok és konferenciák

SVD, 2DSVD, 3DSVD és alkalmazások ;
„ Szinguláris értékbontás ” ( Archívum • Wikiwix • Archive.is • Google • Mit kell tenni? ) (Hozzáférés : 2013. november 6. ) ;
(en) „ SVD és alkalmazásai ” ( Archívum • Wikiwix • Archive.is • Google • Mit kell tenni? ) (hozzáférés : 2013. november 6. ) ;
(fr) Videokonferencia az MIT-en , Gilbert Strang. A 29. számú játék lefedi az SVD-t;
( fr ) Bevezetés Todd Will, a Wisconsin-La Crosse Egyetem szinguláris értékbontásához;
(de) A létezés igazolása .

Magyarázatok és alkalmazások

en) az SVD alkalmazásai ;
en) „SVD a genom egészére kiterjedő expressziós adatfeldolgozáshoz és modellezéshez” , Stanford Egyetem: génelemzés SVD-vel;
(en) Stanford Egyetem : egyes gének rákra gyakorolt hatásának elemzése SVD alkalmazásával;
en) Los Alamos-csoport : genetikai adatok elemzése;
en) LSA : alkalmazások, magyarázatok és felhasználás lehetősége;
en) bemutatás és felhasználási példa ;
en) SVD , további magyarázatok;
en) LAPACK kézikönyv : a számítási eljárások részletei;
(fr) További információ az SVD C megvalósításáról.