[PYTHON] Sparse Modeling: Kapitel 3 Tracking-Algorithmus
Sparse Modeling Kapitel 3 Implementierte den Tracking-Algorithmus in Python.
Jupyter-Notizbuch mit einer Zusammenfassung des Codes und der experimentellen Ergebnisse.
Implementierte die folgende gierige Methode und die konvexe Relaxationsmethode. IRLS ist ein wenig misstrauisch ...
Gierige Methode
- Orthogonale Matching-Verfolgung (OMP)
- Matching Verfolgung (MP)
- Schwache Matching-Verfolgung (WMP)
- Schwellenwertalgorithmus
Konvexe Entspannungsmethode
- Iterative-Reweighted-Lease-Sqaures (IRLS)
Übersicht über die Giermethode
Initialisieren
Als $ k = 0 $
- Anfangslösung $ \ mathbf {x} ^ {0} = \ mathbf {0} $
- Anfangsrest $ \ mathbf {r} ^ {0} = \ mathbf {b} $
- Erste Unterstützung für Lösung $ S ^ {0} = \ Emptyset $
Hauptschleife
Führen Sie die folgenden Schritte als $ k \ leftarrow k + 1 $ aus.
- Fehlerberechnung, Support-Update: Spalte $ \ mathbf {a} _ {j} $, die den Rest $ \ mathbf {r} ^ {k} $ von $ \ mathbf {A} $ reduzieren kann Zu $ S ^ k $
1.Vorläufiges Welt-Update:
\\| \mathbf{Ax}-\mathbf{b}\\|^{2}_{2} \, \rm{subject} \, \rm{to} \, \rm{Support}\\{\mathbf{x}\\}=S^{k} Optimale Lösung von\mathbf{x}^{k} Lassen. - Restaktualisierung: Berechnen Sie $ \ mathbf {r} ^ {k} = \ mathbf {b} - \ mathbf {Ax} ^ {k}
. 1.Stoppbedingung: Wenn \|\mathbf{r}^{k}\|<\epsilon_{0}$Wenn ja, endet es, sonst wiederholt es sich.
Bei der Fehlerberechnung und Support-Aktualisierung wird das innere Produkt aller Spalten $ \ mathbf {a} _ {j} $ von $ \ mathbf {A} $ und der Rest $ \ mathbf {r} $ berechnet und der Absolutwert des inneren Produkts berechnet. Fügen Sie der Unterstützung die Spalte hinzu, die maximiert wird. Mit anderen Worten, Spalten parallel zu $ \ mathbf {r} $ werden der Reihe nach hinzugefügt.
Unterschiede im Gier-Algorithmus
- OMP
- An der Spitze bleiben
- MP
- Die vorläufige Lösung wurde nur mit neu hinzugefügtem $ \ mathbf {a} _j $ anstelle von $ \ mathbf {A} $ aktualisiert
- WMP
- Fügen Sie den Hyperparametern den Skalar $ t , (0 <t <1) $ hinzu
*Mit Fehlerberechnungen und Support-Updates
\mathbf{r}^{k-1} Der absolute Wert des inneren Produkts mitt\\|\mathbf{r}^{k-1}\\| Mehr als\mathbf{a}_j Wird gefunden, wird die Berechnung gestoppt. Der Rest ist der gleiche wie MP. - Schwellenwertalgorithmus
- $ K $ Anzahl der Basisfunktionen hinzugefügt, die zur Unterstützung von Hyperparametern enthalten sind
- $ k $ vom Anfang von $ \ mathbf {a} _j $, der mit $ \ mathbf {b} $ einen großen absoluten Wert des inneren Produkts hat, wird unterstützt. Lösen Sie danach das Problem der kleinsten Quadrate und setzen Sie es als $ \ mathbf {x} $.
IRLS-Übersicht
- Lösen Sie das Problem $ \ left (P_ {1} \ right) $ anstelle des Problems $ \ left (P_ {0} \ right) $.
- Lösen Sie das Problem $ \ left (P_ {1} \ right) $, indem Sie die Norm $ L_ {1} $ mit der gewichteten Norm $ L_ {2} $ approximieren.
- Es muss viel wiederholt werden, um eine spärliche Lösung zu erhalten.
Initialisieren
Als $ k = 0 $
- Anfängliche ungefähre Lösung $ \ mathbf {x} ^ {0} = \ mathbf {1} $ (alle 1 Vektoren)
- Anfangsgewichtsmatrix $ \ mathbf {X} ^ {0} = \ mathbf {I} $
Hauptschleife
Führen Sie die folgenden Schritte als $ k \ leftarrow k + 1 $ aus.
- Minimum-Quadrat-Methode: Lineare simultane Gleichungen
$ \ mathbf {x} \ _ {k} = \ mathbf {X} \ _ {k-1} ^ {2} \ mathbf {A} ^ {T} (\ mathbf Löse und approximiere {A} \ mathbf {X} _ {k-1} ^ {2} \ mathbf {A} ^ {T}) ^ {+} \ mathbf {b} $ direkt oder mit iterativen Methoden Holen Sie sich die Lösung $ \ mathbf {x} \ k. 1.Gewichtsaktualisierung: X{k}(j,j)=|x_{k}(j)|^{0.5}Als Gewichtsdiagonalmatrix \mathbf{X}Aktualisieren 1.Stoppbedingung: Wenn \|\mathbf{x}_{k}-\mathbf{x}_{k-1}\|_{2}$Wenn der vorgegebene Schwellenwert kleiner ist, wird er beendet, andernfalls wird er wiederholt.
Experiment
Simulation
$ \ mathbf {x} $ 50-dimensionaler Vektor $ \ mathbf {b} $ 30-dimensionaler Vektor $ \ mathbf {A} $ 30 × 50-dimensionale Matrix, Spaltennormalisierung einheitlicher Zufallszahlen von $ [-1, 1) $
- $ \ mathbf {x} $ Die Anzahl der Nicht-Null-Elemente beträgt $ k $, und der Wert der Nicht-Null-Elemente ergibt sich aus einer gleichmäßigen Verteilung im Bereich von $ [-2, -1] \ cup [1, 2] $ Extrakt.
- Simulieren Sie jeweils 200 Mal mit $ k = 1, ..., 10 $
Index
- $ L_2 $ Norm des geschätzten $ \ mathbf {\ hat {x}} $ und des wahren $ \ mathbf {x} $
*Geschätzt
\mathbf{\hat{x}} Und wahr\mathbf{x} Abstand zwischen den Stützen$dist(\hat{S},S)=\frac{max\\{|\hat{S}|, |S| \\} - |\hat{S}\cap S|}{max\\{|\hat{S}|,|S|\\}} $ - Nehmen Sie den Durchschnitt von 200 Simulationen.
Ergebnis
Durchschnittlicher $ L_ {2} $ Fehler
- Wenn k zunimmt, nimmt der Fehler zu.
- Der IRLS-Fehler ist klein, aber natürlich, da es sich um einen $ L_ {2} $ -Fehler handelt
- OMP gibt auch sein Bestes. Es ist schnell
Durchschnittlicher Abstand zwischen den Stützen
- Wenn k niedrig ist, hat sich der Abstand zwischen den IRLS-Unterstützungen vergrößert. Das Lehrbuch enthält so etwas nicht, daher kann es unzureichend oder fehlerhaft sein
- OMP gibt auch sein Bestes.
Erwägung
- OMP Ich gebe mein Bestes
- IRLS stimmt nicht mit den Ergebnissen des Lehrbuchs überein, daher muss die Ursache untersucht werden