[PYTHON] Approximation de bas rang des images par HOSVD et HOOI

introduction

La décomposition d'un tenseur en un ensemble de tenseurs de bas rang (tenseurs de noyau) et de matrices est appelée décomposition de Tucker. Parmi les méthodes, HOSVD (décomposition en valeur singulière d'ordre supérieur) et HOOI (itération orthogonale supérieure des tenseurs) sont utilisées pour effectuer une approximation de bas rang de l'image.

Le code source est https://github.com/kaityo256/hooi_sample À.

Décomposition de Tucker du tenseur

Par exemple, supposons que vous ayez un tenseur du troisième ordre $ X $ et que les dimensions de chaque pied soient $ R_1, R_2, R_3 $. A ce moment, le tenseur du troisième ordre $ \ chi $ dont les dimensions du pied sont $ r_1, r_2, r_3 $ et la matrice $ A_i (i = 1,2,3) $ dans la colonne $ r_i $ ligne $ R_i $. Démontez en. Cette matrice $ A_i $ change sa dimension de $ r_i $ à $ R_i $ lorsqu'elle est réduite à la $ i $ ème jambe du tenseur du noyau, c'est-à-dire que $ A_i $ retourne du tenseur du noyau au tenseur d'origine. Cela devient une procession. Inversement, si vous prenez la $ i $ ème jambe du tenseur d'origine et la contraction de $ A_i ^ \ dagger $, la dimension de la jambe passe de $ R_i $ à $ r_i $, c'est-à-dire que $ A_i ^ \ dagger $ est projetée. C'est une procession. Cela ressemble à ceci lorsque chacun est illustré.

Premièrement, le tenseur du noyau $ \ chi $ est obtenu en multipliant chaque jambe du tenseur original $ X $ par une matrice de projection.

De plus, le résultat de la multiplication de chaque jambe du tenseur du noyau $ \ chi $ par la matrice de restauration est le tenseur $ X '$, qui est une approximation du tenseur d'origine.

À l'origine, la quantité d'informations dans le tenseur était de $ R_0 R_1 R_2 $, mais comme le nombre d'éléments dans le tenseur de noyau est $ r_0 r_1 r_2 $ et le nombre d'éléments dans la matrice $ A_i $ est $ R_i r_i $, le nombre d'éléments après compression est Il devient $ r_0 r_1 r_2 + R_0 r_0 + R_1 r_1 + R_2 r_2 $.

La décomposition de Tucker est le problème de trouver l'ensemble $ A_i $ de la matrice de projection qui se rapproche le plus fidèlement possible du tenseur d'origine étant donné les dimensions du tenseur d'origine $ X $ et du tenseur du noyau. Faisons cela avec deux méthodes, HOSVD et HOOI, basées sur l'approximation de bas rang de l'image.

HOSVD

