Maschinelles Lernen und neuronale Netze - Seite 26

 

Vorlesung 6. Singulärwertzerlegung (SVD)



6. Singulärwertzerlegung (SVD)

Dieses Video erklärt das Konzept der Singular Value Decomposition (SVD), das verwendet wird, um eine Matrix in drei Matrizen zu zerlegen, wobei die mittlere diagonal ist und die Singularwerte enthält. Die SVD hilft, die Beziehung zwischen A, Sigma und V zu verstehen und hilft letztendlich, Gleichungen zu lösen. Das Video erörtert die Bedeutung orthogonaler Vektoren, Eigenvektoren und Eigenwerte in SVD und betont die Orthogonalität von A- und V-Matrizen. Das Video erklärt auch die grafische Darstellung des SVD-Prozesses und die Polzerlegung einer Matrix. Schließlich diskutiert das Video den Prozess des Extrahierens des wichtigsten Teils einer großen Datenmatrix mit SVD.

  • 00:00:00 In diesem Abschnitt erörtert der Kursleiter das Konzept der Singular Value Decomposition (SVD), das den Eigenwerten ähnelt, aber auf rechteckige Matrizen anwendbar ist. Eigenwerte sind für rechteckige Matrizen nicht möglich, da Eigenvektoren entweder komplex oder nicht orthogonal sind. SVD führt zwei Sätze von singulären Vektoren und singulären Werten anstelle von Eigenvektoren bzw. Eigenwerten ein. Der Schlüssel zu SVD ist, dass eine Transponierte a eine große Matrix ist, die quadratisch ist und das Produkt rechteckiger Matrizen darstellt. Der erste Schritt zur Durchführung von SVD besteht darin, zu zeigen, dass jede Matrix in u mal Sigma mal V transponiert werden kann.

  • 00:05:00 In diesem Abschnitt diskutiert der Referent die Faktorisierung der Matrix A transponiert A und führt das Konzept der Eigenvektoren und Eigenwerte ein. Die Matrix hat positive bestimmte Eigenwerte, die verwendet werden, um ihre Quadratwurzeln zu berechnen. Die Eigenvektoren dieser Matrix sind quadratisch, symmetrisch und positiv definit. Die resultierende Matrix hat die gleichen Eigenwerte, aber unterschiedliche Eigenvektoren. Der Sprecher spricht dann über die Faktorisierung von A, wobei wir nach einem Satz orthogonaler Vektoren V suchen, die mit A multipliziert werden können, um einen Satz orthogonaler Vektoren U zu erhalten. Diese Vektoren werden verwendet, um die Singulärwertzerlegung (SVD) zu berechnen ). Das Ziel von SVD ist es, eine Zerlegung von A in drei Matrizen zu finden, wobei die mittlere diagonal ist und die singulären Werte von A enthält.

  • 00:10:00 In diesem Abschnitt wird das Konzept der orthogonalen Eigenschaft von Vs im Ausgaberaum im großen Bild der linearen Algebra untersucht, wo der Raum in Spaltenraum, Nullraum und andere unterteilt wird. Es wird gezeigt, dass, wenn V mit a multipliziert werden, die resultierenden Verwendungen auch orthogonal sind, was V zu etwas Besonderem macht. Eine Matrixform der Gleichungen wird präsentiert, und es zeigt sich, dass durch Betrachten einer Transponierten a das Problem des Auffindens orthogonaler und orthonormaler Verwendungen vereinfacht werden kann. Daraus wird geschlossen, dass eine Transponierte a symmetrisch, positiv definit ist und eine Diagonalform hat, was uns die Eigenschaften von V mitteilt.

  • 00:15:00 In diesem Abschnitt geht der Referent auf das Konzept der Singular Value Decomposition (SVD) ein. Die Vs in der SVD sind die Eigenvektoren der Transponierten von A. Die Sigma-Transponierte Sigma sind die Eigenwerte der A-Transponierten A. Die SVD wird erstellt, indem der letzte Schritt unternommen wird, die Eigenvektoren für doppelte oder dreifache Eigenwerte zu verstehen. Die SVD hilft, die Beziehung zwischen A, Sigma und V zu verstehen, was letztendlich dazu beitragen wird, Gleichungen wie A mal A transponiert mal X gleich B zu lösen.

  • 00:20:00 In diesem Abschnitt erläutert der Referent den letzten Schritt des Singular Value Decomposition (SVD)-Prozesses, der beweist, dass die gewählten Basisvektoren U orthogonal sind. Dazu zeigt der Sprecher, dass das Skalarprodukt von U1 und U2 gleich Null ist. Da U1 AV1/Sigma1 und U2 AV2/Sigma2 ist, wird der Nenner des Bruchs gestrichen, was die V1-Transponierte multipliziert mit der Matrix multipliziert mit V2 übrig lässt, was die Sigma2-Transponierte V2 ist. Da V2 ein Eigenvektor von A Transponiertem A ist, ist das Skalarprodukt zwischen U1 und U2 gleich Null, was beweist, dass die Basisvektoren U orthogonal sind.

  • 00:25:00 In diesem Abschnitt erörtert der Referent die Orthogonalität der A- und V-Matrizen in der Singular Value Decomposition (SVD) und ihre Beziehung zu Eigenvektoren. Die A- und V-Matrizen sind im Spalten- bzw. Zeilenraum orthogonal zueinander dargestellt. Anschließend geht der Referent auf die Entdeckungsgeschichte und Bedeutung dieses Zusammenhangs in Datenmatrizen ein. Der Sprecher warnt davor, A transponiert A zu verwenden, um die SVD zu berechnen, da dies rechenintensiv und anfällig für Rundungsfehler sein kann. Abschließend erklärt der Referent anhand eines Diagramms, wie man sich die SVD-Faktoren als eine Reihe von Drehungen und Dehnungen vorstellen kann.

  • 00:30:00 In diesem Abschnitt wird das Konzept der Singular Value Decomposition (SVD) anhand einer grafischen Darstellung des Prozesses erläutert. Das Video zeigt, wie die orthogonale Matrix die Einheitsvektoren dreht und wie Sigma sie dehnt, was zu einer Ellipse führt. Schließlich wird die orthogonale Matrix U angewendet, die die Ellipse dreht. Wenn die Matrix positiv definit und symmetrisch ist, dann ist U dasselbe wie V, und das S, das ursprünglich als Eingabe gegeben wurde, ist dasselbe wie die Ausgabe von A. Das Video erklärt auch, wie die Parameter in der Faktorisierung gezählt werden können.

  • 00:35:00 In diesem Abschnitt erklärt der Referent den Abgleich der Zahlen zwischen linker und rechter Seite in der Singularwertzerlegung (SVD) anhand eines Zwei-mal-Zwei-Beispiels. Die Drehung in der SVD erfordert zwei Parameter, während die Streckung zwei Parameter erfordert, was insgesamt vier Parameter ergibt, die zu den vier Zahlen in der SVD passen. Außerdem spricht der Referent über die Berechnung der SVD für eine Drei-mal-drei-Matrix und schlägt vor, dass eine Drehung im 3D-Raum drei Parameter erfordert, nämlich Rollen, Nicken und Gieren. Abschließend erwähnt der Referent, dass das im Text vorgestellte Beispiel für die SVD für eine bestimmte Matrix gilt, und führt einige Fakten zu Eigenwerten und singulären Werten ein.

  • 00:40:00 In diesem Abschnitt erklärt der Referent, dass die Determinante des SVD-Produkts gleich dem Produkt der Singulärwerte ist. Das verwendete Beispiel zeigt, dass das Produkt der Sigmas auch gleich der Determinante ist. Das Berechnen von Beispielen der SVD nimmt jedoch mehr Zeit in Anspruch, da man die Quadratwurzeln des Arguments ziehen muss. Der Sprecher betont, dass die wichtigsten Teile der SVD in der nächsten Sitzung verwendet werden, einschließlich der kleineren und der größeren SVD-Formen, die aus Nicht-Null-Werten bestehen und jeweils das Nullraum-Zeug ausmachen.

  • 00:45:00 In diesem Abschnitt führt der Sprecher die Polzerlegung einer Matrix ein, die jede Matrix in eine symmetrische Matrix multipliziert mit einer orthogonalen Matrix zerlegt. Dies ist eine berühmte Faktorisierung in Technik und Geometrie und kann schnell aus der SVD abgerufen werden. Durch Einfügen der Identität und leichtes Verschieben können S und Q von der SVD abgelesen werden, um diese Zerlegung einer Matrix wiederherzustellen, die uns in der Sprache des Maschinenbaus sagt, dass jede Dehnung als symmetrische Dehnung und innere Verdrehung beschrieben werden kann .

  • 00:50:00 In diesem Abschnitt erklärt der Redner den Prozess des Extrahierens des wichtigsten Teils einer großen Datenmatrix, was die Datenwissenschaft tun muss, da ein Teil der Matrix Rauschen und ein Teil davon ein Signal ist. Um den signifikantesten Teil des Signals zu finden, untersucht der Sprecher u Sigma Vtranspose und wählt die wichtigste Zahl, Sigma 1, aus. Diese Zahl bildet zusammen mit ihrer Spalte und Zeile den kritischsten Teil der Matrix, wie sie es hat den substanziellsten Rang eins und ist somit der Teil der Matrix mit der höchsten Varianz. Der nächste Schritt besteht darin, diese drei Elemente zu berechnen, um die Daten vollständiger zu verstehen.
 

Vorlesung 7. Eckart-Young: The Closest Rank k Matrix to A



7. Eckart-Young: Die nächste Rang-k-Matrix zu A

