Approximation de rang faible

Soit une matrice ${\displaystyle A\in \mathbb {R} ^{m\times n}}$, et ${\displaystyle \|\cdot \|}$ une norme matricielle. Le problème d'approximation de rang ${\displaystyle k}$ peut être formulé comme le problème d'optimisation suivant:

$${\displaystyle \min _{B\in \mathbb {R} ^{m\times n},\operatorname {rang} (B)\leq k}\|A-B\|.}$$

Une manière d'imposer la contrainte de rang consiste simplement à chercher un minimiseur sous la forme ${\displaystyle B=FG}$ avec ${\displaystyle F\in \mathbb {R} ^{m\times k}}$ et ${\displaystyle G\in \mathbb {R} ^{k\times n}}$.

Pour certaines normes, la meilleure approximation est donnée directement par la troncature de la décomposition en valeurs singulières. Cela correspond à effectuer une analyse en composantes principales du nuage de points formé des colonnes de la matrice ${\displaystyle A}$.

Le résultat a été obtenu par Carl Eckart et Gale J. Young (en) pour le cas de la norme de Frobenius^[1], puis étendu au cas des normes invariantes par transformation unitaire par Leon Mirsky (en).

Dans le cas de la norme d'opérateur, l'approximation optimale est toujours donnée par la décomposition en valeurs singulières, toutefois ${\displaystyle \min _{B\in \mathbb {R} ^{m\times n},\operatorname {rang} (B)\leq r}\|A-B\|_{2}=\|A-A_{r}\|_{2}=\sigma _{r+1}}$.

De nombreux problèmes d'approximation matricielle peuvent s'écrire sous la forme

$${\displaystyle \min _{C\in \mathbb {R} ^{m\times k},D\in \mathbb {R} ^{k\times n}}D(A,FG)\quad {\text{ tel que }}\quad F\in {\mathcal {F}},G\in {\mathcal {G}},}$$

où ${\displaystyle {\mathcal {F}},{\mathcal {G}}}$ correspondent à des ensembles de contraintes qui peuvent dépendre de ${\displaystyle A}$, et ${\displaystyle D(\cdot ,\cdot )}$ est une mesure de l'éloignement de l'approximation ${\displaystyle FG}$ à la matrice ${\displaystyle A}$. Cette dernière peut par exemple être issue d'une norme, ou correspondre à une divergence statistique.

Le problème d'approximation par matrices non-négatives correspond au cas où ${\displaystyle F\geq 0,G\geq 0}$ ont des éléments non-négatifs.

Certaines approximations reposent sur la sélection des lignes et des colonnes de la matrice d'origine. C'est le cas de l'approximation CUR (également appelée « pseudo-skeleton approximation » en anglais), qui est de la forme ${\displaystyle A\approx CUR}$ où ${\displaystyle C}$ est une matrice obtenue en sélectionnant des colonnes de ${\displaystyle A}$ et ${\displaystyle R}$ obtenue en sélectionnant des lignes de ${\displaystyle A}$.

L'approximation de Nyström (également appelée « adaptive cross-approximation » en anglais) correspond au cas particulier où ${\displaystyle A}$ est une matrice semi-définie positive.

L'analyse archétypale correspond à une classe d'approximation où les colonnes de ${\displaystyle F}$ sont contraintes à être des combinaisons convexes des colonnes de ${\displaystyle A}$, et chaque colonne de ${\displaystyle G}$ est également contrainte à être une combinaison convexe^[2].

L'analyse factorielle est une technique d'analyse de données, qui consiste à expliquer des observations multivariées comme des combinaisons linéaires d'un petit nombre de facteurs. Il s'agit d'une classe de méthodes plus générale, et fondée sur un modèle statistique^[3]. De multiples techniques d'analyse factorielles sur données continues reposant sur un modèle à bruit additif peuvent toutefois s'écrire comme des problèmes d'approximation de rang faible sous contraintes. Le choix de la fonction ${\displaystyle D}$ utilisée pour mesurer l'erreur d'approximation dérive alors typiquement des hypothèses de modélisation formulée sur le bruit.

• Portail des mathématiques