Dans HOSVD (décomposition de valeur singulière d'ordre supérieur), le tenseur à plusieurs jambes est d'abord divisé en deux jambes, l'une à laquelle prêter attention et l'autre à. Puis, puisqu'il s'agit d'une matrice, SVD (décomposition en valeurs singulières) peut être appliquée. Après SVD, celle qui a pris le rang supérieur de la matrice de droite est la matrice de restauration du pied d'intérêt. HOSVD est une procédure qui se répète pour toutes les jambes.

Dans la figure ci-dessus, concentrez-vous sur la première branche du tenseur à trois pattes $ X $, et SVD les deuxième et troisième pattes ensemble comme une matrice de $ R_2 R_3 \ fois R_1 $. .. Ensuite, une matrice carrée de $ R_2 R_3 \ times R_2 R_3 $ apparaît sur le côté gauche et $ R_1 \ times R_1 $ apparaît sur le côté droit, mais celle qui prend la ligne supérieure $ r_1 $ sur le côté droit est la matrice de restauration $ A_1 $ de la première étape. Devenir. De même, $ A_2 $ et $ A_3 $ peuvent être obtenus.

HOOI

Or, on sait que HOSVD ne donne pas la meilleure approximation. HOOI (itération orthogonale supérieure des tenseurs) améliore cela par itération.

Tout d'abord, préparez la matrice de restauration $ A_i $ au hasard dans un premier temps. Ensuite, sauf pour le pied d'intérêt (par exemple, n ° 1), écrasez le pied du tenseur d'origine en utilisant $ A_i (i \ neq 1) $. Ensuite, comme HOSVD, faites une matrice des jambes d'intérêt et des autres jambes, multipliez par SVD, et prenez le $ r_1 $ supérieur de la matrice résultante pour faire un nouveau $ A_1 $.

Notez que la quantité de calcul requise pour SVD a considérablement diminué parce que les dimensions ont été supprimées à l'aide de la matrice de projection, à l'exception du pied d'intérêt.

Ceci est exécuté pour toutes les jambes comme une boucle, et la précision est améliorée en tournant cette boucle.

Approximation de bas rang de l'image

Une image bidimensionnelle peut être considérée comme un tenseur du troisième ordre avec des dimensions (hauteur, largeur, 3) car la valeur du pixel est déterminée en spécifiant la coordonnée x, la coordonnée y et la couleur (RVB). Parmi ceux-ci, trouvez la matrice qui écrase la hauteur et la largeur par HOSVD et HOOI, et essayez d'approcher l'image par un faible rang. Pour HOSVD, voir Articles précédents.

Pour une image d'une largeur de $ w $ et d'une hauteur de $ h $, pensez à écraser la dimension de largeur à $ r1 $ et la dimension de hauteur à $ r2 $. Ce que nous voulons trouver, c'est une matrice de projection qui écrase la largeur et la hauteur. Soit ceci $ a_1 ^ \ dagger, a_2 ^ \ dagger $. Quant à la couleur, il n'y a que 3 dimensions, donc je ne vais pas l'écraser.

Tout d'abord, il est nécessaire de préparer les valeurs initiales de $ a_1 et a_2 $. La valeur initiale peut être n'importe quoi [^ 1], mais chaque ligne doit être orthogonale. Je ne pouvais pas penser à un bon moyen de le donner, alors j'ai préparé une matrice aléatoire de $ w \ fois w $ et $ h \ fois h $, SVD, et j'ai récupéré les premières lignes $ r_1, r_2 $. Je l'ai essayé comme valeur.

[^ 1]: Dans le but d'améliorer l'approximation de HOSVD, il est efficace d'utiliser le résultat de HOSVD comme valeur initiale. Cependant, si vous souhaitez abaisser l'ordre de calcul par rapport à HOSVD, vous pouvez préparer la valeur initiale de manière aléatoire. Dans tous les cas, vous pouvez obtenir une précision suffisante en répétant plusieurs fois.

    X1 = np.random.rand(w,w)
    X2 = np.random.rand(h,h)
    U,s,A1 = linalg.svd(X1)
    U,s,A2 = linalg.svd(X2)
    a1 = A1[:r1, :]
    a2 = A2[:r2, :]

Pour votre commodité plus tard, préparons une fonction qui donne un tenseur compressé et restauré en utilisant $ a_1 et a_2 $.

def restored_tensor(X,a1,a2):
    pa1 = a1.T.dot(a1)
    pa2 = a2.T.dot(a2)
    X2 = np.tensordot(X,pa1,(1,0))
    X3 = np.tensordot(X2,pa2,(0,0))
    return X3.transpose(2,1,0)

C'est une fonction qui multiplie $ X $ par $ a_i ^ \ dagger $ pour créer un noyau tenseur, puis multiplie $ a_i $ pour renvoyer le tenseur restauré.

Après ça

1. Écrasez la jambe de hauteur (n ° 2) avec $ a_2 ^ \ dagger $, puis SVD avec la couleur, et mettez à jour la matrice d'écrasement de largeur $ a_1 ^ \ dagger $
2. Écrasez la jambe de largeur (n ° 1) avec $ a_1 ^ \ dagger $, puis SVD avec la couleur, et mettez à jour la matrice d'écrasement de hauteur $ a_2 ^ \ dagger $

Doit être répété. Le code suivant l'implémente.

    for i in range(10):
    	X1 = np.tensordot(X,a2.T,(0,0)).transpose(2,1,0).reshape(r2*3,w)
    	U,s,A1 = linalg.svd(X1)
    	a1 = A1[:r1, :]
    	X2 = np.tensordot(X,a1.T,(1,0)).transpose(2,1,0).reshape(r1*3,h)
    	U,s,A2 = linalg.svd(X2)
    	a2 = A2[:r2, :]

résultat

Pour le tenseur original $ X $, étant donné son tenseur approximatif $ X '$, le résidu $ r $

Défini dans. pourtant|X|EstXFrobenius Norm.

Considérez une conversion qui prend une image appropriée comme entrée et compresse chacune des dimensions de largeur et de hauteur à 20%. Comme image d'entrée, j'utilise une image du cheval spirituel Itanium2 que j'avais sous la main.

L'image suivante en est une approximation avec HOSVD.

Le résidu était de 0,966415890942.

Si vous tournez HOOI 10 étapes, le résidu diminuera comme suit.

1.28857987024
0.97532217632
0.95714093422
0.952636586271
0.950770629606
0.949809071863
0.949257702502
0.948920613334
0.948705104294
0.948562468306

La première ligne est la valeur sans aucune optimisation. Si vous tournez la boucle deux fois à partir de là, le résidu sera plus petit que HOSVD. L'image après avoir tourné 10 fois est la suivante.

Le résidu dans cette image est de 0,948562468306, un peu moins de 2% d'amélioration par rapport à HOSVD, mais il est difficile (du moins pour moi) de distinguer visuellement la différence.

Résumé

Pensant que l'image est un tenseur au 3ème étage, j'ai essayé une approximation de bas rang en utilisant deux méthodes, HOSVD et HOOI. Pour une image d'une taille de $ (w, h) $, si vous écrasez la largeur à $ r_1 $ et la hauteur à $ r_2 $, HOSVD en a deux, $ (3h, w) $ et $ (3w, h) $. Vous devez SVD la matrice une fois, mais HOOI doit boucler plusieurs fois au lieu de SVDing une matrice assez petite avec $ (3r_2, w) $ et $ (3r_1, w) $. .. Cependant, dans la plage testée avec l'image, le résidu est devenu plus petit que celui de HOSVD après l'avoir tourné plusieurs fois, donc si la dimension du tenseur d'origine est grande, la quantité totale de calcul semble être plus petite dans HOOI.