[PYTHON] Essayez de décomposer la matrice daimyo par valeur singulière

introduction

L'algèbre linéaire a une opération appelée décomposition de singularité. C'est un processus qui décompose une matrice en valeurs singulières et une matrice qui les crée. Cette décomposition est un processus réversible, mais la matrice originale peut être approchée en ne prenant que la grande singularité et en ignorant la petite singularité. Ces dernières années, la compression d'informations utilisant cette propriété a été activement utilisée dans divers endroits. Dans mon environnement immédiat, la décomposition de singularité joue un rôle central dans l'approximation des états quantiques avec des réseaux tensoriels.

Le but de cet article est d'essayer le type de traitement de la décomposition de valeurs singulières en utilisant en fait une matrice simple, et de réaliser que "je vois, c'est une compression d'information".

Le code est ci-dessous.

https://github.com/kaityo256/daimyo_svd

Si vous souhaitez ouvrir Jupyter Notebook dans Google Colab, cliquez ici (https://colab.research.google.com/github/kaityo256/daimyo_svd/blob/main/daimyo_svd.ipynb).

Essayez de décomposer des valeurs singulières

Tout d'abord, confirmons que l'information peut être compressée par décomposition en valeurs singulières. Ci-dessous, il est supposé être exécuté dans Google Colab. Si vous souhaitez l'exécuter dans un autre environnement, veuillez lire ce qui convient, par exemple comment spécifier le chemin d'accès à la police.

Préparation de la matrice cible

Tout d'abord, importons ce dont vous avez besoin.

from PIL import Image, ImageDraw, ImageFont
import numpy as np
from scipy import linalg

Ensuite, installez la police japonaise.

!apt-get -y install fonts-ipafont-gothic

Après une installation réussie, créons un objet police de ʻImageFont`.

fpath='/usr/share/fonts/opentype/ipafont-gothic/ipagp.ttf'
fontsize = 50
font = ImageFont.truetype(fpath, fontsize)

Écrivez «Daimyo Procession» en noir sur fond blanc.

LX = 200
LY = fontsize
img  = Image.new('L', (LX,LY),color=255)
draw = ImageDraw.Draw(img)
draw.text((0,0), "Procession Daimyo", fill=0, font=font)
img

Ce fut un succès que la "procession Daimyo" se soit déroulée ainsi.

Maintenant, recevons la matrice sous la forme d'un tableau NumPy à partir de l'image dessinée. Mangez simplement ʻimg.getdata () sur np.array, mais cela donnerait un tableau unidimensionnel, alors utilisez reshape` pour créer une matrice.

data = np.array(img.getdata()).reshape((LY,LX))

Ces «données» sont la matrice d'origine. L'élément de matrice a une valeur de 0 à 255 et représente la luminosité du pixel.

A l'inverse, affichons la matrice sous forme d'image.

Image.fromarray(np.uint8(data))

Si l'écran suivant s'affiche, cela signifie qu'il a réussi.

Vérifions également le rang de cette matrice ici. Vous pouvez le vérifier avec np.linalg.matrix_rank.

np.linalg.matrix_rank(data) # => 47

Le rang maximum de la matrice est min (ligne, colonne). Puisque «data» est une matrice de 50 par 200, le rang maximum est de 50, mais en raison des marges au-dessus et en dessous de la «matrice de daimyo», le rang tombe un peu à 47. Approximons cela avec une matrice de rang inférieur, qui est la compression par décomposition en valeurs singulières.

Décomposition et compression de singularité

Décomposons maintenant la matrice «data» en valeurs singulières. C'est un coup avec scipy.linalg.svd.

u, s, v = linalg.svd(data)

Vérifions également chaque forme.

print(f"u: {u.shape}")
print(f"s: {s.shape}")
print(f"v: {v.shape}")

Le résultat ressemble à ceci.

u: (50, 50)
s: (50,)
v: (200, 200)

«U» est une matrice carrée 50x50 et «v» est une matrice carrée 200x200. Notez que «s» est mathématiquement une matrice diagonale de 50 x 200, mais «scipy.linalg.svd» renvoie un tableau unidimensionnel car il n'a de toute façon que des composantes diagonales. Ce «s» est une valeur singulière, tous sont des nombres réels non négatifs, et «scipy.linalg.svd» est arrangé par ordre décroissant. «U» et «v» sont également disposés dans l'ordre correspondant à la valeur singulière.

Maintenant que nous avons une décomposition de singularité, faisons une approximation de bas rang de la matrice originale. Nous ne laisserons que r valeurs singulières des plus grandes. En conséquence, ʻur, qui prend les vecteurs de colonne r à gauche de ʻu, Soit «vr» une matrice qui prend les vecteurs de ligne «r» du haut de «v». Les colonnes sont respectivement de 50 lignes et r colonnes et r lignes et 200 colonnes. Pour les valeurs singulières, utilisez une matrice diagonale de r lignes et r colonnes. Puisqu'il s'agit d'un nombre réel non négatif, il peut prendre une racine carrée. Soit «sr», «notre @ sr» «A» et «sr @ vr» «B».

Le code suivant implémente l'opération ci-dessus telle quelle. Ici, r = 10 est défini.

r = 10
ur = u[:, :r]
sr = np.diag(np.sqrt(s[:r]))
vr = v[:r, :]
A = ur @ sr
B = sr @ vr

Puisque A est une matrice avec 50 lignes et r colonnes et B est une matrice avec r lignes et 200 colonnes, le produit est le même que la matrice d'origine «data», qui est de 50 lignes et 200 colonnes.

print(f"A: {A.shape}")
print(f"B: {B.shape}")
print(f"AB: {(A @ B).shape}")

Résultat de l'exécution ↓

A: (50, 10)
B: (10, 200)
AB: (50, 200)

Cependant, alors que le rang de «data» était 47, «A @ B» ne laisse que 10 valeurs singulières, c'est donc une matrice de rang 10.

np.linalg.matrix_rank(A @ B) # => 10

Le rang est certainement de 10. C'est pourquoi on l'appelle une approximation de bas rang.

Maintenant, la matrice «data» a été approximée par deux matrices, «A» et «B». Voyons combien les données ont été compressées. Le nombre d'éléments dans la matrice peut être obtenu avec "size".

print((A.size + B.size)/data.size) # => 0.25

Si vous laissez 10 valeurs singulières, vous savez que les données ont été compressées à 25%.

Restauration de données

Maintenant, revoyons l'image pour voir combien d'informations ont été perdues à cause de l'approximation de rang bas. Restaurons les données approximées par ʻA @ Bsur l'image. Cependant, les données de pixels avaient à l'origine une valeur de 0 à 255, mais elles sont poussées de 0 à 255 parnumpy.clip` car elles débordent en raison de l'approximation et l'image devient étrange.

b = np.asarray(A @ B)
b = np.clip(b, 0, 255)
Image.fromarray(np.uint8(b))

Il a été restauré comme ça.

Et si nous faisons une approximation de rang inférieur? Définissons r = 3.

r = 3
ur = u[:, :r]
sr = np.diag(np.sqrt(s[:r]))
vr = v[:r, :]
A = ur @ sr
B = sr @ vr
b = np.asarray(A @ B)
b = np.clip(b, 0, 255)
Image.fromarray(np.uint8(b))

Le résultat ressemble à ceci.

Je ne suis pas doué pour les lignes diagonales.

Résumé

Afin de confirmer comment la décomposition de valeurs singulières est utilisée pour la compression d'informations, pensez à l'image écrite comme "Daimyo Matrix" comme une matrice, une décomposition en valeurs singulières, créez une matrice approximative de bas rang et un taux de compression de l'information. J'ai vérifié et essayé de restaurer les données. J'espère que vous essaierez ce code et que vous penserez: "Je vois, c'est une approximation de mauvaise qualité."

Matériel complémentaire

Je voudrais compléter les aspects mathématiques des opérations ci-dessus.

Qu'est-ce qu'une valeur singulière?

Considérons la décomposition suivante de la matrice carrée $ A $.

Cependant, $ P $ est une matrice régulière et $ D $ est une matrice diagonale. Quand une telle décomposition est possible, $ A $ est dit diagonal, $ D $ est un élément diagonal avec les valeurs propres de $ A $ arrangées, et $ P $ est le vecteur propre de $ A $ comme vecteur de colonne. Il sera disposé côte à côte.

J'ai également écrit que les valeurs propres et les vecteurs propres d'une matrice sont importants dans Why Learn Linear Algebra. La nature de la matrice est déterminée par les valeurs propres et les vecteurs propres. Et les vecteurs propres sont responsables des propriétés de la matrice d'origine dans l'ordre décroissant de la valeur absolue des valeurs propres. Par exemple, un vecteur propre avec la plus grande valeur propre absolue représente l'état d'équilibre si la matrice est un opérateur d'évolution temporelle, et l'état de base si la matrice représente l'hamiltonien indépendant du temps de la mécanique quantique. De plus, si la matrice est une matrice de transition de Markov, la valeur absolue de la valeur propre avec la valeur absolue maximale est 1, et la valeur propre avec la deuxième plus grande valeur propre détermine le taux de relaxation à l'état stationnaire [^ markov].

[^ markov]: Je n'ai pas pu écrire la relation entre la matrice de transition de Markov et l'algèbre linéaire depuis plusieurs années, dans l'espoir de l'écrire un jour. S'il y a une forte demande "d'écrire!", Je pourrai peut-être faire de mon mieux.

Or, les valeurs propres et les vecteurs propres d'une matrice ne peuvent être définis que dans une matrice carrée. Cependant, il y a des moments où vous voulez faire quelque chose de similaire à une matrice rectangulaire générale. La décomposition de singularité est utilisée dans de tels cas.

Considérons la matrice $ X $ dans la colonne $ m $ row $ n $ ($ m <n $). La décomposition de singularité est la décomposition de la matrice $ X $ comme suit.

Cependant, $ U $ est une matrice carrée avec m lignes et m colonnes, et $ V $ est une matrice carrée avec n lignes et n colonnes, qui sont toutes deux des matrices unitaires. $ V ^ \ dagger $ est une matrice contingente de $ V $. $ \ Sigma $ est une matrice diagonale de $ m $ lignes et $ n $ colonnes, et les éléments diagonaux sont appelés valeurs singulières $ X $. La valeur singulière est un nombre réel non négatif, et le nombre d'éléments est celui avec le moins de lignes et de colonnes de $ X $, et $ m $ si $ m <n $. Pour plus de commodité, les $ \ Sigma $ sont répertoriés par ordre décroissant de singularité à partir du haut.

Quel est le rang

Le rang (ordre) d'une matrice est "le nombre de vecteurs linéairement indépendants lorsque les vecteurs lignes sont considérés comme alignés" ou "le nombre de vecteurs linéairement indépendants lorsque les vecteurs colonnes sont considérés comme alignés". est. Les deux définitions correspondent. Dans une matrice rectangulaire avec $ m $ lignes et $ n $ colonnes ($ m <n $), il existe des vecteurs de colonne $ n $ de dimension $ m $. Puisqu'un espace de dimension $ m $ peut être créé s'il existe des vecteurs $ m $ linéairement indépendants, un vecteur colonne linéairement indépendant ne peut pas dépasser $ m $. La même chose est vraie pour $ m> n $. D'après ce qui précède, le rang de la matrice dans la colonne $ m $ row $ n $ est $ \ min (m, n) $ au maximum. Intuitivement, vous pouvez voir que plus la matrice contient des vecteurs linéairement dépendants, moins la matrice contient de "quantité d'informations essentielle".

Approximation de bas rang

Maintenant, selon la définition du produit matriciel, lorsque la matrice de $ m $ row $ r $ column et la matrice de $ r $ row $ n $ column sont multipliées, les jambes du milieu $ r $ sont écrasées et $ m $ row $ Ce sera une matrice de n $ colonnes. En prenant $ r $ plus petit à partir d'ici, la matrice de $ m $ ligne $ n $ colonne peut être approximée par la matrice de $ m $ ligne $ r $ colonne et la matrice de $ r $ ligne $ n $ colonne. Je peux.

Le rang de la matrice est déterminé par la plus petite des lignes et des colonnes. Par conséquent, si $ r <m <n $, la matrice de colonnes $ m $ row $ r $ et la colonne $ r $ row $ n $ ont un rang maximum de $ r $. La multiplication d'une matrice de rangs $ r $ n'augmente pas le rang, donc le rang de la colonne $ m $ row $ n $ de $ AB $ est également $ r $.

De cette manière, lors de l'approximation d'une matrice par le produit d'une autre petite matrice, il s'agit d'une approximation de bas rang qui se rapproche d'une matrice de rang inférieur à la matrice d'origine. Il existe différentes manières de créer une si petite matrice, mais la meilleure approximation au sens de la norme de Frobenius est l'approximation utilisant la décomposition de singularité.

Maintenant, la décomposition en valeurs singulières de la matrice $ X $ dans la colonne $ m $ row $ n $

Disons que vous obtenez. $ U $ et $ V $ sont des matrices carrées de $ m $ ligne $ m $ colonne et $ n $ ligne $ n $ colonne, respectivement, qui sont toutes deux des matrices unitaires. $ V ^ \ dagger $ est une matrice contingente de $ V $ (transloquée pour prendre un conjugué complexe). $ \ Sigma $ est une matrice diagonale de $ m $ lignes et $ n $ colonnes, avec des valeurs singulières alignées sur les éléments diagonaux. À ce stade, organisez-les par ordre décroissant à partir du haut (décidez que $ U $ et $ V $ correspondent également).

Maintenant, faisons une approximation de bas rang en utilisant seulement $ r $ de valeurs singulières. Cela utilise uniquement la partie matrice carrée de $ r $ row $ colonne $ à partir du coin supérieur gauche de $ \ Sigma $, les vecteurs de colonne $ r $ à partir de la gauche et les vecteurs de ligne $ V ^ \ dagger $ à partir du haut. C'est une forme qui se rapproche de la matrice originale de $ r $. Maintenant, puisque la valeur singulière est un nombre réel non négatif et que $ \ Sigma $ est une matrice diagonale, elle peut être séparée de $ \ Sigma = \ sqrt {\ Sigma} \ sqrt {\ Sigma} $. Combinons cela avec une matrice dérivée de $ U $ et une matrice dérivée de $ V ^ \ dagger $. Cela ressemble à ceci lorsqu'il est illustré.

De ce qui précède,

Obtenir Ainsi, la matrice de colonnes $ m $ row $ n $ $ X $ devient la matrice de colonnes $ m $ row $ r $ $ A $ et la matrice de colonnes $ r $ row $ n $ $ B $ par décomposition de singularité. J'ai pu l'approcher en tant que produit. Le rang de la matrice d'origine est jusqu'à $ \ min (m, n) $, mais le rang de la matrice ainsi approchée est jusqu'à $ r $. Les éléments originaux de la matrice $ m * n $ sont maintenant $ r * (m + n) $. Lorsque $ r $ est petit, vous pouvez voir que les informations sont compressées.