[PYTHON] Modélisation parcimonieuse: 2.3 Construction de la matrice Glasman
J'ai essayé de construire la matrice Glasman dans le chapitre 2.3 de Sparse Modeling de Michael Elad et traduit par Toru Tamaki en Python.
Dans la modélisation clairsemée
Ici, plus $ \ mathbf {A} $ est proche de la matrice orthogonale (plus $ \ mathbf {A} ^ T \ mathbf {A} $ est proche de $ \ mathbf {I} $), plus on obtient $ P_0 $. Sera plus facile.
Puisque $ \ mathbf {A} $ n'est pas une matrice carrée, les éléments hors diagonale de $ \ mathbf {A} ^ T \ mathbf {A} $ ne peuvent pas tous être 0, et sa limite inférieure est
Ce sera. Ce $ \ mu (\ mathbf {A}) $ est appelé __ cohérence mutuelle __ de la matrice $ \ mathbf {A} $.
Quand $ \ mathbf {x} $ est trouvé comme solution candidate pour $ P_0 $ par un algorithme, $ \ mathbf {x} $
On peut dire que $ \ mathbf {x} $ est la seule solution éparse sous la contrainte de $ \ mathbf {b} = \ mathbf {Ax} $ si la condition de est satisfaite (Théorème 2.5). .. En d'autres termes, si vous recherchez un $ \ mathbf {x} $ clairsemé qui satisfait $ \ mathbf {b} = \ mathbf {Ax} $ avec un algorithme approximatif, la valeur de $ \ mu (\ mathbf {A}) $ On peut dire que plus la valeur est petite, plus il est facile de trouver la réponse sur une base plus lâche.
C'est pourquoi plus la cohérence mutuelle de $ \ mathbf {A} $ est faible, mieux c'est.
Une matrice dont la cohérence mutuelle correspond à la limite inférieure est appelée matrice de Glasman. On peut dire que la matrice de Glasman est une matrice $ n × m $ aussi proche que possible d'une matrice orthogonale.
Je pense qu'il serait utile de résoudre le problème $ P_0 $ si une telle matrice Glasman pouvait être construite, mais j'ai calculé numériquement la matrice Glasman dans "2.3 Construction de la matrice Glasman" de la modélisation Sparse. J'ai trouvé le code MATLAB à faire, alors je l'ai porté en Python (avec une longue introduction).
L'algorithme lui-même réduit une grande valeur de la matrice de gramme $ \ mathbf {G} = \ mathbf {A} ^ T \ mathbf {A} $ puis effectue une conversion SVD de sorte que le rang de la matrice soit N. Lors de l'itération, une matrice gramme $ \ mathbf {G} $ dont la valeur de composante hors diagonale était proche de la limite inférieure a été obtenue, et enfin, la matrice gramme $ \ mathbf {G} $, qui a été traitée itérativement par la conversion SVD, est devenue une matrice Glasman. Vous obtenez $ \ hat {\ mathbf {A}} $.
Voir ipynb sur Github ci-dessous pour le code Python qui construit la matrice Glasman. https://github.com/kibo35/sparse-modeling/blob/master/ch02.ipynb
Il est suspect d'obtenir $ \ hat {\ mathbf {A}} $ qui est devenu la matrice Glasman à la fin, mais je pense que le traitement de la matrice gramme donne le même résultat que le manuel.
Le coin supérieur gauche est la matrice gramme $ \ mathbf {G} = \ mathbf {A} ^ T \ mathbf {A} $ de la matrice système redondante $ \ mathbf {A} $ (50 lignes x 100 colonnes) donnée par la distribution normale. Je vais. Le coin supérieur droit est la matrice de gramme après 10000 itérations.
Si vous regardez l'image avec les valeurs absolues dans la ligne inférieure, vous pouvez voir que les valeurs des composants hors diagonale sont uniformes.
La figure ci-dessus trace les valeurs des composantes hors diagonale de la matrice gramme à chaque itération.
Quoi qu'il en soit, à partir du chapitre 2 de Sparse Modeling, nous pouvons voir que la cohérence mutuelle de la matrice système redondante $ \ mathbf {A} $ $ \ mu (\ mathbf {A}) $ (valeur absolue maximale des composantes hors diagonale de la matrice de gramme). Si vous connaissez la valeur de (value) et trouvez une solution $ \ mathbf {x} $ dont la norme $ L_0 $ est inférieure à un certain seuil obtenu à partir de cette valeur, vous pouvez dire que c'est une solution unique, alors faites de votre mieux. Résolvons le problème $ P_0 $.