In diesem YouTube-Video erklärt der Dozent das Konzept der Hauptkomponentenanalyse (PCA), die verwendet wird, um eine Matrix von Daten zu verstehen und aussagekräftige Informationen daraus zu extrahieren. Die Bedeutung der größten k Einzelwerte einer Matrix, die die wichtigsten Informationen enthalten, wird hervorgehoben, und das Eckart-Young-Theorem, das besagt, dass die ersten k Teile einer Singulärwertzerlegung die beste Annäherung an eine Rang-k-Matrix liefern , ist vorgestellt. Der Referent diskutiert auch verschiedene Arten von Normen für Vektoren und Matrizen, einschließlich der l2-, l1- und Unendlichkeitsnormen. Die Bedeutung der Frobenius-Norm im Netflix-Wettbewerb und bei MRT-Scans wird hervorgehoben, zusammen mit dem Konzept der Rang-k-Matrix, die A am nächsten liegt. Der Referent diskutiert auch die Verwendung orthogonaler Matrizen zur Erhaltung der Eigenschaften der ursprünglichen Matrix und stellt das Konzept vor der Singular Value Decomposition (SVD) und wie sie sich auf PCA bezieht. Schließlich wird die Bedeutung der Lösung eines linearen Gleichungssystems mit der rechteckigen Matrix A und ihrer Transponierten diskutiert, zusammen mit der Verwendung der SVD-Methode, um das beste Verhältnis von Alter zu Größe für einen gegebenen Datensatz zu finden.

  • 00:00:00 In diesem Abschnitt erläutert der Dozent das Konzept der Hauptkomponentenanalyse (PCA), einem Werkzeug zum Verständnis einer Datenmatrix. Er betont, wie wichtig es ist, sinnvolle Informationen aus den Daten zu extrahieren, anstatt alles zu kopieren. Er erklärt, dass die größten k Einzelwerte der Matrix die wichtigsten Fakten enthalten und ein K die beste Annäherung an eine Rang-K-Matrix ist. Das Eckert-Young-Theorem, das besagt, dass die Verwendung der ersten K Stücke einer Singulärwertzerlegung die beste Annäherung an eine Rang-K-Matrix ist, wird vorgestellt, und der Dozent erklärt die verschiedenen Maße der Norm einer Matrix.

  • 00:05:00 In diesem Abschnitt diskutiert der Referent verschiedene Arten von Normen für Vektoren und Matrizen. Die l2-Norm oder der größte Singularwert ist eine wichtige Norm für Matrizen. Der Sprecher erklärt, dass beim Minimieren einer Funktion unter Verwendung der l1-Norm der Gewinnvektor spärlich ist oder hauptsächlich aus 0-Komponenten besteht, was bei der Signalverarbeitung und -erfassung nützlich ist. Die l1-Norm wird auch als Basisverfolgung bezeichnet und ist wichtig, da sie die Interpretation der Komponenten des Gewinnvektors ermöglicht. Die l2- und l1-Normen werden verglichen, und der Sprecher führt auch die Unendlichkeitsnorm ein.

  • 00:10:00 In diesem Abschnitt erläutert der Referent drei wichtige Matrixnormen. Die erste ist die Zweiernorm, die der Länge eines Vektors ähnelt und die Dreiecksungleichung erfüllt. Die zweite ist die Frobenius-Norm, die die Einträge einer Matrix wie einen langen Vektor behandelt und die Quadratwurzel aus der Summe ihrer Quadrate zieht. Die dritte ist die Kernnorm, die die Summe der Einzelwerte einer Matrix ist. Diese Normen sind wichtig, weil sie alle die Eckart-Young-Aussage erfüllen, dass die engste Rang-K-Annäherung an eine Matrix aus ihren ersten K singulären Werten gefunden werden kann.

  • 00:15:00 In diesem Abschnitt erörtert der Referent, wie die L2- und Frobenius-Normen einer Matrix nur von ihren singulären Werten abhängen. Die Frobenius-Norm wurde im Netflix-Wettbewerb verwendet, bei dem die Teilnehmer eine große Matrix von Filmrankings mit fehlenden Einträgen vervollständigen mussten, und es stellte sich als die richtige Norm für die beste nukleare Normvervollständigung der Matrix heraus. Diese Methode der Matrixvervollständigung wird nun für MRT-Scans mit fehlenden Daten verwendet, wo sie auch bei unvollständigen Daten ein hervorragendes Bild liefern kann.

  • 00:20:00 In diesem Abschnitt erörtert der Referent das Konzept der Rang-k-Matrix, die A am nächsten liegt. Dazu gehört das Vervollständigen einer Matrix, indem das MRT an den Positionen, an denen es nicht lange genug ausgesehen hätte, ausgefüllt hätte die Nuklearnorm. Das gegebene Beispiel ist eine Rang-4-Matrix, und um die beste Annäherung an den Rang zwei zu finden, wählt der Sprecher 4 und 3 als die zwei größten Werte. Jede andere Matrix B wäre weiter von A entfernt als diese gewählte Matrix, obwohl es nicht offensichtlich ist, weil es von der Norm abhängt. Der Punkt des Theorems ist, dass es nicht einfach ist, die Rang-k-Matrix zu finden, die A am nächsten liegt, und ein Beweis ist erforderlich.

  • 00:25:00 In diesem Abschnitt erörtert der Redner, warum Diagonalmatrizen nicht so besonders sind, wie sie scheinen, und stellt das Konzept einer orthogonalen Matrix vor, die verwendet werden kann, um auf beiden Seiten einer gegebenen Matrix zu multiplizieren. Der Referent stellt die Frage, was mit den singulären Werten einer Matrix passiert, wenn sie mit einer orthogonalen Matrix multipliziert werden, und erklärt, dass sich die singulären Werte nicht ändern werden. Der Referent erklärt auch, dass die Normen von Vektoren durch orthogonale Matrizen nicht verändert werden, und kommt zu dem Schluss, dass orthogonale Matrizen genauso gut sind wie diagonale Matrizen, um die Eigenschaften der ursprünglichen Matrix zu bewahren.

  • 00:30:00 In diesem Abschnitt wurde das Konzept der Singular Value Decomposition (SVD) im Kontext der Matrix-QA erläutert. Die SVD der Matrix QA besteht aus einer Diagonalmatrix, Sigma, rechts davon; V-Transponierung rechts von Sigma; und Q u auf der linken Seite von Sigma, wobei Q u eine orthogonale Matrix ist. In diesem Abschnitt wurde das Konzept der Hauptkomponentenanalyse (PCA) vorgestellt und erläutert, wie aus Datenpunkten aussagekräftige Erkenntnisse gewonnen werden können. Der erste Schritt in PCA bestand darin, den Mittelwert Null zu erhalten, indem die Durchschnittswerte der Datenpunkte für jede Komponente subtrahiert wurden. Der Abschnitt erläuterte weiter, wie die resultierenden Werte verwendet werden könnten, um die lineare Beziehung zwischen Komponenten zu finden.

  • 00:35:00 In diesem Abschnitt erörtert der Referent die Hauptkomponentenanalyse (PCA) und wie sie sich von der Methode der kleinsten Quadrate unterscheidet. Während die Methode der kleinsten Quadrate die Fehler zwischen Punkten und einer Linie misst, misst PCA den senkrechten Abstand von Punkten von einer Linie und addiert ihre Quadrate, um sie zu minimieren. Daher beinhaltet die Lösung dieses Problems die Singular Value Decomposition (SVD) Sigmas anstelle der Gleichungen, die in der gewöhnlichen linearen Algebra zu finden sind. Der Sprecher unterscheidet das Problem, die beste lineare Beziehung in der PCA zu finden, von der Suche nach der Lösung der kleinsten Quadrate, da das erstere Problem darauf abzielt, nichtlineare Daten auf lineare Weise zu modellieren.

  • 00:40:00 In diesem Abschnitt erörtert der Referent die Bedeutung der Lösung eines linearen Gleichungssystems mit der rechteckigen Matrix A und ihrer Transponierten. Obwohl dies eine grundlegende Anwendung im Jahr 1806 ist, stellt der Sprecher fest, dass dies nicht dasselbe ist wie die Hauptkomponentenanalyse (PCA), die Statistiker seit langem anwenden. Er stellt fest, dass die Kovarianzmatrix oder die Stichproben-Kovarianzmatrix, die den Mittelwert und die Varianz beinhaltet, bei solchen statistischen Anwendungen eine große Rolle spielt. Insbesondere wird die Probenkovarianzmatrix aus den Proben berechnet und durch die Anzahl der Datenpunkte normalisiert, und sie ist genau eine Zug-aa-Transponierung.

  • 00:45:00 In diesem Abschnitt stellt der Sprecher ein Problem vor, bei dem es darum geht, das beste Verhältnis von Alter zu Größe für einen bestimmten Datensatz zu finden. Ziel ist es, die Distanz zwischen den gegebenen Daten und der Lösung zu minimieren. Der Sprecher schlägt vor, dass die Antwort darin liegt, den Vektor zu finden, der in die richtige Richtung zeigt, was eine Hauptkomponente in der symmetrischen positiv definiten Matrix sein könnte. Als Lösung für dieses Problem wird das SVD-Verfahren vorgeschlagen.
 

Vorlesung 8: Normen von Vektoren und Matrizen



Vorlesung 8: Normen von Vektoren und Matrizen

