Modélisation éparse: Chapitre 3 Algorithme de suivi
Modélisation éparse Chapitre 3 Implémentation de l'algorithme de suivi en Python.
Cahier Jupyter résumant le code et les résultats expérimentaux.
Implémentation de la méthode gloutonne et de la méthode de relaxation convexe suivantes. IRLS est un peu suspect ...
Méthode gourmande
- Poursuite de correspondance orthogonale (OMP)
- Poursuite assortie (MP)
- Poursuite de correspondance faible (WMP)
- Algorithme de seuil
Méthode de relaxation convexe
- Carrés de location itératifs repondérés (IRLS)
Vue d'ensemble de la méthode de la cupidité
Initialisation
Comme $ k = 0 $
- Solution initiale $ \ mathbf {x} ^ {0} = \ mathbf {0} $
- Résidu initial $ \ mathbf {r} ^ {0} = \ mathbf {b} $
- Prise en charge initiale de la solution $ S ^ {0} = \ emptyset $
Boucle principale
Effectuez les étapes suivantes comme $ k \ leftarrow k + 1 $.
- Calcul des erreurs, mise à jour du support: Colonne $ \ mathbf {a} _ {j} $ qui peut réduire le plus résiduel $ \ mathbf {r} ^ {k} $ de $ \ mathbf {A} $ À $ S ^ k $
1.Mise à jour provisoire du monde:
\\| \mathbf{Ax}-\mathbf{b}\\|^{2}_{2} \, \rm{subject} \, \rm{to} \, \rm{Support}\\{\mathbf{x}\\}=S^{k} Solution optimale de\mathbf{x}^{k} Laisser. - Mise à jour résiduelle: Calculez $ \ mathbf {r} ^ {k} = \ mathbf {b} - \ mathbf {Ax} ^ {k}
. 1.Condition d'arrêt: Si \|\mathbf{r}^{k}\|<\epsilon_{0}$Si c'est le cas, il se termine, sinon il se répète.
Dans le calcul des erreurs et la mise à jour du support, le produit interne de toutes les colonnes $ \ mathbf {a} _ {j} $ de $ \ mathbf {A} $ et le résiduel $ \ mathbf {r} $ est calculé, et la valeur absolue du produit interne est calculée. Ajoutez la colonne qui maximise au support. En d'autres termes, les colonnes parallèles à $ \ mathbf {r} $ sont ajoutées dans l'ordre.
Différences dans l'algorithme de cupidité
- OMP
- Restez au top
- MP
- Solution provisoire mise à jour uniquement avec $ \ mathbf {a} _j $ nouvellement ajouté au lieu de $ \ mathbf {A} $
- WMP
- Ajouter le scalaire $ t , (0 <t <1) $ aux hyperparamètres
*Avec des calculs d'erreurs et des mises à jour de support
\mathbf{r}^{k-1} La valeur absolue du produit intérieur avect\\|\mathbf{r}^{k-1}\\| Plus que\mathbf{a}_j Si est trouvé, le calcul est arrêté. Le reste est le même que MP. - Algorithme de seuil
- Ajout du nombre $ k $ de fonctions de base incluses dans la prise en charge des hyperparamètres
- $ k $ du haut de $ \ mathbf {a} _j $, qui a une grande valeur absolue du produit interne avec $ \ mathbf {b} $, est pris en charge. Après cela, résolvez le problème des moindres carrés et définissez-le comme $ \ mathbf {x} $.
Présentation de IRLS
- Résolvez le problème $ \ left (P_ {1} \ right) $ au lieu du problème $ \ left (P_ {0} \ right) $.
- Résolvez le problème $ \ left (P_ {1} \ right) $ en approchant la norme $ L_ {1} $ avec la norme $ L_ {2} $ pondérée.
- Il doit être répété beaucoup pour obtenir une solution clairsemée.
Initialisation
Comme $ k = 0 $
- Solution initiale approximative $ \ mathbf {x} ^ {0} = \ mathbf {1} $ (tous les 1 vecteurs)
- Matrice de poids initial $ \ mathbf {X} ^ {0} = \ mathbf {I} $
Boucle principale
Effectuez les étapes suivantes comme $ k \ leftarrow k + 1 $.
- Méthode du carré minimum: équations linéaires simultanées
$ \ mathbf {x} \ _ {k} = \ mathbf {X} \ _ {k-1} ^ {2} \ mathbf {A} ^ {T} (\ mathbf {A} \ mathbf {X} _ {k-1} ^ {2} \ mathbf {A} ^ {T}) ^ {+} \ mathbf {b} $ résolus et approximés directement ou en utilisant des méthodes itératives Obtenez la solution $ \ mathbf {x} \ k. 1.Mise à jour du poids: X{k}(j,j)=|x_{k}(j)|^{0.5}En tant que matrice diagonale de poids \mathbf{X}Mise à jour 1.Condition d'arrêt: Si \|\mathbf{x}_{k}-\mathbf{x}_{k-1}\|_{2}$Si est inférieur au seuil prédéfini, il sort, sinon il se répète.
Expérience
simulation
$ \ mathbf {x} $ 50 dimensions vecteur $ \ mathbf {b} vecteur $ 30 dimensions $ \ mathbf {A} $ 30 × 50 matrice dimensionnelle, normalisation de colonne de nombres aléatoires uniformes de $ [-1, 1) $
- En supposant que le nombre d'éléments non nuls de $ \ mathbf {x} $ est $ k $, la valeur des éléments non nuls est iid à partir d'une distribution uniforme dans la plage de $ [-2, -1] \ cup [1, 2] $. Extrait.
- Simulez 200 fois chacun avec $ k = 1, ..., 10 $
indice
- $ L_2 $ norme estimée de $ \ mathbf {\ hat {x}} $ et vraie $ \ mathbf {x} $
*Estimé
\mathbf{\hat{x}} Et vrai\mathbf{x} Distance entre les supports$dist(\hat{S},S)=\frac{max\\{|\hat{S}|, |S| \\} - |\hat{S}\cap S|}{max\\{|\hat{S}|,|S|\\}} $ - Prenez la moyenne de 200 simulations.
résultat
Erreur moyenne $ L_ {2} $
- Lorsque k augmente, l'erreur augmente.
- L'erreur IRLS est petite, mais elle est naturelle car il s'agit d'une erreur $ L_ {2} $
- OMP fait également de son mieux. C'est rapide
Distance moyenne entre les supports
- Lorsque k est faible, la distance entre les supports IRLS a augmenté. Il n'y a rien de tel dans le manuel, il peut donc être insuffisant ou défectueux
- OMP fait également de son mieux.
Considération
- OMP je fais de mon mieux
- IRLS ne correspond pas aux résultats du manuel, il est donc nécessaire d'en rechercher la cause