BD 7

Une image est un ensemble de pixels, par exemple 780 environ dans la base de données MNIST, et jusqu'à des millions pour des images de grande précision.

Supposons n images, vues comme une matrice (n,d) où d est la dimension de chaque image.

Une approche classique est de compresser l'image en .gif et .jpeg par exemple. Une autre approche est de réduire la dimension.

Problème général: on a n points v de dimension d. On souhaite remplacer ces points par des points v' de dimension k plus faible, sans trop d'erreurs.
- Johnson-Lindenstrauss: si k > 4 eps² .log n alors la distortion est au plus eps avec une projection aléatoire.
- Une projection aléatoire est une matrice (d,k) où chaque valeur est tirée selon N(0,1)
- On peut aussi choisir k=log n/ eps² et tirer selon N(0,1/k)
PCA: Analyse en composantes principales.
- on choisit les vecteurs propres correspondant aux plus grandes valeurs propres de la matrice de covariance A(i,j)
- on obtient une matrice A' avec moins de colonnes
- on reconstruit approximativement la matrice d'origine
  - http://mdr.free.fr/td/reconstruct.py

https://up2.fr/contents/td/Ad.pdf

Gram's decomposition
- on peut toujours trouver des vecteurs v_i pour i=1...n tels que v_i. v_j= A(i,j)
- Problème: trouver des vecteurs de petite dimension tels que v_i. v_j= A(i,j)
- Word2vec

http://nlp.polytechnique.fr/word2vec#french

Exercice:
- Matrice A=

                [0.1,2,2.0,1,2]
                [0.2,3,3.0,1,1]
                [0.1,4,4.1,1,2]

Réduire à 2 lignes et 2 colonnes. Instruction Python:

A = np.array([ [0.1,2,2.0,1,2],[0.2,3,3.0,1,1],[0.1,4,4.1,1,2] ])

UP2