Diese Vorlesung behandelt das Konzept der Normen von Vektoren und Matrizen, einschließlich L1- und Max-Normen, und ihre Anwendung in Bereichen wie Kompressionserkennung und Signalverarbeitung. Die Vorlesung behandelt auch die Bedeutung der Dreiecksungleichung in Normen, die Form von S-Normen und den Zusammenhang zwischen der L2-Norm von Vektoren und Matrizen. Darüber hinaus befasst sich die Vorlesung mit der Frobenius-Norm und der Nuklearnorm, die eine Vermutung zur Optimierung neuronaler Netze bleibt, und betont die Bedeutung des Lehrens und Lernens mit Studenten.

  • 00:00:00 In diesem Abschnitt diskutiert der Redner eine interessante Beobachtung eines Fakultätsmitglieds der Sloan School des MIT, die sich darauf bezieht, wie Menschen das Ergebnis von Münzwürfen erraten. Er erklärt, dass, obwohl theoretisch die optimale Strategie darin bestünde, konsequent Kopf zu erraten, Menschen und Tiere in etwa einem Viertel der Fälle Zahl erraten, obwohl die Wahrscheinlichkeit, Kopf zu bekommen, viel höher ist. Der Grund dafür wird nicht erklärt, da der Redner nicht genug Zeit hatte, sich die Erklärung anzuhören. Der Referent führt auch kurz in das Konzept der Normen und ihre Bedeutung bei der Messung der Größe von Vektoren, Matrizen, Tensoren und Funktionen ein.

  • 00:05:00 In diesem Abschnitt wird das Konzept der Normen von Vektoren und Matrizen diskutiert. Der Dozent stellt verschiedene Arten von Normen wie die L1-Norm und die Max-Norm vor, die im Bereich der Drucksensorik und Signalverarbeitung von wesentlicher Bedeutung sind. Er erklärt, dass die P-Norm gleich der P-Potenz zur P-Potenz hier oben P ist, wobei das Ziehen von P-Potenzen und P-Wurzeln die Norm von zwei V ergibt, um einen Faktor von zwei im Vergleich zur Norm von V zu haben. Außerdem die Null Norm eingeführt, deren Anzahl von Nicht-Null-Komponenten ein Maß für die Sparsity von Matrizen und Vektoren gibt. Es ist jedoch keine Norm, da es gegen die Regel verstößt, dass die gleiche Anzahl von Nicht-Null-Komponenten dieselbe Norm haben, und die mathematischen Arbeiten zwischen eins und unendlich, in denen geeignete Normen existieren, werden diskutiert.

  • 00:10:00 In diesem Abschnitt diskutiert der Dozent die Normen von Vektoren und Matrizen. Die Einheitskugel für die Norm ist ein Kreis mit der Gleichung v1 zum Quadrat plus v2 zum Quadrat gleich eins. Die Einheitskugel für die l1-Norm ist eine Raute mit dem geraden Liniendiagramm von v1 plus v2 gleich eins im positiven Quadranten. Die Einheitskugel für die Max-Norm wird ebenfalls mit den Punkten Null, +/- Eins und +/- i gleich Max gezeichnet, und der Rest der Grenze erfordert ein wenig Überlegung, um herauszufinden. Wenn sich die Zahl p ändert, beginnt die Norm mit einer Raute, schwillt bei p gleich zwei zu einem Kreis an und wird bei p gleich unendlich zu einem Quadrat. Schließlich ist die 0-Norm nicht enthalten, und die Punkte mit nur einem Nicht-Null-Wert befinden sich auf den Achsen.

  • 00:15:00 In diesem Abschnitt diskutiert der Dozent verschiedene Arten von Normen, wie z. B. die L1- oder Manhattan-Norm, die L2- oder Euklidische Norm und die S-Norm, die eine Norm positiv definiter symmetrischer Matrizen ist. Der Dozent weist auf die Bedeutung der Dreiecksungleichung in Normen hin, die in bestimmten Fällen gebrochen wird, etwa bei Verwendung der Lp-Norm mit p kleiner eins. Darüber hinaus wird gezeigt, dass die S-Norm eine bestimmte Form hat, die die Konvexitätseigenschaft erfüllt, die bestimmte Normen, die die Regeln einer Norm verletzen, nicht besitzen.

  • 00:20:00 In diesem Abschnitt diskutiert der Dozent die verschiedenen Arten von Normen, die auf Vektoren und Matrizen angewendet werden können. Die L2-Norm wird verwendet, wenn die Matrix S die Identitätsmatrix ist, aber die Verwendung einer anderen Matrix S wird die Form der Norm ändern. Ein typischer Fall ist S gleich 3, wodurch eine gewichtete Norm entsteht, die durch eine Ellipse dargestellt wird. Alle Vektornormen sind Variationen der L2-Norm mit unterschiedlichen Werten für P. Der Dozent erwähnt auch kurz das Basisverfolgungsproblem und die Ridge-Regression mit ihren jeweiligen L1- und L2-Normen.

  • 00:25:00 In diesem Abschnitt diskutiert der Dozent das Konzept der Normen in der Optimierung, insbesondere die L1- und L2-Normen. Am Beispiel des Findens des Punktes auf einer Linie mit der kleinsten L2-Norm und dann der kleinsten L1-Norm betont der Dozent, dass der Punkt mit der kleinsten L1-Norm der Gewinner ist und die meisten Nullen hat, was ihn zu einem schwach besetzten Vektor macht. Dies ist eine wichtige Tatsache, die in höhere Dimensionen hineinreicht und die L1-Norm besonders macht. Insgesamt befasst sich die Vorlesung mit den Nuancen und Anwendungen von Normen bei der Optimierung neuronaler Netze und des Lebens im Allgemeinen.

  • 00:30:00 In diesem Abschnitt erörtert der Sprecher den Gewinner der L1-Norm und wie es nicht ratsam ist, weiter nach oben zu gehen, da dies die Nicht-Null-über-Second-Komponente erhöht. Sie führen auch den Begriff der Zwei-Normen von Matrizen ein und wie es mit den Zwei-Normen von Vektoren durch einen Vergrößerungsfaktor verbunden ist, der das maximale Verhältnis der beiden Normen von AX zu den beiden Normen von X ist. Die Matrix-Norm ist definiert als der maximale Aufblasfaktor über alle X.

  • 00:35:00 In diesem Abschnitt diskutiert der Dozent Normen von Matrizen und wie man eine gute Norm einer Matrix findet. Er erklärt, dass der Maximalwert des Verhältnisses, das durch die beiden Normen erhalten wird, Sigma 1 genannt wird. Dieser Wert kann verwendet werden, um zu bestimmen, was der singuläre Vektor ist, ohne tatsächlich alle zu finden. Zusätzlich können andere Matrixnormen erhalten werden, indem dieser Vergrößerungsfaktor in dieser Vektornorm maximiert wird. Singuläre Vektoren sind eine Möglichkeit, die Normen zu finden, daher funktionieren Eigenvektoren möglicherweise nicht, wenn es um Matrizen geht, die nicht symmetrisch sind.

  • 00:40:00 In diesem Abschnitt geht der Dozent auf die Frobenius-Norm von Matrizen ein, die mit dem großen F bezeichnet wird und der Quadratwurzel aus der Summe aller Matrixelemente zum Quadrat entspricht. Diese Norm bezieht sich auf die Sigmas, die Quadrate der singulären Werte der SVD. Darüber hinaus untersucht die Vorlesung, wie die orthogonale Matrix und die Frobenius-Norm miteinander verbunden sind und wie die nukleare Norm mit Deep-Learning-Optimierungsalgorithmen zusammenhängt.

  • 00:45:00 In diesem Abschnitt diskutiert der Dozent die Vermutung, dass in einer Modellsituation die Optimierung durch Gradientenabstieg die Gewichte auswählt, die die nukleare Norm minimieren. Die Kernnorm ist die Summe der Einzelwerte einer Matrix, ähnlich der L1-Norm für Vektoren. Diese Vermutung bleibt unbewiesen, aber die Idee hat potenzielle Anwendungen in Deep Learning und Compressed Sensing. Der Dozent betont, dass es seine Aufgabe nicht sei, seine Studierenden zu benoten, sondern mit ihnen zu lehren und zu lernen. Die Vorlesung endet mit der Ankündigung der Hausaufgabe drei, die die Notizen aus den Abschnitten acht und neun verwenden wird.
 

Vorlesung 9. Vier Wege zur Lösung von Kleinste-Quadrate-Problemen



9. Vier Wege zur Lösung von Kleinste-Quadrate-Problemen

In diesem Video erläutert der Kursleiter das Konzept der kleinsten Quadrate und verschiedene Vorgehensweisen. Er betont die Bedeutung der kleinsten Quadrate, da sie ein wesentliches Problem der linearen Algebra darstellen und als Kitt dienen, der den gesamten Kurs zusammenhält. Das Video behandelt die Pseudo-Inverse von Matrizen, SVD von invertierbaren und nicht-invertierbaren Matrizen und verschiedene Methoden zur Lösung von Problemen der kleinsten Quadrate, einschließlich des Gauß-Plans und orthogonaler Spalten. Das Video diskutiert auch die Idee, den Abstand zwischen ax + b und den tatsächlichen Messungen unter Verwendung des L2-Normquadrats zu minimieren und wie dies mit linearer Regression und Statistik zusammenhängt. Darüber hinaus bietet das Video Einblicke in ein Projekt, das das im Kurs gelernte Material verwendet und sich auf Bereiche wie maschinelles Lernen und Deep Learning konzentriert.

  • 00:00:00 In diesem Abschnitt erörtert der Kursleiter die Bedeutung der kleinsten Quadrate und erklärt, dass dies ein grundlegendes Problem in der linearen Algebra ist. Er erwähnt, dass es verschiedene Möglichkeiten gibt, sich den kleinsten Quadraten zu nähern, und dieses Thema ist der Kitt, der den gesamten Kurs zusammenhält. Er erwähnt auch, dass es keine Abschlussprüfungen oder Tests geben wird, sondern dass er ein Projekt anregen wird, das den im Kurs gelernten Stoff verwendet. Das Projekt wird verschiedene Bereiche wie maschinelles Lernen und Deep Learning umfassen, und er wird zu gegebener Zeit eine Nachricht über die Details des Projekts versenden.

  • 00:05:00 In diesem Abschnitt erläutert der Referent das Konzept der Pseudo-Inversen einer Matrix. Wenn die Inverse existiert, können wir damit multiplizieren und dann zum ursprünglichen Vektor zurückkehren, aber für eine Matrix ohne Inverse wenden wir uns der Pseudo-Inversen zu. Dies ist in Fällen relevant, in denen die Matrix rechteckig ist, Null-Eigenwerte hat oder einen Nullraum hat. Der Sprecher verwendet ein Bild des Zeilen- und Spaltenraums, um zu erklären, welche Teile des Bildes umkehrbar und welche hoffnungslos sind. Die Pseudo-Inverse wird verwendet, um Probleme zu lösen, wenn die Matrix nicht invertierbar ist, wodurch eine angemessene Lösung bereitgestellt wird.

  • 00:10:00 In diesem Abschnitt erklärt der Referent, wie man die Pseudo-Inverse einer Matrix für Situationen definiert, in denen eine Matrix nicht invertiert werden kann. Sie diskutieren, wie man mit dem Nullraum einer Matrix umgeht und was die Pseudo-Inverse in diesem Fall tun sollte. Der Sprecher liefert einen Plan dafür, was die Pseudo-Inverse im Spaltenraum und im orthogonalen Raum tun soll, wo niemand darauf trifft. Unter Verwendung der SVD stellen sie eine Formel für die Pseudo-Inverse bereit, bei der eine Matrix auf die Identitätsmatrix in der oberen Hälfte und Null in der unteren Hälfte projiziert wird.

  • 00:15:00 In diesem Abschnitt behandelt das Video die SVD (Singular Value Decomposition) einer invertierbaren Matrix, wobei die SVD die Vs zurück zu den Us bringt oder umgekehrt. Wenn eine Matrix nicht invertierbar ist, erfordert ihre SVD, dass ihre rechteckige Sigma-Matrix durch ihre Pseudo-Inverse ersetzt wird. Das Video zeigt ein Beispiel einer Matrix mit zwei unabhängigen Spalten, in der Sigma nur zwei Nicht-Nullen hat und der Rest Nullen sind, was eine total singuläre Situation darstellt. Daher ist es am besten, die Pseudo-Inverse von Sigma anstelle von Sigma Inverse zu verwenden.

  • 00:20:00 In diesem Abschnitt wird das Konzept von Sigma plus, der Pseudo-Umkehrung von Sigma, als Lösung für rechteckige Matrizen eingeführt, die nicht invertiert werden können. Die Pseudo-Inverse wird verwendet, um das Problem der kleinsten Quadrate zu lösen, bei dem es eine Gleichung ax gleich B gibt, aber a nicht invertierbar ist. Dieses Problem tritt auf, wenn zu viele Messungen oder Rauschen vorhanden sind. Die Sigma-Plus-Matrix wird verwendet, um die Vektoren im Spaltenraum zu erhalten, während die Vektoren im orthogonalen Raum als unlösbar betrachtet werden. Der erste Weg, das Problem der kleinsten Quadrate zu lösen, besteht darin, die Sigma-Plus-Matrix zu verwenden, um die Lösung zu erhalten.

  • 00:25:00 In diesem Abschnitt erörtert der Referent das Problem der kleinsten Quadrate, bei dem eine gerade Linie mit einem linearen Gleichungssystem an verrauschte Messungen angepasst wird. Sie erklären, dass, wenn die Messungen auf einer Linie liegen, das lineare System eine Lösung hat, aber im Allgemeinen nicht. Dann führen sie die Idee ein, den Abstand zwischen ax + b und den tatsächlichen Messungen unter Verwendung des L2-Normquadrats zu minimieren. Diese Technik wurde von Gauß vorgeschlagen und wird verwendet, um die besten Werte von C und D in der Gleichung Cx + D zu finden, die die gerade Linie darstellt, die den Messungen am nächsten kommt.

  • 00:30:00 In diesem Abschnitt erklärt der Referent das Konzept der kleinsten Quadrate und wie es verwendet wird, um unlösbare Probleme in der linearen Regression und Statistik zu lösen. Durch Minimieren der quadratischen Verlustfunktion wird ein System linearer Gleichungen erzeugt, das letztendlich die beste Antwort liefert, wobei man den Ratschlägen von Gauß folgt. Das beste X wird gefunden, indem die Gleichung a transponiert a mal X gleich transponiert B gelöst wird, was zum Minimum führt. Der Sprecher zeichnet dann einen Graphen, um das Konzept des Spaltenraums von A zu erklären und wie B nicht im Spaltenraum liegt und wie die Quadrate und Normalgleichungen zum besten AX führen.

  • 00:35:00 In diesem Abschnitt erörtert der Referent verschiedene Methoden zur Lösung von Problemen der kleinsten Quadrate. Methode 2 beinhaltet das Lösen der Normalgleichungen mit Matrizen in MATLAB. Diese Methode funktioniert jedoch möglicherweise nicht, wenn die Matrix fast einzelne Spalten hat. Methode 3 beinhaltet die Verwendung des Gauß-Plans, der nur funktioniert, wenn die Matrix unabhängige Spalten hat, was bedeutet, dass die Matrix invertierbar ist. Das pseudoinverse Verfahren kann auch verwendet werden, wenn die Matrix nicht invertierbar ist, aber unabhängige Spalten hat. Die Bedeutung der Invertierbarkeit der Matrix wird im gesamten Abschnitt betont.

  • 00:40:00 In diesem Abschnitt erklärt der Sprecher, dass, wenn der Nullraum null ist, die Antwort von der pseudoinversen Methode die gleiche ist wie die Antwort, die von der Methode einer Transponierung einer Inversen einer Transponierung B kommt Der Sprecher merkt an, dass der Nullraum einer Transponierung nicht umkehrbar ist, aber eine Transponierung a ist umkehrbar. Darüber hinaus erklärt der Sprecher, dass die Matrix-aa-Transponierung ihr Bestes tut, um die Inverse zu sein, aber es ist nicht nah genug. Es wird gezeigt, dass die Pseudo-Inverse funktioniert, wenn der Rang gleich ist.

  • 00:45:00 In diesem Abschnitt erörtert der Sprecher zwei weitere Möglichkeiten zur Lösung von Problemen der kleinsten Quadrate. Der dritte Weg besteht darin, zuerst orthogonale Spalten zu erhalten, was das Problem einfacher machen würde. Das Gram-Schmidt-Verfahren ist eine Möglichkeit, orthogonale Vektoren auf natürliche Weise zu erhalten. Der vierte und letzte Weg zur Lösung von Kleinste-Quadrate-Problemen wird nicht im Detail besprochen, aber es geht darum, die Tatsache auszunutzen, dass Daten im wirklichen Leben oft spärlich sind. Der Redner schließt mit der Feststellung, dass die Methode der kleinsten Quadrate kein neues Konzept ist und aus gutem Grund weiterhin verwendet wird.
 

