14.3 Approximation pour une matrice de rang inférieur

Une image numérique en niveaux de gris peut être représentée par une matrice dont chaque élément représente un pixel. L’idée fondamentale qui sous-tend la compression d’image avec perte est l’obtention d’une représentation matricielle voisine \(\mathbf{A}\) qui requiert moins de stockage que cette dernière. Dans cette section, nous allons tenter de trouver des matrices \(\mathbf{P}\) et \(\mathbf{Q}\) pour lesquelles \(\mathbf{A} \approx \mathbf{P}\mathbf{Q},\) et telles que \(\mathbf{P}\) et \(\mathbf{Q}\) prennent le moins de stockage possible.

Nous devons répondre à deux questions :

1. Qu’entend-on par une matrice voisine d’une autre?

2. Comment obtient-on les matrices \(\mathbf{P}\) et \(\mathbf{Q}\)?

14.3.1 La norme de Frobenius

Pour mesurer la « distance » entre deux matrices, nous utilisons la norme de Frobenius d’une matrice.

Soit \(\mathbf{A} \in \mathbb{R}^{m \times n}\). La norme de Frobenius de \(\mathbf{A}\), dénotée par \(\|\mathbf{A}\|_F\), est la quantité \[\sqrt{ \sum_{i = 1}^m \sum_{j = 1}^n a_{i,j}^2}.\]

Si \(\mathbf{B} \in \mathbb{R}^{m\times n}\), alors la distance entre \(\mathbf{A}\) et \(\mathbf{B}\) dénotée par \(d(\mathbf{A},\mathbf{B})\), est la quantité \[\|\mathbf{A} - \mathbf{B}\|_F.\]

Plus la valeur de \(d(\mathbf{A},\mathbf{B})\) est petite, plus les matrices \(\mathbf{A}\) et \(\mathbf{B}\) sont voisines. Notons que \(d(\mathbf{A},\mathbf{B}) = d(\mathbf{B},\mathbf{A})\).

Exemple 14.1 Si \(\mathbf{A} = \begin{bmatrix} 1 & 0 \\ 0 & 1\end{bmatrix}\) et \(\mathbf{B} = \begin{bmatrix} 1 & -1 \\ 2 & 0\end{bmatrix}\), alors \[d(A,B) = \|A-B\|_F = \left\|\begin{bmatrix} 0 & 1 \\ -2 & 1\end{bmatrix}\right \|_F = \sqrt{ 0^2 + 1^2 + (-2)^2 + 1^2 } = \sqrt{6}.\]

14.3.2 Application à la compression d’images avec pertes

Pour la compression d’images, nous devons trouver de bonnes approximations qui requièrent moins de stockage. Une matrice de rang inférieur peut s’avérer être très utiles dans ce cas.

Supposons que \(\mathbf{B}\) soit une matrice de rang \(r\). Rappelons que l’on peut obtenir, par réduction de matrices, une matrice inversible \(\mathbf{M} \in \mathbb{R}^{m\times m}\) et une matrice \(\mathbf{R}\) sous forme échelonnée réduite telles que \(\mathbf{B} = \mathbf{M}\mathbf{R}\).

Puisque \(\mathbf{B}\) est de rang \(r\), les \(m-r\) dernières lignes de \(\mathbf{R}\) ne contiennent que des nuls. Donc, si \(\mathbf{P}\) correspond aux les premières \(r\) colonnes de \(\mathbf{M}\) et si \(\mathbf{Q}\) correspond aux premières \(r\) lignes de \(\mathbf{R}\), alors \(\mathbf{P}\mathbf{Q} = \mathbf{M}\mathbf{R} = \mathbf{B}\). Conséquemment, si \(r\) est beaucoup plus petit que \(\min(m, n)\), l’espace requis afin de stocker \(\mathbf{P}\) et \(\mathbf{Q}\) peut être substantiellement moindre que l’espace requis afin de stocker \(\mathbf{B}\).

En résumé, une façon d’utiliser la compression d’images avec perte, pour des bitmaps en noir et blanc, est de trouver une matrice de faible rang dont la distance à la matrice de l’image originale est petite. Nous utilisons la décomposition en valeurs singulières pour obtenir une telle matrice.

Soit \(\mathbf{A} \in \mathbb{R}^{m\times n}\). Soit \(r\) un entier positif plus petit que le minimum de \(m\) et \(n\). Considérons un décomposition en valeurs singulières de \(\mathbf{A}\) obtenue par \(\mathbf{U} \mathbf{\Sigma} \mathbf{V}^\mathsf{T}\) telle que \(\sigma_1 \geq \sigma_2 \geq \ldots\) où \(\sigma_i\) dénote l’élément \((i,i)\) de \(\mathbf{\Sigma}.\)

Soient \(\mathbf{U}_r\) et \(\mathbf{V}_r\) les matrices obtenues des \(r\) premières colonnes de \(\mathbf{U}\) et \(\mathbf{V}\), respectivement. Soit \(\mathbf{\Sigma}_r \in \mathbb{R}^{r\times r}\) une matrice diagonale telle que le \(i\)-ième élément de la diagonale est donné par l’élément \((i,j)\) de \(\mathbf{\Sigma}\) pour \(i = 1,\ldots r\).

Le théorème de Eckart-Young dit que la matrice \(\mathbf{M} = \mathbf{U}_r \mathbf{\Sigma}_r \mathbf{V}_r^\mathsf{T}\) est une matrice de rang \(r\) qui minimise \(\|\mathbf{A}-\mathbf{M}\|_F\). Autrement dit, toutes les autres matrices de taille \(m \times n\) de rang \(r\) sont aux moins aussi éloignées de \(\mathbf{A}\) que \(\mathbf{M}\) l’est. Bien entendu, la distance est donnée par la norme de Frobenius. La preuve de ce résultat est trop sophistiquée pour le présent ouvrage et ne sera pas présentée. (Pour la matrice \(\mathbf{A}\) à l’exemple ci-dessus, \(u_1 \sigma_1 v_1^\mathsf{T}= \begin{bmatrix} \frac{1}{2} & 1 & \frac{1}{2} \\ \frac{1}{2} & 1 & \frac{1}{2}\end{bmatrix}\) est de rang \(1\) et est voisine de \(\begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1\end{bmatrix}\). Quelle est la distance entre les deux matrices?)