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

Méthode de relaxation convexe

Vue d'ensemble de la méthode de la cupidité

Initialisation

Comme $ k = 0 $

Boucle principale

Effectuez les étapes suivantes comme $ k \ leftarrow k + 1 $.

  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.
  2. 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é

Présentation de IRLS

Initialisation

Comme $ k = 0 $

Boucle principale

Effectuez les étapes suivantes comme $ k \ leftarrow k + 1 $.

  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) $

indice

résultat

Erreur moyenne $ L_ {2} $ l2_err.png

Distance moyenne entre les supports dist_S.png

X_1.png X_3.png X_5.png

Considération

Recommended Posts

Modélisation éparse: Chapitre 3 Algorithme de suivi
Modélisation parcimonieuse: Chapitre 5 De la solution exacte à la solution approximative
<Course> Machine learning Chapitre 6: Algorithme 2 (k-means)
Modélisation parcimonieuse: 2.3 Construction de la matrice Glasman