Vorlesung 10: Übersicht über Schwierigkeiten mit Ax = b



Vorlesung 10: Übersicht über Schwierigkeiten mit Ax = b

In dieser Vorlesung zur numerischen linearen Algebra werden die Schwierigkeiten bei der Lösung linearer Gleichungen der Form Ax=b besprochen. Diese Schwierigkeiten treten auf, wenn die Matrix A nahezu singulär ist, was ihre Inverse unangemessen groß macht, und wenn das Problem mit einer riesigen Matrix zu groß ist, die in einer machbaren Zeit nicht zu lösen ist. Der Dozent skizziert mehrere Möglichkeiten zur Lösung des Problems, die vom einfachen Normalfall bis zum extrem schwierigen Fall unterbestimmter Gleichungen reichen. Die Verwendung von randomisierter linearer Algebra, iterativen Methoden und der SVD werden diskutiert, zusammen mit der Wichtigkeit, Lösungen zu finden, die auf Testdaten funktionieren, insbesondere mit Deep Learning. Darüber hinaus betont der Dozent, dass die SVD immer noch das beste Werkzeug zur Diagnose von Matrixproblemen ist.

  • 00:00:00 In diesem Abschnitt diskutiert der Dozent die Schwierigkeiten, die beim Versuch auftreten können, die Gleichung Ax = B zu lösen. Er stellt fest, dass das Problem in verschiedenen Größen und Rängen auftreten und nahezu singulär oder nicht annähernd singulär sein kann. Er skizziert mehrere Möglichkeiten zur Lösung des Problems, die vom einfachen Normalfall einer quadratischen Matrix mit vernünftiger Bedingungszahl bis zum extrem schwierigen Fall unterbestimmter Gleichungen reichen. Im letzteren Fall stellt der Dozent fest, dass das Problem beim Deep Learning häufig vorkommt und dass mehrere Lösungen existieren können.

  • 00:05:00 In diesem Abschnitt bespricht der Dozent schwierige Probleme mit Ax = b und wie man sie angeht. Diese Probleme treten normalerweise auf, wenn die Spalten der Matrix nahezu abhängig sind, was es problematisch macht, die Spalten a1, a2 bis an der gegebenen Matrix zu akzeptieren. Die Lösung hierfür besteht darin, orthonormale Spaltenvektoren in diesem Spaltenraum zu finden, indem Gram-Schmidt verwendet wird und die Spalten durch Orthogonalisierung fixiert werden. Der Dozent verschiebt die Gram-Schmidt-Diskussion auf die nächste Vorlesung, gibt aber einen Ausblick auf die Wichtigkeit der Spaltenschwenkung, die eine Neuordnung der Spalten ermöglicht, ein Konzept, das auch bei der Eliminierung anwendbar ist.

  • 00:10:00 In diesem Abschnitt diskutiert der Dozent die Schwierigkeiten beim Lösen linearer Gleichungen der Form Ax=b, einschließlich der Möglichkeit, dass die Matrix nahezu singulär sein kann, wodurch ihre Inverse unangemessen groß wird. Der Dozent spricht auch über inverse Probleme, die typischerweise Probleme sind, bei denen Sie die Ausgabe des Systems kennen, aber die Struktur oder Eingabe des Netzwerks bestimmen müssen. Diese Probleme ergeben oft fast singuläre Matrizen, was es schwierig macht, das System genau zu lösen, ohne einen Strafterm hinzuzufügen, um das Problem zu minimieren. Die Leu- und QR-Welten, der Zeilenaustausch und die Gram-Schmidt-Orthogonalisierung werden ebenfalls erwähnt.

  • 00:15:00 In diesem Abschnitt lernen wir einige Schwierigkeiten kennen, die beim Lösen linearer Gleichungen mit der Ax=b-Methode auftreten. Eine solche Schwierigkeit besteht darin, dass die Matrix A schlecht konditioniert ist, was zu Vektoren führt, die sich Null nähern, und zu einer riesigen Umkehrung einer Transponierten a. Um dem entgegenzuwirken, müssen wir A bestrafen, was es besser konditioniert, aber auch das Problem auf die Entscheidung verschiebt, wie stark es bestraft werden soll. Eine andere Methode sind iterative Methoden, wie die konjugierte Gradientenmethode, bei der wir der exakten Antwort einen Schritt näher und näher kommen, bis sie nahe genug ist. Wenn das Problem mit einer riesigen Matrix zu groß ist, die in einer machbaren Zeit nicht zu lösen ist, wird randomisierte lineare Algebra verwendet, um die Spalten und Zeilen der Matrix abzutasten, um eine Antwort aus der Stichprobe zu liefern.

  • 00:20:00 In diesem Abschnitt diskutiert der Dozent die Verwendung randomisierter linearer Algebra zur Bestimmung von Lösungen für schwierige Probleme in Fällen, in denen die Matrix angemessen ist. Es gibt zwar keine Garantie dafür, dass die Lösungen korrekt sind, aber die Verwendung der Wahrscheinlichkeiten von Ungleichungen kann zu einer guten Lösung des Problems führen. Als Lösungsverfahren werden iterative Verfahren und randomisierte Algorithmen sowie der Einsatz der SVD diskutiert. Der Dozent betont, wie wichtig es ist, Lösungen zu finden, die auf Testdaten arbeiten, insbesondere mit Deep Learning, und geht auf die tiefen mathematischen Fragen ein, die sich bei diesem Problem stellen. Die SVD wird als mögliche Lösung erklärt, wenn die Matrix nahezu singulär ist.

  • 00:25:00 In diesem Abschnitt diskutiert der Professor eine Methode zur Regularisierung des Problems, die minimale Summe von ax minus B zum Quadrat zu finden, wenn große Inverse vorhanden sind. Durch die Verwendung eines Problems der kleinsten Quadrate mit einem zusätzlichen Strafterm, der ein positives Delta enthält, ist das Problem immer noch lösbar, und die Funktion ist garantiert vom Singular entfernt, selbst wenn dieser Wert auf Null geht oder a verrückte Dinge tut. Wenn Delta auf Null geht, ändert sich das Verhalten des Ergebnisses drastisch, und dieser Faktor kann vom Rauschpegel im System abhängen.

  • 00:30:00 In diesem Abschnitt des Videos diskutiert der Sprecher die Lösung für ein bestimmtes Delta und analysiert, wann die Lösung existiert. Der Schwerpunkt liegt auf der Lösung eines Eins-zu-Eins-Problems, bei dem das Minimum eines bestraften Kleinste-Quadrate-Problems gefunden wird. Die Gleichung wird gelöst, indem die Ableitung auf Null gesetzt wird, und der resultierende X-Wert wird verwendet, um die Grenze zu bestimmen, wenn Delta auf Null geht. Die beiden Möglichkeiten sind, dass Sigma nicht null ist und die Lösung sich der Umkehrung von Sigma annähert, oder dass Sigma null ist und die Lösung nicht existiert.

  • 00:35:00 In diesem Abschnitt des Videos erörtert der Sprecher das Verhalten des Penalized Squares-Ansatzes, wenn der Penalty Term auf Null geht. Der Sprecher stellt fest, dass sich das System in diesem Fall auf seltsame Weise verhält, mit einer plötzlichen Gabelung zwischen Null und einer Nicht-Null-Grenze. Diese Grenze wird als Pseudo-Inverse identifiziert, und wenn Delta immer kleiner wird, nähert sich die Lösung des Systems der Pseudo-Inversen, die immer die richtige Antwort für das System ist. Der Referent merkt an, dass dieser Ansatz in einem praktischen Fall nützlich wäre, um die unbekannten Parameter eines Systems zu finden, wie beispielsweise die Widerstände und Induktivitäten in einem elektrischen Schaltkreis.

  • 00:40:00 In diesem Abschnitt erklärt der Dozent, dass die Lösung des Problems Ax=b erreicht werden kann, indem ein Strafterm hinzugefügt wird, um das Problem zu regularisieren. Der Strafterm kann eingeführt werden, indem die L1-Norm verwendet wird, die spärliche Lösungen ohne viele kleine Komponenten in der Antwort liefert. Er diskutiert auch die Bedeutung iterativer Methoden in der konventionellen linearen Algebra und Gram-Schmidt mit oder ohne Pivotisierung. Er beschließt jedoch, diese Themen in der nächsten Vorlesung zu behandeln.

  • 00:45:00 In diesem Abschnitt erörtert der Dozent, wie die SVD ein effektives Werkzeug ist, um Dinge über Matrizen zu beweisen; Es vereinfacht ein chaotisches Problem zu einem Problem mit einem diagonalen Matrix-Sigma in der Mitte, weshalb es bei der Diagnose von Matrixproblemen nützlich ist. Zusätzlich liefert der Dozent eine Formel für einen Spezialfall eines Problems mit Sigma als Diagonalmatrix, was impliziert, dass das Verständnis von Sigmas Verhalten, insbesondere bei jedem diagonalen Eintrag, für die Verfolgung solcher Fälle von entscheidender Bedeutung ist. Die SVD, betont der Dozent, sei dafür nach wie vor das beste Werkzeug. Abschließend betont der Dozent, dass diese Vorlesung ein Überblick darüber ist, womit sich die numerische lineare Algebra befasst, und obwohl noch nicht alle Themen behandelt wurden, werden sie in den verbleibenden Sitzungen behandelt.
 

Vorlesung 11: Minimierung von ‖x‖ Vorbehaltlich Ax = b



Vorlesung 11: Minimierung von ‖x‖ Vorbehaltlich Ax = b

