Ich habe über Singular Value Decomposition (SVD) gelesen. In fast allen Lehrbüchern wird erwähnt, dass es die Matrix in drei Matrizen mit gegebener Spezifikation zerlegt.
Aber was ist die Intuition hinter der Aufspaltung der Matrix in einer solchen Form? PCA und andere Algorithmen zur Dimensionsreduzierung sind in dem Sinne intuitiv, dass der Algorithmus eine gute Visualisierungseigenschaft aufweist, bei SVD ist dies jedoch nicht der Fall.
matrix
linear-algebra
svd
intuition
SHASHANK GUPTA
quelle
quelle
Antworten:
Schreiben den SVD der Matrix (real, n × p ) als X = U D V T , wo U ist n × p , D ist diagonal p × p und V T ist , p × p . In Bezug auf den Spalten der Matrizen U und V können wir schreiben X = Σ p i = 1 d i u i v T iX n×p
Stellen Sie sich nun , das die Graustufenwerte eines Schwarzweißbilds enthält, wobei jeder Eintrag in der Matrix ein Pixel darstellt. Zum Beispiel das folgende Bild eines Pavians:X
Lesen Sie dann dieses Bild in R ein und holen Sie sich den Matrixteil der resultierenden Struktur, möglicherweise unter Verwendung der Bibliothek
pixmap
.Wenn Sie eine schrittweise Anleitung zur Reproduktion der Ergebnisse benötigen, finden Sie den Code hier .
Berechnen Sie die SVD:
Daraus ergeben sich die folgenden zwei Bilder:
Links sind die vertikalen / horizontalen Streifen im Rang-1-Bild gut zu erkennen.
Was ziemlich interessant ist: Wir sehen die Teile des Originalbildes, die schwer darzustellen sind, als Überlagerung von vertikalen / horizontalen Linien, meist diagonalen Nasenhaaren und etwas Textur, und die Augen!
quelle
Sei (also quantifiziert die Sprengkraft von in der Richtung ). Angenommen, die Einheitsvektoren sind so definiert, dass Die Gleichungen (2) können unter Verwendung der Matrixnotation kurz ausgedrückt werden als wobei die Matrix ist, deren te Spalte , die Matrix ist, deren Die dritte Spalte ist undσi=∥Avi∥2 σi A vi ui Avi=σiuifor i=1,…,n.(2) AV=UΣ,(3) V n×n i vi U m×n i ui Σ ist die Diagonalmatrix, deren ter diagonaler Eintrag . Die Matrix ist orthogonal, also können wir beide Seiten von (3) mit multiplizieren , um
Es könnte den Anschein haben, dass wir die SVD von mit nahezu null Aufwand abgeleitet haben. Keiner der Schritte war bisher schwierig. Es fehlt jedoch ein entscheidender Teil des Bildes - wir wissen noch nicht, dass orthogonal ist.n×n i σi V VT A=UΣVT. A U
Hier ist die entscheidende Tatsache, das fehlende Teil: Es stellt sich heraus, dass orthogonal zu : Ich behaupte, wenn dies nicht wahr wäre, dann wäre für problem (1) nicht optimal. In der Tat wäre es möglich, wenn (4) nicht erfüllt wäre, zu verbessern, indem es ein wenig in der Richtung .Av1 Av2 ⟨Av1,Av2⟩=0.(4) v1 v1 v2
Angenommen (für einen Widerspruch), dass (4) nicht erfüllt ist. Wenn in der orthogonalen Richtung leicht gestört ist , ändert sich die Norm von nicht (oder zumindest ist die Änderung der Norm von vernachlässigbar). Wenn ich auf der Erdoberfläche wandle, ändert sich mein Abstand zum Erdmittelpunkt nicht. Wenn jedoch in Richtung gestört wird , die Vektor ist in dem gestörten nichtorthogonalen Richtung , und so die Änderung in der Norm von ist nicht vernachlässigbare . Die Norm vonv1 v2 v1 v1 v1 v2 Av1 Av2 Av1 Av1 kann um einen nicht zu vernachlässigenden Betrag erhöht werden. Dies bedeutet, dass für Problem (1) nicht optimal ist, was ein Widerspruch ist. Ich liebe dieses Argument, weil: 1) die Intuition sehr klar ist; 2) Die Intuition kann direkt in einen strengen Beweis umgewandelt werden.v1
Ein ähnliches Argument zeigt, dass sowohl zu als auch zu orthogonal ist und so weiter. Die Vektoren sind paarweise orthogonal. Dies bedeutet, dass die Einheitsvektoren paarweise orthogonal gewählt werden können, was bedeutet, dass die obige Matrix eine orthogonale Matrix ist. Damit ist unsere Entdeckung der SVD abgeschlossen.Av3 Av1 Av2 Av1,…,Avn u1,…,un U
Um das obige intuitive Argument in einen strengen Beweis umzuwandeln, müssen wir die Tatsache konfrontieren, dass der gestörte Vektor , wenn in der Richtung gestört wird, nicht wirklich ein Einheitsvektor ist. (Die Norm lautet .) Um einen strengen Beweis zu erhalten, definieren Sie Der Vektor ist wirklich ein Einheitsvektor. Aber wie Sie leicht zeigen können, wenn (4) nicht erfüllt ist, haben wir für ausreichend kleine Werte von (unter der Annahme, dass das Vorzeichen vonv1 v2 v~1=v1+ϵv2 1+ϵ2−−−−−√ v¯1(ϵ)=1−ϵ2−−−−−√v1+ϵv2. v¯1(ϵ) ϵ f(ϵ)=∥Av¯1(ϵ)∥22>∥Av1∥22 ϵ ist richtig gewählt). Um dies zu zeigen, überprüfen Sie einfach, ob . Dies bedeutet, dass für Problem (1) nicht optimal ist, was ein Widerspruch ist.f′(0)≠0 v1
(Übrigens empfehle ich, die SVD-Erklärung von Qiaochu Yuan hier zu lesen. Sehen Sie sich insbesondere "Key lemma # 1" an, was wir oben besprochen haben. Wie Qiaochu sagt, ist "Key lemma # 1" das technische Herz der Singularwertzerlegung ".)
quelle
Alter, nimm dir eine Stunde Zeit und sieh dir diesen Vortrag an: https://www.youtube.com/watch?v=EokL7E6o1AE
Dieser Typ ist super direkt, es ist wichtig, nichts davon zu überspringen, weil am Ende alles zusammenkommt. Auch wenn es am Anfang etwas langsam erscheinen mag, versucht er, einen kritischen Punkt zu bestimmen, was er auch tut!
Ich werde es für Sie zusammenfassen, anstatt Ihnen nur die drei Matrizen zu geben, die jeder tut (weil mich das verwirrte, als ich andere Beschreibungen las). Woher kommen diese Matrizen und warum richten wir sie so ein? Der Vortrag nagelt es! Jede Matrix (jemals in der Geschichte der Everness) kann aus einer Grundmatrix mit den gleichen Dimensionen konstruiert werden. Dann kann sie gedreht und gedehnt werden (dies ist der Hauptsatz der linearen Algebra). Jede dieser drei Matrizen, die Menschen herumwerfen, repräsentiert eine anfängliche Matrix (U), eine Skalierungsmatrix (Sigma) und eine Rotationsmatrix (V).
Die Skalierungsmatrix zeigt Ihnen, welche Rotationsvektoren dominieren, diese werden als Singularwerte bezeichnet. Die Zerlegung wird nach U, Sigma und V aufgelöst.
quelle