[PYTHON] Spärliche Modellierung: 2.3 Konstruktion der Glasman-Matrix
Ich habe versucht, die Glasman-Matrix in Kapitel 2.3 von Sparse Modeling von Michael Elad zu erstellen und von Toru Tamaki in Python übersetzt.
In spärlicher Modellierung
Je näher $ \ mathbf {A} $ an der orthogonalen Matrix liegt (je näher $ \ mathbf {A} ^ T \ mathbf {A} $ an $ \ mathbf {I} $ liegt), desto näher ist die Lösung von $ P_0 $. Wird einfacher sein.
Da $ \ mathbf {A} $ keine quadratische Matrix ist, können die nicht diagonalen Elemente von $ \ mathbf {A} ^ T \ mathbf {A} $ nicht alle 0 sein und ihre Untergrenze
Es wird sein. Dieses $ \ mu (\ mathbf {A}) $ heißt __ gegenseitige Kohärenz __ der Matrix $ \ mathbf {A} $.
Wenn $ \ mathbf {x} $ von einem Algorithmus als Lösungskandidat für $ P_0 $ gefunden wird, ist $ \ mathbf {x} $
Man kann sagen, dass $ \ mathbf {x} $ die einzige spärliche Lösung unter der Bedingung $ \ mathbf {b} = \ mathbf {Ax} $ ist, wenn die Bedingung von erfüllt ist (Satz 2.5). .. Mit anderen Worten, wenn Sie nach einem spärlichen $ \ mathbf {x} $ suchen, das $ \ mathbf {b} = \ mathbf {Ax} $ mit einem ungefähren Algorithmus erfüllt, ist der Wert von $ \ mu (\ mathbf {A}) $ Man kann sagen, je kleiner der Wert, desto einfacher ist es, die Antwort auf einer lockeren Basis zu finden.
Deshalb ist es umso besser, je geringer die gegenseitige Kohärenz von $ \ mathbf {A} $ ist.
Eine Matrix, deren gegenseitige Kohärenz mit der Untergrenze übereinstimmt, wird als Glasman-Matrix bezeichnet. Man kann sagen, dass die Glasman-Matrix eine $ n × m $ -Matrix ist, die einer orthogonalen Matrix so nahe wie möglich kommt.
Ich denke, dass es nützlich wäre, das $ P_0 $ -Problem zu lösen, wenn eine solche Glasman-Matrix konstruiert werden könnte, aber ich habe die Glasman-Matrix in "2.3 Konstruktion der Glasman-Matrix" der Sparse Modeling numerisch berechnet. Ich fand den MATLAB-Code dafür und portierte ihn nach Python (mit einer langen Einführung).
Der Algorithmus selbst verkleinert einen großen Wert der Gramm-Matrix $ \ mathbf {G} = \ mathbf {A} ^ T \ mathbf {A} $ und führt dann eine SVD-Konvertierung durch, sodass der Rang der Matrix N ist. Bei der Iteration wurde eine Grammmatrix $ \ mathbf {G} $ erhalten, deren nicht diagonaler Komponentenwert nahe der Untergrenze lag, und schließlich wurde die Grammmatrix $ \ mathbf {G} $, die iterativ durch die SVD-Konvertierung verarbeitet wurde, eine Glasman-Matrix. Sie erhalten $ \ hat {\ mathbf {A}} $.
Siehe ipynb auf Github unten für Python-Code zum Erstellen der Glasman-Matrix. https://github.com/kibo35/sparse-modeling/blob/master/ch02.ipynb
Es ist verdächtig, $ \ hat {\ mathbf {A}} $ zu erhalten, das am Ende zur Glasman-Matrix wurde, aber ich denke, dass die Verarbeitung der Gramm-Matrix das gleiche Ergebnis liefert wie das Lehrbuch.
Oben links ist die Grammmatrix $ \ mathbf {G} = \ mathbf {A} ^ T \ mathbf {A} $ der redundanten Systemmatrix $ \ mathbf {A} $ (50 Zeilen x 100 Spalten), die durch die Normalverteilung gegeben ist. Ich werde. Oben rechts ist die Gramm-Matrix nach 10000 Iterationen.
Wenn Sie das Bild mit den absoluten Werten in der unteren Reihe betrachten, können Sie sehen, dass die Werte der nicht diagonalen Komponenten einheitlich sind.
Die obige Abbildung zeigt die Werte der nicht diagonalen Komponenten der Grammmatrix bei jeder Iteration.
Wie auch immer, aus Kapitel 2 der Sparse Modeling können wir sehen, dass die gegenseitige Kohärenz der redundanten Systemmatrix $ \ mathbf {A} $ $ \ mu (\ mathbf {A}) $ ist Wenn Sie den Wert von (Wert) kennen und eine Lösung $ \ mathbf {x} $ finden, deren $ L_0 $ -Norm kleiner als ein bestimmter Schwellenwert ist, der aus diesem Wert erhalten wird, können Sie sagen, dass es sich um eine eindeutige Lösung handelt. Geben Sie also Ihr Bestes. Lösen wir das Problem $ P_0 $.