In dieser Vorlesung behandelt der Referent eine Reihe von Themen rund um die numerische lineare Algebra. Sie beginnen mit der Diskussion der Probleme, die beim Lösen nach Ax=b auftreten können, und gehen dann zum Gram-Schmidt-Prozess zum Finden einer orthogonalen Basis für einen Raum und zum modifizierten Gram-Schmidt-Verfahren zum Minimieren von „x“ in Abhängigkeit von Ax = b über . Der Referent führt auch das Konzept des Spaltenaustauschs oder Spaltenschwenkens in einem professionelleren Gram-Schmidt-Algorithmus ein und diskutiert eine Verbesserung des Standard-Gram-Schmidt-Verfahrens zur Orthonormalisierung der Spalten einer Matrix A. Sie berühren auch die Idee des Krylov-Raums um das Problem Ax=b zu lösen und die Wichtigkeit, eine gute Grundlage für die Minimierung von „x“ unter Berücksichtigung von Ax = b zu haben. Abschließend erwähnen sie, dass sie das Problem der Minimierung von x unter Berücksichtigung von Ax=b abgeschlossen haben und sich nun dem Problem des Umgangs mit sehr großen Matrizen zuwenden.

  • 00:00:00 In diesem Abschnitt erwähnt der Dozent drei Dinge. Erstens die Probleme, die beim Lösen nach Ax=b auftreten können, einschließlich wo A zu groß ist, um in den Kern zu passen, aber wo andere Methoden verfügbar sind. Zweitens zeigt er den groben ersten Entwurf von zwei Seiten seines Buches und erklärt den zweijährigen Prozess, den er durchläuft, um es zu perfektionieren und zu verbessern. Drittens diskutiert er die Minimierung unterschiedlicher Normen, wie z. B. L1 oder L2 oder max L Unendlichkeitsnorm, für die Bedingung des Lösens mit der Einschränkung einer erfüllten Gleichung, wodurch eine visuelle Darstellung des Unterschieds zwischen L1, L2 und L Unendlichkeitsnormen bereitgestellt wird.

  • 00:05:00 In diesem Abschnitt diskutiert der Sprecher den Gewinnpunkt für verschiedene Einheitsbälle in verschiedenen Normräumen, einschließlich L1, L2 und L unendlich. Er zeigt, wie man den Gewinnpunkt bzw. den Punkt findet, der die Linie jeweils zuerst berührt. Dann stellt er das Thema des Tages, Gram-Schmidt, vor, bei dem es darum geht, eine nicht-orthogonale Matrix orthogonal zu machen, indem ein anderer Satz von Vektoren gefunden wird, die denselben Raum überspannen, während sie orthogonal sind. Er skizziert die allgemeinen Fakten von Gram-Schmidt und erwähnt, dass es sich um ein Standardthema handelt, das in Kursen zur linearen Algebra gelehrt wird.

  • 00:10:00 In diesem Abschnitt erklärt der Professor den Gram-Schmidt-Prozess, der das Bild einer Matrix öffnet, um eine orthogonale Matrix mit orthonormalen Spalten Q1 bis Qn zu erhalten. Die Matrix R wird verwendet, um zu sagen, aus welchen Kombinationen die Qs bestehen, oder umgekehrt, um zu sagen, wie A mit dem endgültigen Q zusammenhängt. Die Gleichung für R ist Q transponiert mal A, und die Einträge in R sind nur das innere Produkt der Qs mit dem As. Der Professor zeigt, dass R wegen der orthogonalen Matrix Q nichts Geheimnisvolles ist. Der MATLAB-Befehl wäre QR von A statt Lu von A.

  • 00:15:00 In diesem Abschnitt erklärt die Vorlesung das Gram-Schmidt-Verfahren zum Finden einer orthogonalen Basis für einen Raum. Die Vorlesung beginnt mit einem nicht-orthogonalen Basissatz und das Ziel ist es, einen orthogonalen Basissatz zu konstruieren. Der Prozess beginnt damit, dass der erste Spaltenvektor der erste Basisvektor ist, und nimmt dann den zweiten Vektor und orthogonalisiert diesen mit dem ersten Vektor. Der nächste Schritt besteht darin, den dritten Vektor zu konstruieren, der orthogonal zu den ersten beiden Vektoren ist. Dies setzt sich fort, bis der gesamte Basissatz orthogonal aufgebaut ist. Schließlich dividieren wir jeden Vektor durch seine Norm, um jeden Basisvektor zu einem Einheitsvektor zu machen. Gram-Schmidt nimmt einen nicht-orthogonalen Basissatz und erzeugt einen orthogonalen Satz, der für Projektionsverfahren geeignet ist.

  • 00:20:00 In diesem Abschnitt diskutiert der Referent das modifizierte Gram-Schmidt-Verfahren zur Minimierung von „x“ unter Berücksichtigung von Ax = b. Sie erklären den Prozess der Subtraktion der Komponenten von Q1 und Q2 vom Vektor und der Überprüfung, ob der resultierende Vektor orthogonal ist. Sie gehen auch auf die Gefahr ein, während der Eliminierung Reihen in der richtigen Reihenfolge zu nehmen, und schlagen vor, die modifizierte Gram-Schmidt-Methode zu verwenden, um Rechenfehler zu vermeiden.

  • 00:25:00 In diesem Abschnitt des Vortrags diskutiert der Referent die Idee des Säulenaustauschs oder Säulenschwenkens in einem professionelleren Gram-Schmidt-Algorithmus. Ähnlich wie bei der Eliminierung können bei Gram-Schmidt, wenn der neue Teil der Spalte zu klein ist, Rundungsfehler eingebaut werden, die nicht entfernt werden können. Daher ist es wichtig, dass der Algorithmus die Größe des Pivots überprüft und gegebenenfalls Zeilen austauscht. Die Hauptidee hinter dem Säulenaustausch besteht darin, den neuen Teil der Säule mit allen anderen potenziellen Möglichkeiten zu vergleichen, um die größte Komponente zu finden, bevor über den nächsten Schritt entschieden wird. Dieser Vorgang ist entscheidend, um Rundungsfehler zu vermeiden, die die Genauigkeit des Ergebnisses beeinträchtigen können.

  • 00:30:00 In diesem Abschnitt erläutert der Referent eine Verbesserung des standardmäßigen Gram-Schmidt-Prozesses zur Orthonormalisierung der Spalten einer Matrix A. Anstatt nur die nächste Spalte in A zu berücksichtigen, umfasst die Verbesserung die Berücksichtigung aller verbleibenden Spalten in A when Orthonormalisieren jeder neuen Spalte. Der Sprecher argumentiert, dass dies nicht mehr Arbeit als die Standardmethode ist, da alle erforderlichen Subtraktionen trotzdem früher berechnet werden. Die Verbesserung beruht auf der Auswahl der größten verbleibenden Spalte und ähnelt der Auswahl des größten Drehpunkts bei der Gaußschen Eliminierung.

  • 00:35:00 In diesem Abschnitt stellt der Dozent die Idee des Krylov-Raums zur Lösung des großen Matrixproblems Ax=b vor. Der Krylov-Raum ist eine Kombination von Vektoren, die einen Raum überspannen, und der Dozent verwendet Kombinationen dieser Vektoren, um die Lösung der kleinsten Quadrate in diesem Raum, XJ, zu finden. Der Krylov-Raum wird bestimmt, indem A mit J-Vektoren bis zu A^k-1B multipliziert wird. Der Dozent sucht in diesem Raum nach der besten Lösung zur Lösung des Problems Ax=b. Allerdings gibt es bei dieser Methode noch einen Haken.

  • 00:40:00 In diesem Abschnitt erörtert der Sprecher die Bedeutung einer guten Grundlage für die Minimierung von „x“ unter Berücksichtigung von Ax = b. Die Basis sollte orthogonalisiert werden, um Berechnungen zu erleichtern, und hier kommen die Beiträge unserer Nolde- und Lan-Shows ins Spiel. Eine orthogonale Basis ist perfekt für eine Projektion, und der Sprecher erklärt die Gleichung, die Berechnungen erleichtert. Wenn die Qs orthogonal sind, können die Koeffizienten C leicht gefunden werden, indem das Punktprodukt des gegebenen Vektors X mit jedem Q berechnet wird und dann eine Q-Transponierung angewendet wird. Dies ermöglicht eine effiziente Lösung des Problems.

  • 00:45:00 In diesem Abschnitt des Vortrags diskutiert der Referent das Basiskonzept und wie man mit Gram-Schmidt- oder Krylov-Vektoren eine gute Basis findet. Der Referent merkt an, dass die Verwendung der Gram-Schmidt-Methode in diesem Fall vorzuziehen ist, und erwähnt auch Abschnitt 2.1 des Buchs zur numerischen linearen Algebra, der die gängigen Techniken auf dem Gebiet wie Krylov, Arnoldi und Lanczos zusammenfasst. Er empfiehlt „Numerical Linear Algebra“ von Golub und van Loan als hervorragendes Lehrbuch für diejenigen, die mehr über das Thema erfahren möchten.

  • 00:50:00 In diesem Abschnitt des Videos erwähnt der Sprecher, dass er das Problem der Minimierung von x unter Berücksichtigung von Ax=b abgeschlossen hat und sich nun dem Problem des Umgangs mit sehr großen Matrizen zuwendet.
 

Vorlesung 12. Berechnung von Eigenwerten und singulären Werten



12. Berechnung von Eigenwerten und singulären Werten

