Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
263 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Valeur singulière

Envoyé par mini_calli 
Valeur singulière
il y a onze mois
avatar
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$.



Edité 3 fois. La dernière correction date de il y a onze mois et a été effectuée par mini_calli.
Re: Valeur singulière
il y a onze mois
avatar
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.
[www.les-mathematiques.net]



Edité 1 fois. La dernière correction date de il y a onze mois et a été effectuée par AD.
Re: Valeur singulière
il y a onze mois
avatar
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 $.



Edité 1 fois. La dernière correction date de il y a onze mois et a été effectuée par mini_calli.
Re: Valeur singulière
il y a onze mois
avatar
C'est bon.
Re: Valeur singulière
le mois dernier
avatar
Bonjour,

Autre question. Voici une citation :

Citation
Citation
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 ?


Je suis l'élève vous êtes les profs. J'abandonne la quête du Callifa c'est up to no good.



Edité 1 fois. La dernière correction date de le mois dernier et a été effectuée par mini_calli.
Re: Valeur singulière
il y a sept semaines
avatar
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



Edité 1 fois. La dernière correction date de il y a sept semaines et a été effectuée par Tonm.
Pièces jointes:
ouvrir | télécharger - matrix-analysisdodatno.pdf (368.4 KB)
Re: Valeur singulière
il y a six semaines
avatar
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.


Je suis l'élève vous êtes les profs. J'abandonne la quête du Callifa c'est up to no good.



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par AD.
Re: Valeur singulière
il y a six semaines
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 eye rolling smiley (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.



Edité 3 fois. La dernière correction date de il y a six semaines et a été effectuée par Chalk.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 149 244, Messages: 1 507 384, Utilisateurs: 27 667.
Notre dernier utilisateur inscrit Setif.


Ce forum
Discussions: 19 584, Messages: 197 770.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page