Valeur singulière

Bonjour
La question suivante vient d'un sujet à la frontière de plusieurs disciplines (analyse matricielle et probabilité). Je le poste dans cette section car je pense que c'est surtout une question d'analyse matricielle plus précisément de décomposition en valeur singulière notée SVD. Et je précise que je suis persuadé que la question n'est pas dure.

Soit $X = B + E \in M_{d,n}$ avec $E$ une matrice dont les coefficients sont des variables aléatoires et $B$ une matrice de rang $d$.
Notons utilisons la décomposition en valeurs singulières de $X$ et $B$, on a $X = \sum_{i=1}^{\hat{r}} \hat{\sigma}_{k} \hat{u}_{k} \hat{v}_{k}^{T}$ et $B = \sum_{i=1}^{r} \sigma_{k} u_{k} v_{k}^{T}$
Soit $\lambda \ge 0$ fixé notons $\hat{d} = \max\{ k \mid \hat{\sigma}_{k} \ge \lambda \}$
On a la convention $\sigma_{1}(A) \ge \cdots \ge \sigma_{r}(A)$.

Je lis $\mathbb{P}(\hat{d} \ne d) = \mathbb{P}(\hat{\sigma}_{d+1} \ge \lambda \text{ ou } \hat{\sigma}_{d} < \lambda ) \le \mathbb{P}(|E|_{op} \ge \lambda \wedge \sigma_{d} - \lambda) $

J'aimerais comprendre l'inégalité pour moi le reste est ok !

Alors qu'est ce que j'ai fait ? Déjà le $\text{or}$ m'embête alors je passe au complémentaire. Supposons que $|E|_{op} < \lambda \wedge \sigma_{d} - \lambda$ (EDIT) et montrons que $\hat{d} = d$ c'est à dire que $\hat{\sigma}_{d+1} < \lambda \text{ et } \hat{\sigma}_{d} \ge \lambda$
Une conclusion est directe par l'inégalité de Weyl
$$
|\hat{\sigma}_{d} - \sigma_{d}| \le |E|_{op} \le \sigma_{d} - \lambda
$$
D'où $ \hat{\sigma}_{d} \ge \lambda$

Par contre je ne vois pas quoi dire sur $\hat{\sigma}_{d+1}$, il faudrait surêment utiliser le fait que le rang de $B$ est $d$ ce qui veut dire que $\sigma_{d+1}= 0$ mais de toute façon l'inégalité de Weyl ne marche pas dans ce cas car $X$ est une matrice $d\times n$.

Réponses

  • Bonjour, il y a d'abord une inégalité stricte quand tu passes au complémentaire, un résultat que j'ai vu très récemment ici dit que avec $X-B=E$ pour les matrices (complexes) avec $B$ de rang $d$, $E$ ayant les valeurs singulières $\gamma_i$ et $X$ les v.singulières ${\hat{\sigma}_i}$
    alors $\gamma_i\ge {\hat{\sigma}_{d+i}}$, j'ai dit que je n'ai pas
    vue une preuve mais ça semble très lié à ton problème voici le lien.
    http://www.les-mathematiques.net/phorum/read.php?3,2002558
  • Bonjour,

    Merci et bien il faudrait essayer de montrer que $\sigma_{d+1}(A) \le \sigma_{1}(A+B)$ avec $\text{rg}(B) = d$. Où l'on note $\sigma_{1}(A) \ge ... \ge \sigma_{r}(A)$ les valeurs singulière d'une matrice $A $.
  • C'est bon.
  • Bonjour,

    Autre question. Voici une citation :
    Citation a écrit:
    Dans un autre registre, il est pertinent d’évoquer la méthode des moindres carrés dans cette leçon, par exemple en faisant ressortir la condition de rang maximal pour garantir l’unicité de la solution et s’orienter vers les techniques de décomposition en valeurs singulières pour le cas général. On peut alors naturellement analyser l’approximation d’une matrice par une suite de matrices de faible rang.

    Que signifie l’approximation d’une matrice par une suite de matrices de faible rang ? Grâce à la DVS je connais la meilleurs approximation par une matrice de rang $r$ d'une matrice donnée pour la norme de Frobenius. Mais de quelle suite ici parle t on ?
  • Bonjour, en fait après le post j'ai vu une référence mais en anglais, 'Low rank approximation matrices'. (Des trucs non trivials).
    Tu trouveras peut être les inégalités cherchées sans qu'on s'enfonce peut être
    Cordialement.


    C'était ce pdf
  • Merci Tonm,

    J'en profite pour poser une nouvelle question sur le sujet pour ceux que ça intéresse, comment peut-on implémenter une calcul de SVD en pratique ? J'ai l'impression que le recours au calcul des valeurs propres est très coûteux.
  • Plusieurs méthodes, ça dépend si la matrice est grande ou pas, si elle est sparse ou pas (qui impacte le coût d'une multiplication), du niveau de précision souhaité, même potentiellement du hardware (algorithme très parallélisé ou pas), etc.

    Il y a des algorithmes basé sur la méthode de Householder/décomposition QR, ou encore sur les puissances itérées/Lanczos par exemple.

    Mais vu les futurs métiers auxquels tu te destines potentiellement, je pense que tu devrais prendre le réflexe de faire des recherches Google. C'est plus rapide que le forum, et les réponses seront plus précises et plus étendues sur ce genre de questions, et donc plus enrichissantes 8-) (je dis pas que le forum n'est pas bien !)

    De manière générale, le calcul des valeurs propres est effectivement coûteux (du même genre que l'inversion, $O(n^3)$), mais pas au point d'être rédhibitoire.
Connectez-vous ou Inscrivez-vous pour répondre.