In diesem Video wird das QR-Verfahren zur Berechnung von Eigenwerten und Singulärwerten vorgestellt. Der Prozess beinhaltet, mit der gewünschten Matrix zu beginnen und sie in QR zu faktorisieren, wodurch eine obere Dreiecksmatrix R erstellt wird, die die nicht-orthogonale Basis mit der orthogonalen Basis verbindet. Der Prozess wird iteriert, bis die diagonalen Einträge klein werden, an welchem Punkt sie verwendet werden können, um die Eigenwerte zu approximieren. Der Sprecher erörtert auch ein Verschiebungsverfahren zum Berechnen von Eigenvektoren, um den Prozess zu beschleunigen. Die Vorteile der Verwendung von MATLAB für symmetrische Matrizen werden ebenfalls hervorgehoben. Das Video berührt auch das Konzept der Krylov-Vektoren zur Lösung von Eigenwertproblemen für große Matrizen.

  • 00:00:00 In diesem Abschnitt stellt der Professor die QR-Methode zur Berechnung von Eigenwerten und singulären Werten einer Matrix vor. Bei der QR-Methode beginnt man mit einer Matrix, deren Eigenwerte erwünscht sind, und faktorisiert sie in QR. Die Spalten der Matrix werden in eine orthogonale Basis umgewandelt, indem sie orthogonalisiert und eine Matrix R erstellt wird, die die nicht orthogonale Basis mit der orthogonalen Basis verbindet, die ein oberes Dreieck ist. Als nächstes beinhaltet das Verfahren, die Reihenfolge umzukehren und dasselbe noch einmal zu tun, um die nächste Matrix zu erzeugen. Der Professor behauptet, dass die Eigenwerte vor und nach der Transformation gleich sind und die Matrizen ähnlich sind, was für die Berechnung der singulären Werte der Matrix nützlich ist.

  • 00:05:00 In diesem Abschnitt erklärt der Professor den Prozess der Berechnung von Eigenwerten mittels QR-Faktorisierung. Der Prozess beinhaltet das mehrmalige Iterieren der QR-Faktorisierung, bis die diagonalen Einträge der resultierenden Matrix sehr klein werden. An diesem Punkt liegen die diagonalen Einträge nahe an den tatsächlichen Eigenwerten der ursprünglichen Matrix und können verwendet werden, um sie anzunähern. Der Professor hebt auch die schnelle Konvergenz der Methode hervor, wobei die Einträge außerhalb der Diagonale gewürfelt werden und sich schnell Null nähern, was die Methode extrem genau macht.

  • 00:10:00 In diesem Abschnitt erörtert das Video eine Verbesserung des Algorithmus zur Berechnung von Eigenvektoren, bei der eine Verschiebung eingeführt wird. Anstatt die Matrix A zu nehmen, nehmen sie die Matrix A - siI, wobei si ein Vielfaches der Identitätsmatrix ist. Dadurch werden alle Eigenwerte der Matrix A um si verschoben. Sie arbeiten dann mit dieser verschobenen Matrix, führen den Gram-Schmidt-Prozess durch und kehren die Reihenfolge um, um eine Matrix zu erhalten, die A so nahe wie möglich kommt. Schließlich machen sie die Verschiebung rückgängig, um eine neue Matrix A1 zu erhalten. Die Hoffnung ist, dass A1 immer noch ähnlich wie A ist, aber mit einer schnelleren Rechenzeit.

  • 00:15:00 In diesem Abschnitt diskutiert der Professor die QR-Methode zur Berechnung von Eigenwerten einer Matrix. Er demonstriert ein unvollständiges Beispiel, in dem er die QR-Methode verwendet, um zu zeigen, dass der untere dreieckige Teil der Matrix zu verschwinden beginnt und die Eigenwerte beginnen, auf der Diagonale aufzutauchen. Der Professor diskutiert dann, wie die Effizienz der QR-Methode verbessert werden kann, indem alle Nullen in der ursprünglichen Matrix ausgenutzt werden. Wenn zusätzliche Diagonalen mit Nullen vorhanden sind, kann das Verfahren beschleunigt werden, indem einige Schritte im QR-Faktorisierungsprozess übersprungen werden.

  • 00:20:00 In diesem Abschnitt erläutert der Referent, wie Eigenwerte und Singulärwerte berechnet werden. Es ist nicht möglich, alle Eigenwerte zu erhalten, da es unmöglich ist, einen ganzen unteren dreieckigen Teil gleich Null zu erhalten, was uns die Eigenwerte liefern würde. Dies liegt daran, dass die Eigenwerte eine Gleichung n-ten Grades lösen und vor Jahrhunderten bewiesen wurde, dass es unmöglich ist, eine Instant-Gleichung durch einfache Schritte zu lösen. Außerdem gibt es keine einfache Formel, um Lambdas oder singuläre Werte zu finden. Es ist jedoch möglich, so nahe zu kommen, wie wir möchten, indem wir mit der QR-Methode fortfahren und eine Matrix auf die Hessenberg-Form mit einem Dreieck plus einer weiteren Diagonalen, aber vielen Nullen reduzieren. MATLAB und andere Matrixsysteme verwenden la pack und Linpack, um diese Werte zu berechnen.

  • 00:25:00 In diesem Abschnitt des Videos erläutert der Referent die Vorteile der Verwendung von MATLAB und gibt einen Einblick in die Eigenschaften symmetrischer Matrizen. Er erklärt, dass bei einer symmetrischen Matrix mit Sicherheit vorhergesagt werden kann, dass sie nur eine Diagonale über der Hauptdiagonalen hat, was sie zu einer tridiagonalen Matrix macht. Dies reduziert die Zeit für die QR-Berechnung erheblich, da nur mit 2n Zahlen anstelle von N^2 gearbeitet werden muss. Der Redner geht auch kurz auf singuläre Werte ein und erklärt, dass sie die Eigenwerte einer transponierten Matrix sind, warnt jedoch davor, sie mit Determinanten zu berechnen, da dies langsam und schlecht konditioniert ist und zu Informationsverlust führt.

  • 00:30:00 In diesem Abschnitt erörtert der Sprecher das Konzept der Verwendung orthogonaler Matrizen zur Vereinfachung symmetrischer Matrizen, indem er sie tridiagonal macht, sodass ihre Eigenwerte leicht gefunden werden können. Dann stellt der Sprecher die Frage, was mit einer allgemeinen Matrix getan werden kann, um sie so zu vereinfachen, dass ihre singulären Werte unverändert bleiben. Der Referent verbindet diese Frage mit der SVD und diskutiert die Invarianz der singulären Werte bei bestimmten Operationen, wie etwa der Multiplikation mit einer orthogonalen Matrix. Die Frage, welche anderen Operationen die singulären Werte invariant lassen, bleibt dem Publikum offen.

  • 00:35:00 In diesem Abschnitt geht der Dozent auf den Effekt der Multiplikation einer orthogonalen Matrix Q auf eine Diagonalmatrix mit Singularwerten ein. Es wird gezeigt, dass die Multiplikation von Q mit der Diagonalmatrix die singulären Werte nicht ändert und dass dies auf beiden Seiten der Gleichung unter Verwendung verschiedener orthogonaler Matrizen erfolgen kann. Diese erhöhte Flexibilität ermöglicht es, die Matrix von tri-diagonal auf bi-diagonal zu reduzieren, wodurch der Algorithmus schneller wird, wenn er jeden Schritt durchläuft. Der Dozent diskutiert auch die Nützlichkeit einer zweidiagonalen Matrix zur Vereinfachung der Matrizenmultiplikation.

  • 00:40:00 In diesem Abschnitt erörtert der Referent die Berechnung von Eigenwerten und singulären Werten, insbesondere für Matrizen der Ordnung bis zu Tausend. Die SVD beinhaltet das Betrachten einer Transponierten einer Matrix, die tridiagonal wäre. Um singuläre Werte zu finden, kann man bis zur Transponierten einer Matrix vordringen, aber um ihre Eigenwerte zu finden, müsste sie symmetrisch und tridiagonal sein. Dieses Verfahren ist für Matrizen bis zu einer bestimmten Größe wirksam, darüber hinaus kann das Krylov-Verfahren für dünnbesetzte Matrizen verwendet werden. Krylovs Methode beschränkt die Matrix auf eine bestimmte Größe, typischerweise hundert mal hundert, und findet den Eigenvektor in diesem Raum.

  • 00:45:00 In diesem Abschnitt erläutert der Referent einen Ansatz namens Krylov-Vektoren, der zur Lösung von Eigenwertproblemen für große Matrizen verwendet werden kann. Durch Anwenden der Matrixoperation auf Krylov-Vektoren, die eine kleinere Dimension als die ursprüngliche Matrix haben, kann ein kleineres Eigenwertproblem erzeugt und gelöst werden. Obwohl sie keine genauen Eigenwerte liefern, können Krylov-Vektoren gute Annäherungen für bestimmte Probleme liefern. Der Referent stellt auch die Idee der Zufallsstichprobe für große Matrizen vor und erwähnt, dass dies in der nächsten Vorlesung untersucht wird.
 

Vorlesung 13: Randomisierte Matrixmultiplikation



Vorlesung 13: Randomisierte Matrixmultiplikation

Dieser Videovortrag behandelt das Konzept der randomisierten Matrixmultiplikation, bei der die Spalten der Matrix A und die entsprechenden Zeilen der Matrix B mit Wahrscheinlichkeiten abgetastet werden, die sich zu eins addieren. Der Mittelwert der Stichproben kann berechnet werden, um die richtige Antwort zu erhalten, aber es wird immer noch Varianz geben. Die Vorlesung geht weiter auf die Konzepte von Mittelwert und Varianz ein und wie man die besten Wahrscheinlichkeiten auswählt, die die Varianz minimieren. Der Prozess beinhaltet die Einführung einer unbekannten Variablen namens Lambda und die Ableitung davon, um den besten PJ zu finden. Der Fokus verschiebt sich dann auf die Frage, wie man die Wahrscheinlichkeiten gewichtet, wenn man sich anschaut, welche Spalten in einer Matrix größer oder kleiner sind. Der Dozent schlägt zwei Möglichkeiten vor: Wahrscheinlichkeiten nach der Norm zum Quadrat gewichten oder die Spalten der Matrix mischen und gleiche Wahrscheinlichkeiten verwenden. Insgesamt bietet das Video eine detaillierte Erklärung der randomisierten Matrixmultiplikation und des Prozesses zur Optimierung von Wahrscheinlichkeiten, um die kleinste Varianz zu erhalten.

  • 00:00:00 In diesem Abschnitt des Videos erläutert der Sprecher das Konzept der randomisierten Matrixmultiplikation, eine Idee, die unter die randomisierte lineare Algebra fällt. Dieses Verfahren wird für große Matrizen verwendet, indem die Spalten der Matrix A und die entsprechenden Zeilen der Matrix B abgetastet werden, aber nicht alle. Stattdessen werden verschiedene Teile zufällig mit Wahrscheinlichkeiten ausgewählt, die sich zu eins addieren. Durch die Berechnung des Mittelwerts der Stichproben kann die richtige Antwort erhalten werden, aber es wird immer noch Varianz geben. Das Ziel besteht dann darin, die besten Wahrscheinlichkeiten auszuwählen, die die Varianz minimieren. In der Vorlesung werden die Konzepte von Mittelwert und Varianz diskutiert und anhand eines Beispiels geübt.

  • 00:05:00 In diesem Abschnitt beschreibt der Sprecher einen randomisierten Abtastprozess für die Matrixmultiplikation. Der Prozess besteht darin, zwei Spalten mit Wahrscheinlichkeiten von jeweils der Hälfte zu nehmen, sie zu addieren und dann durch die Anzahl der Stichproben zu dividieren. Der Mittelwert der randomisierten Matrix wird dann unter Verwendung der Formel zur Berechnung des Durchschnitts der beiden Stichproben berechnet. Die Varianz wird mit einer der beiden Methoden berechnet, von denen die eine das Addieren der Wahrscheinlichkeiten verschiedener Ausgangswerte zum Quadrat umfasst, während die andere das Quadrat des durchschnittlichen Abstands vom Mittelwert umfasst.

  • 00:10:00 In diesem Abschnitt des Videos erörtert der Sprecher die Konzepte von Mittelwert und Varianz in der Statistik und wie sie sich auf ihr aktuelles Beispiel zur Berechnung der Varianz für randomisierte Matrixmultiplikation beziehen. Er erklärt, dass die Varianz ein Maß für die Summe der Quadrate zwischen Punkten auf beiden Seiten des Mittelwerts ist und dass er in seinem Beispiel die Quadrate der Differenzen zwischen seiner Ausgabe und dem Mittelwert summiert. Anschließend berechnet er die Varianz für sein spezifisches Beispiel, das jeweils zwei mögliche Ergebnisse und Wahrscheinlichkeiten beinhaltet.

  • 00:15:00 In diesem Abschnitt erörtert der Sprecher die Berechnung der Varianz und führt eine neue Formel für die Varianz ein, die Wahrscheinlichkeiten und Distanzen vom Mittelwert im Quadrat verwendet. Der Sprecher bringt auch das Konzept der randomisierten Stichprobe in der linearen Algebra zur Sprache und wie das Anpassen von Wahrscheinlichkeiten helfen kann, die Varianz zu verringern, wenn B viel größer als A ist. Die optimale Wahrscheinlichkeit ergibt sich aus dem Quadrat der Größe von B dividiert durch A und den Sprecherplänen um dies in Zukunft weiter zu diskutieren. Schließlich erwähnt der Sprecher eine zweite Formel für die Varianz, die die Wahrscheinlichkeit und den Abstand zum Quadrat des Ergebnisses beinhaltet.

  • 00:20:00 In diesem Abschnitt erörtert der Referent den Mittelwert und die Varianz der Wahrscheinlichkeit und demonstriert die beiden Methoden zur Berechnung des Quadrats des Mittelwerts bei der Subtraktion des Mittelwerts. Der Fokus verschiebt sich dann auf die Frage, wie man die Wahrscheinlichkeiten gewichtet, wenn man sich anschaut, welche Spalten in einer Matrix größer oder kleiner sind. Der Referent schlägt zwei Möglichkeiten vor: Wahrscheinlichkeiten nach der Norm zum Quadrat gewichten oder die Spalten der Matrix mischen und gleiche Wahrscheinlichkeiten verwenden. Der Sprecher favorisiert den ersten Ansatz und erklärt, wie man Wahrscheinlichkeiten proportional zum Quadrat der Norm verwendet.

  • 00:25:00 In diesem Abschnitt erklärt der Dozent, wie man Wahrscheinlichkeiten neu skaliert, sodass sie sich zu eins addieren. Dann bespricht er seinen Plan, Zeile Spalte und Spalte Zeile J mit bestimmten Wahrscheinlichkeiten zu wählen und wie er sie multiplizieren wird. Seine Annäherung, das ungefähre aB, ist die Summe aller dieser Abtastungen über S Abtastungen. Der Dozent erwähnt auch, dass geplant ist, die PJs so zu wählen, dass die Gesamtvarianz minimiert wird und dass der Mittelwert korrekt ist.

  • 00:30:00 In diesem Abschnitt erklärt der Dozent, wie man die Varianz für eine Stichprobe in der randomisierten Matrixmultiplikation berechnet. Der Mittelwert der Summe aller Stichproben wird berechnet, indem der Mittelwert einer Stichprobe mit der Anzahl der Stichproben multipliziert wird, was zum schwierigen Teil der Berechnung der Varianz führt. Die Varianzberechnung hängt von dem Stück ab, P1 bis PR, das mit Wahrscheinlichkeiten ausgewählt wurde, die von der Größe abhängen. Jede Stichprobe ist sicherlich falsch, weil sie Rang eins ist, also werden wir bei der Berechnung der Varianz definitiv nicht null erhalten. Die Varianz für eine Probe stellt sich als die Summe über die AJ AJ Transpositionswahrscheinlichkeit im Quadrat heraus. Der quadratische Mittelwert wird von dieser Berechnung abgezogen, um die vollständige Varianz zu erhalten.

  • 00:35:00 In diesem Abschnitt fügt der Sprecher die Werte für PJ ein und vereinfacht den Nenner zu einer Summe aus einem JPG von einem JP j bj-Normen. Indem er die erste Potenz addiert und C erhält, erhält der Sprecher den Ausdruck für die Varianz. Nachdem s Stichproben genommen und kombiniert wurden, ist die Varianz eine feste Zahl, nämlich C, die sie gerne klein machen würden. Der Sprecher möchte zeigen, dass dies die beste Wahl ist, indem er die Gewichte der Wahrscheinlichkeiten basierend auf der Länge von a mal der Länge von B wählt.

  • 00:40:00 In diesem Abschnitt diskutiert der Referent den letzten Schritt der Optimierung der Wahrscheinlichkeiten P1 bis PR für die Zeilen bzw. Spalten der Matrix A und die Zeilen der Matrix B unter der Bedingung, dass sie sich zu 1 addieren. Das Ziel besteht darin, den Varianzausdruck zu minimieren, indem die optimalen PJs ausgewählt werden. Der Redner führt die Lagrange-Idee ein, die Einschränkung in die Funktion einzubauen, indem eine unbekannte Zahl, oft als Lambda bezeichnet, eingeführt wird, um den besten PJ zu finden. Dieser Abschnitt schließt die Diskussion der randomisierten Stichprobenziehung ab und führt zum letzten Unterproblem.

  • 00:45:00 In diesem Abschnitt diskutiert der Dozent das Konzept von Lagranges Idee zur Optimierung von Wahrscheinlichkeiten unter der Bedingung, dass sie sich zu eins addieren. Der Prozess umfasst den Einbau der Gleichung in die Funktion und die Ableitung von Lambda, einer unbekannten Variablen. Nach dem Setzen der Ableitungen auf Null und dem Auflösen erhält man die endgültige empfohlene Antwort, die durch Bilden der Ableitung nach P validiert werden kann. Der Dozent erklärt auch, dass der Lagrange-Multiplikator die richtige Zahl ist, um die Gleichung gleich eins zu machen.

  • 00:50:00 In diesem Abschnitt erläutert der Professor den Prozess der Auswahl von Wahrscheinlichkeiten, um die kleinste Varianz in einem randomisierten System zu erhalten. Er erwähnt, dass die idealen Wahrscheinlichkeiten höher sind, wenn die Spalte größer ist, daher ist das Ermitteln der Längen der Spalten eine Voraussetzung vor der randomisierten Stichprobe. Obwohl die Berechnung der Varianz etwas schwierig sein kann, ermutigt er die Schüler, die Notizen langsam durchzugehen und die Formeln zum besseren Verständnis noch einmal durchzugehen, da sie die Wahrscheinlichkeit in Zukunft ernsthafter verwenden werden.
 

Vorlesung 14. Niedrige Rangänderungen in A und sein Inverses



14. Niedrige Rangänderungen in A und seiner Inversen

Das Video diskutiert das Konzept von Matrizen mit niedrigem Rang und ihre Bedeutung in Funktionsmatrizen, insbesondere die Matrixinversionsformel, die die Inverse einer N-mal-n-Matrix in Bezug auf eine einfachere 1-mal-1-Matrix findet. Die Formel ist nützlich, um das Inverse von Matrizen zu finden, die Störungen mit niedrigem Rang aufweisen, und kann den Prozess des Findens von Inversen vereinfachen. Der Referent zeigt, wie die Formel funktioniert, indem er die Formel für die zweite Matrix vorstellt und zeigt, wie dieselbe Logik angewendet wurde, um zu der Antwort zu gelangen. Das Video diskutiert auch praktische Anwendungen dieser Formel, insbesondere bei Problemen der kleinsten Quadrate und dem Kalman-Filter.

  • 00:00:00 In diesem Abschnitt diskutiert der Professor das Konzept von Matrizen mit niedrigem Rang und ihre Bedeutung in Funktionsmatrizen. Das Fokusthema liegt auf einer berühmten Formel namens Matrixinversionsformel, die auch als Änderungen des niedrigen Rangs in A und seiner Umkehrung bekannt ist. Die Formel findet die Umkehrung einer N-mal-n-Matrix in Bezug auf eine einfachere 1-mal-1-Matrix unter Verwendung einer UV-Transponierung und Division durch 1 minus der Transponierung von V mal U. Die Formel ist nützlich, um die Umkehrung von Matrizen zu finden, die niedrig sind ordnen Störungen ein und können verwendet werden, um den Prozess des Auffindens von Inversen zu vereinfachen. Der Professor erklärt, wie diese Formel funktioniert und ihre praktischen Anwendungen.

  • 00:05:00 In diesem Abschnitt erörtert der Sprecher, wie die Änderung einer Matrix um Rang 1 zu einer Änderung ihrer Umkehrung um Rang 1 führt. Die Formel, die er präsentiert, berechnet eine N-mal-n-Umkehrung in Bezug auf eine 1-mal-1-Umkehrung, was sehr nützlich ist. Der Sprecher demonstriert dann, wie man die Formel überprüft, indem man die behauptete Inverse mit der ursprünglichen Matrix multipliziert und hofft, eine Identitätsmatrix zu erhalten. Der Referent zeigt, wie die Formel funktioniert, indem er die Formel für die zweite Matrix vorstellt und zeigt, wie dieselbe Logik angewendet wurde, um zu der Antwort zu gelangen.

  • 00:10:00 eine Formel für eine niedrige Rangänderung in Matrix A und ihre Inverse. Die Formel beinhaltet das Inverse einer N-mal-n-Matrix, kann aber auf eine K-mal-K-Matrix umgeschaltet werden, was eine kleinere Störung der Identitätsmatrix ist. Die Formel wird durch eine Überprüfung als wahr bewiesen und kann nützlich sein, um eine Matrix A zu stören. Die Namen der Personen, die diese Formel entdeckt haben, sind ebenfalls aufgeführt.

  • 00:15:00 In diesem Abschnitt diskutiert der Sprecher die Änderungen, die auftreten, wenn man die Inverse einer Matrix A mit niedrigem Rang nimmt. Sie verwenden algebraische Manipulationen, um zu zeigen, dass es bestimmte Terme gibt, die sein können, wenn man die Inverse von A nimmt eliminiert, was zu einem vereinfachten Ausdruck führt. Der Sprecher merkt an, dass er zwar in der Lage ist, die Formel zu beweisen, indem er überprüft, ob sie die Identitätsmatrix erzeugt, es aber wichtig ist zu überlegen, wie die Formel überhaupt hergeleitet werden kann. Sie schlagen vor, die Formel zu verwenden, um ein lineares System mit einer neuen Messung oder Beobachtung nach der Methode der kleinsten Quadrate zu lösen.

  • 00:20:00 In diesem Abschnitt erläutert der Referent den Umgang mit neuen Messungen bei der Lösung von Kleinste-Quadrate-Aufgaben. Bei einer rechteckigen Matrix A führt das Hinzufügen einer weiteren Messung oder eines Datenpunkts zur Lösung zu einer neuen Matrix und einer zu lösenden rechten Seite. Anstatt jedoch die Matrixmultiplikation A^TA neu zu berechnen, beschreibt der Sprecher, wie die Matrix mit der neuen Messung erweitert, transponiert und zur Berechnung der aktualisierten Lösung verwendet wird. Indem bereits berechnete Daten verwendet werden, ermöglicht dies eine recheneffizientere Lösung von Problemen der kleinsten Quadrate.

  • 00:25:00 In diesem Abschnitt erörtert der Sprecher die Störung von A und seiner Umkehrung mit neuen Daten, die eine Rang-1-Änderung in der A-Transponierung von A liefern. Dieses Konzept ist auf Probleme der kleinsten Quadrate anwendbar, und der Kalman-Filter ist ein Beispiel für a rekursive Methode der kleinsten Quadrate, die diesen Ansatz verwendet. Der Kalman-Filter wird beim Lenken von Flugkörpern und Satelliten verwendet, indem neue Daten verfolgt und die Lösung aktualisiert werden, was eine wichtige Anwendung dieses Konzepts in der Praxis darstellt.

  • 00:30:00 In diesem Abschnitt des Videos erklärt der Sprecher, wie die Sherman-Morrison-Woodbury-Formel angewendet wird, um Änderungen des niedrigen Rangs in A und seiner Umkehrung zu berechnen. Sie erwähnen, dass der Kalman-Filter, der für dynamische kleinste Quadrate verwendet wird, zwei zusätzliche Faktoren hat, die berücksichtigt werden – die Kovarianzmatrix und die Zustandsgleichung. Die Kovarianzmatrix befasst sich damit, wie Fehler korreliert sind, und die Zustandsgleichung gibt an, wie viel sich der Satellit (im Beispiel) bewegen sollte. Der Kalman-Filter ist eine verbesserte Version von rekursiven Quadraten, die sich mit sich ändernden Messungen befasst, während ein großer Teil unverändert bleibt.

  • 00:35:00 In diesem Abschnitt diskutiert der Sprecher die Verwendung der Low-Rank-Update-Formel beim Lösen linearer Systeme. Die Formel beinhaltet, die Matrix eines gelösten Problems um Rang eins zu stören und die Inverse der ursprünglichen Matrix zu verwenden, um das neue Problem schnell zu lösen. Dieser Ansatz kann die zum Lösen eines neuen Problems erforderliche Zeit erheblich verkürzen und ist besonders nützlich für große Matrizen, bei denen herkömmliche Eliminierungsmethoden zeitaufwändig wären.

  • 00:40:00 In diesem Abschnitt erklärt der Referent, wie man die Inverse einer Matrix findet, indem man Lösungen für verschiedene Probleme kombiniert. Durch die Faktorisierung von Matrix A in Lu wird die ganze harte Arbeit auf der linken Seite erledigt, und das Finden der Lösungen für verschiedene rechte Seiten erfordert nur eine Rücksubstitution. Durch die Verwendung der Sherman-Morrison-Woodbury-Formel kann die Antwort X durch Kombinieren der Lösungen W und Z erreicht werden. Die Formel ändert die Lösung W um einen Term, der von Sherman-Morrison Woodbury stammt, und der Term im Zähler ist ein Vielfaches von Z mal X.

  • 00:45:00 In diesem Abschnitt erörtert der Redner, wie Änderungen des niedrigen Rangs in einer Matrix A ihre Umkehrung beeinflussen können, und stellt eine Formel zum Invertieren einer N-mal-N-Matrix durch Umschalten und Invertieren einer K-mal-K-Matrix bereit. Die Formel beinhaltet das Subtrahieren einer Kopie der Umkehrung und das Hinzufügen einiger anderer Teile und führt letztendlich zu einer Rang-K-Änderung der ursprünglichen Umkehrung. Der Redner stellt fest, dass diese Formel praktische Anwendungen hat, und ermutigt die Zuschauer, sie zum späteren Nachschlagen aufzuschreiben.

  • 00:50:00 In diesem Abschnitt diskutiert der Sprecher die Umkehrung einer K-mal-K-Matrix und erkennt die Fülle an Formeln an, die in den letzten 50 Minuten behandelt wurden. Der Abschnitt schließt mit der Feststellung, dass die Anmerkungen einige Anwendungen abdecken und sich mit anderen Aspekten von niedrigem Rang befassen werden.
 

Vorlesung 15. Matrizen A(t) Abhängig von t, Ableitung = dA/dt



15. Matrizen A(t) Abhängig von t, Ableitung = dA/dt

Dieses Video behandelt verschiedene Themen im Zusammenhang mit Matrizen, einschließlich Änderungen in Matrizen und ihrer Inversen sowie Änderungen in Eigenwerten und singulären Werten im Laufe der Zeit. Der Referent erläutert Schlüsselformeln zur Berechnung dieser Änderungen und betont die Bedeutung des Verständnisses der Analysis in der linearen Algebra. Darüber hinaus diskutiert die Vorlesung die Bedeutung der Normalisierung und untersucht Interlacing-Theoreme für Eigenwerte sowohl in symmetrischen als auch in Rang-1-Matrizen. Abschließend schließt das Video mit einem Rückblick auf die behandelten Themen und dem Versprechen, diese in zukünftigen Vorlesungen zu vertiefen.

  • 00:00:00 In diesem Abschnitt erörtert der Sprecher die Änderungen in Matrizen, Eigenwerten und singulären Werten, wenn sich eine Matrix ändert. Der Schwerpunkt liegt auf dem Verständnis der Formeln für die Änderung der inversen Matrix, der Ableitung der inversen Matrix und der Änderung von Eigen- und Singulärwerten bei Änderung einer Matrix. Der Referent erklärt, dass es zwar keine exakte Formel für die Änderung von Eigenwerten und singulären Werten geben muss
    möglich, können sie dennoch Ungleichheiten ableiten, um zu verstehen, wie groß die Veränderung sein könnte. Die Vorlesung behandelt auch den Aufbau der Matrix A, die von der Zeit (T) und der Inversen A-Inversen abhängt.

  • 00:05:00 In diesem Abschnitt diskutiert der Sprecher eine Identität in der Infinitesimalrechnung, die die Diskussion des vorherigen Abschnitts über die Umkehrung von Matrizen ergänzt. Die Formel besagt, dass die Ableitung der inversen Matrix gleich dem negativen Einmalen der Inversen der Matrix ist, multipliziert mit der Ableitung der Matrix und der Inversen der Matrix. Der Sprecher erklärt, wie man die Ableitung der inversen Matrix findet, indem er sie „Änderung der Umkehrung“ nennt und beide Seiten der Formel durch Delta T dividiert. Schließlich wendet der Sprecher einen Kalkül an, um Delta T auf Null gehen zu lassen, was zu einem intuitiven Ergebnis führt Verständnis der Formel. Der Redner drückt auch seine Meinung zur Betonung der Infinitesimalrechnung in der Hochschulmathematik aus und stellt fest, dass sie die lineare Algebra überschattet.

  • 00:10:00 In diesem Abschnitt erläutert der Referent die Formel für die Ableitung einer Matrix A als dA/dt nach der Zeit t, wenn Delta T gegen Null geht. Das Verhältnis Delta a dividiert durch Delta T hat eine Bedeutung, und wenn sich Delta T Null nähert, wird die Gleichung invers. Die Ableitung von eins über X im Eins-zu-eins-Fall ist nur 1 über X im Quadrat, und dies ist parallel zu Formeln, bei denen Delta a die volle Größe, aber einen niedrigen Rang hat. Der Schwerpunkt des Vortrags verlagert sich dann auf die Lambda-Eigenwerte und wie sie sich ändern, wenn sich eine Matrix ändert, mit zwei Möglichkeiten, einer kleinen Änderung und einer vollständigen Größenordnung einer Änderung. Die Vorlesung endet mit Fakten rund um Eigenwerte und Eigenvektoren.

  • 00:15:00 In diesem Abschnitt wird das Konzept der Eigenvektoren und Eigenwerte für Matrizen erklärt, die von einem Parameter abhängen. Die Matrix A wird im Detail untersucht, mit dem Eigenvektor X auf der linken Seite, der den gleichen Eigenwert wie AX hat. Im Gegensatz dazu wird der Eigenvektor Y für eine symmetrische Matrix A in gleicher Weise mit der Transponierten von A oder AT verwendet. Die Wichtigkeit der Normalisierung, insbesondere Y-Transponierung mal X gleich eins, wird betont. Der Autor fährt dann damit fort, die Ableitung einer Formel zu nehmen, und diskutiert, wie die Gleichung verzerrt werden kann, um sie in diesen neuen Kontext einzupassen.

  • 00:20:00 In diesem Abschnitt erklärt der Referent, wie die Ableitung einer Matrix verwendet werden kann, um die Ableitung ihrer Eigenwerte und Eigenvektoren bei Zeitänderungen zu finden. Mit Hilfe der Produktregel leiten sie eine Formel für die Ableitung des Produkts dreier zeitabhängiger Glieder her. Durch Umordnen der Terme und Anwendung der Diagonalisierungsformel gelangen sie zu einer einfachen Formel für die Ableitung des Eigenwerts. Der Referent merkt an, dass dies zwar eine klassische Technik ist, aber nicht immer allgemein bekannt ist oder in Kursen gelehrt wird.

  • 00:25:00 In diesem Abschnitt diskutiert der Sprecher eine Formel zum Ermitteln der Ableitung eines Eigenwerts unter Verwendung der Änderungsrate der Matrix und der Eigenvektoren links und rechts. Sie vereinfachen die Formel, um zu zeigen, dass sich zwei Terme gegenseitig aufheben und der verbleibende Term die richtige Antwort für die Ableitung ist. Sie verwenden die Tatsache, dass die Ableitung von Eins Null ist, um diese Aufhebung zu beweisen. Der Sprecher erwähnt auch, dass diese Formel nicht die Ableitung des Eigenvektors beinhaltet und auch zum Auffinden von Ableitungen auf höherer Ebene verwendet werden kann.

  • 00:30:00 In diesem Abschnitt diskutiert der Sprecher die Änderung der Eigenwerte nach einer Rang-Eins-Änderung einer symmetrischen Matrix. Er stellt fest, dass die Änderung ein echter Vektor und kein Differential ist, sodass es keine genaue Formel für die neuen Eigenwerte gibt. Er teilt jedoch einige bekannte Fakten, wie z. B. dass die Eigenwerte in absteigender Reihenfolge sind und die Änderung des ersten Ranges positiv semidefinit ist. Er fordert das Publikum auch auf, den Eigenvektor der uu-Transponierungsmatrix zu berücksichtigen, und erklärt, dass es sich um eine vollständige n mal n Matrixspalte mal einer Reihe handelt. Er schließt mit der Feststellung, dass die sich aus dieser Berechnung ergebende Zahl größer als Null ist.

  • 00:35:00 In diesem Abschnitt erörtert der Sprecher eine symmetrische Matrix und was passiert, wenn ihr eine Rang-Eins-Matrix hinzugefügt wird. Sie schlussfolgern, dass dies zu positiven semidefiniten Matrizen führt und die neuen Eigenwerte (Lambdas) größer sind als die ursprünglichen Eigenwerte (Gammas). Der Größenunterschied ist jedoch nicht signifikant, und es gibt ein Theorem namens "Interlacing", das sicherstellt, dass die Eigenwerte nicht aneinander vorbeigehen. Insbesondere ist Lambda 1 größer als Gamma 1, aber Lambda 2 ist kleiner als Gamma 1. Dies ist ein nützliches Theorem, das die Reihenfolge der Eigenwerte garantiert, wenn eine Matrix mit positivem Rang eins zu einer symmetrischen Matrix hinzugefügt wird.

  • 00:40:00 In diesem Abschnitt diskutiert der Professor die Eigenwerte einer Rang-2-Matrix, die aus einer symmetrischen Matrix und einer Rang-1-Änderung resultieren. Er erklärt, dass der Rang der Änderungsmatrix 2 ist, was auf zwei Nicht-Null-Eigenwerte hinweist, und ihre positive halbbestimmte Natur bedeutet, dass die Eigenwerte zunehmen würden, wenn sie zur ursprünglichen Matrix hinzugefügt würden. Er enthüllt jedoch ein Theorem, das besagt, dass die Eigenwerte nicht höher als die ursprünglichen Eigenwerte werden können, wenn eine positive semidefinite Matrix hinzugefügt wird. Er wendet dies auf die Alpha-Werte an und vergleicht sie mit den Lambdas und kommt schließlich zu dem Schluss, dass der Alpha-2-Wert Lambda 1 nicht passieren kann und der Alpha-3-Wert unbekannt bleibt.

  • 00:45:00 In diesem Abschnitt erklärt der Dozent die Verschachtelung von Eigenwerten am Beispiel einer symmetrischen Matrix. Die reduzierte Version dieser Matrix hat auch Eigenwerte, und sie verschachteln sich mit den Eigenwerten der ursprünglichen Matrix. Der Dozent äußert jedoch Bedenken hinsichtlich der Verschachtelung von Eigenwerten, wenn der Rang geändert wird. Wenn der neue Eigenvektor mit einer großen Zahl multipliziert wird, kann er möglicherweise den Eigenwert nach oben verschieben, was dem Interlacing-Theorem zu widersprechen scheint. Der Dozent belässt dies als Frage zur Beantwortung in der nächsten Vorlesung.

  • 00:50:00 In diesem Abschnitt geht der Dozent auf Eigenwerte und Eigenvektoren ein und warum ein bestimmter Eigenvektor mit einem Eigenwert Lambda 2 plus 20 die bisherigen Aussagen nicht entkräftet. Die Vorlesung endet mit einer Wiederholung der behandelten Themen und einem Hinweis, die Diskussion in der nächsten Klasse fortzusetzen.