Resolution inverse de matrice du type R = V.Vt

[invite45567c55]

Bonjour,

Soit V une matrice carrée (N*N) et Vt sa transposée, connaissant uniquemrent la matrice R(N*N) = V.Vt, comment retrouver ou estimer la matrice V ?

Note: V est inversible.

Merci de votre support, bien à vous.
-----

[invitec5eb4b89]

Je résume pour voir si j'ai bien compris : R est une matrice carrée réelle (? réelle ou complexe ?) qui peut s'écrire sous la forme avec V une matrice carrée réelle également.

D'après son expression, R est déjà une matrice symétrique, donc diagonalisable en base orthornormée, c'est à dire qu'il existe P orthogonale et D diagonale (réelles, carrées) telles que .

De plus, et toujours d'après son expression, R est une matrice définie positive : ses valeurs propres sont positives. On peut donc poser la matrice diagonale réelle (carrée) ayant comme coefficients diagonaux les : .

On a donc .

Et enfin : .

Concrètement : tu calcules les éléments propres de R avec l'algorithme de ton choix, et tu peux en déduire V !


V.

[invite45567c55]

Je résume pour voir si j'ai bien compris : R est une matrice carrée réelle (? réelle ou complexe ?) qui peut s'écrire sous la forme avec V une matrice carrée réelle également.

D'après son expression, R est déjà une matrice symétrique, donc diagonalisable en base orthornormée, c'est à dire qu'il existe P orthogonale et D diagonale (réelles, carrées) telles que .

De plus, et toujours d'après son expression, R est une matrice définie positive : ses valeurs propres sont positives. On peut donc poser la matrice diagonale réelle (carrée) ayant comme coefficients diagonaux les : .

On a donc .

Et enfin : .

Concrètement : tu calcules les éléments propres de R avec l'algorithme de ton choix, et tu peux en déduire V !


V.

V est une matrice réelle à coefs >= 0. L'ordre de N est 256 à 512.
Tres subtile en passant par D=D^1/2 * D^1/2. Donc R est a diagonaliser: par "element", je comprend donc valeurs/vecteurs propres. C'est ça ?
Par quel algo (rapide) je calcule ces éléments ? pouvez vous me mettre sur la piste.
Comment faire sans passer par les valeurs/vecteurs propres ?
-> Y-a til des algo iterratifs ?

Merci déjà de votre support.

[invitec5eb4b89]

Ah oui, je suis peut être allé un peu vite.
Ton problème peut également se formuler comme une décomposition de Cholesky.

Franchement je ne connais pas les algos efficaces qui permettent de faire cela (j'ai honte). Mais pour la décomposition en valeurs/vecteurs propres ou pour la décomposition de Choelsky, il y a des algos itératifs qui sont déjà codés dans je crois tous les langages possibles.

Par exemple LAPACK permet de faire ça. R aussi (reprend LAPACK). Matlab aussi etc.

[A voir en vidéo sur Futura]

[invite45567c55]

Excellent, exactement l'info que je cherche !

Algos type "puissance iterrée" ou décomposition Cholesky comme tu me l'a mentionné. je zoom ca, ainsi que tes infos "LAPACK".

Maintenant, supposons V(N*N) toujours inconnu et R = matrice d'autocorrelation [-N/2...+N/2 [ toujous connue tq pour chaque ligne(0...N-1)
R(ligne, k)=somme sur i de V(ligne, i) * V(ligne, i+k). Quelle demarche à adopter ?

PS: c'est qd meme sympa un bon forum: qq'un pose une question/PB, un autre y apporte ce qu'il peut. Une belle entraide via le Net. Je m'attache perso sur les technos de compression "rapides" via transfo. orthogonales, (norme préservée), pour l'instant Hadamard tq: W = H * R * H tenant compte ainsi de la stat du signal.

Bien à toi,
David.

[invitec5eb4b89]

J'avoue qu'en matrice d'autocorrélation, je ne m'y connais pas vraiment... Peut être que quelqu'un d'autre s'y connait mieux ?

[invite45567c55]

Salut Vincent.
Le principe V'= D^1/2 * P marche tres bien (D = Diag des valeurs Propres de R et P = vecteurs propres de R). Pour check, P * Pt est bien = Identity (orthogonalité des vect. propres) ainsi que V' * V't = R. Les algos sont nickels et performant en temps calcul. Mais...
==> Le HIC est que V' n'a rien a voir avec la matrice V initiale...
Il doit y avoir une ribembelle de solutions et là je coince grave.

[invite45567c55]

Complément:
Je peux t'envoyer les algos si tu veux.
V(N,N) contient des valeurs positives. R(N, N) est symetrique et positive. D(N, N) possède des valeurs propres positives (décroissantes, toutes differentes). P(N, N) contient des valeurs négatives et positives. De ce fait, D^1/2 * P ne peux pas coller.

[invite45567c55]

Salut Vincent,

Le principe V'= D^1/2 * P est ok (D = Diag des valeurs Propres de R et P = vecteurs propres de R). Pour check, P * Pt est bien = Identity (orthogonalité des vect. propres) ainsi que V' * V't = R. Les algos sont corrects mais...
==> Le gros pépin est que V' n'a rien a voir avec la matrice V initiale...
Il doit y avoir une ribembelle de solutions et là je coince grave.

Complément:
Meme le cas N=2 ne marche pas. Je peux t'envoyer les algos si tu veux (C).
V(N,N) contient des valeurs positives. R(N, N) est symetrique et positive. D(N, N) possède des valeurs propres positives (décroissantes, toutes differentes). P(N, N) contient des valeurs négatives et positives. De ce fait, D^1/2 * P ne peux pas coller.

a+

[invitec5eb4b89]

En effet la solution n'est pas unique, il faut que tu rajoutes des contraintes pour pouvoir retrouver la matrice initiale (si toutefois tu peux la retrouver...).

[invite45567c55]

Je pense que c'est impossible rien n'est bijectif; meme dès le début en faisant
R = Vt * V, il y a déja une ribembelle de matrices V qui donneront R.
Alors idem via D^1/2.

Donc c'est foutu avec cette méthode.

Question: qu'entends tu par "contraintes" rajouter ?

a+

[invitec5eb4b89]

Je veux dire que le problème (indépendamment de sa méthode de résolution) R = V' V n'admet pas une unique solution. Par exemple les méthodes itératives citées plus haut calculent les valeurs propres et les vecteurs propres dans l'ordre décroissant des valeurs propres.

Peut être que tu as besoin de "dépermuter" les valeurs propres pour retrouver une matrice qui te convient.

Par exemple, en R :

R <- matrix(c(1,0.5,0,0.5,3,1,0,1,2),3,3)
eig <- eigen(R)
d <- diag(eig$values)
p <- eig$vectors

p %*% d %*% t(p) 
p %*% sqrt(d)

s <- c(2,1,3)

p[,s] %*% d [s,s] %*% t(p[,s]) 
p[,s] %*% sqrt(d[s,s])

Soit


R admet comme valeurs propres dans l'ordre décroissant , et on peut conserver cet ordre pour décomposer R en éléments propres, ce qui donne une expression pour V, ou peut peut lui préférer l'ordre , ce qui donne une deuxième expression pour V...

Une décomposition unique pour R serait par exemple une décomposition pour laquelle on imposerait en plus que V soit en plus une matrice triangulaire supérieure.

[invite45567c55]

Je commence (je pense) a comprendre ce que tu me dis.
La permutation des val propres engendre une combinatoires trop importante. Cependant, insiste sur "décomuter".
Je vais me rappeler les matrices triangulaires sup et propriétés. Elle est symetrique par rapport a la diag, c'est ca ?
a+

[invitec5eb4b89]

Une matrice triangulaire supérieure n'a que des 0 en dessous de la diagnale (donc elle n'est pas symétrique, sauf si elle est diagonale) .

Je n'avais pas vu que V était forcément à coefficient tous positifs...

[invite45567c55]

PS: avec tes données, j'ai ca. C'est ok au moins ? Les val propres sont ok.
-6.118e-01
-6.279e-01
-4.811e-01

[invitec5eb4b89]

PS: avec tes données, j'ai ca. C'est ok au moins ? Les val propres sont ok.
-6.118e-01
-6.279e-01
-4.811e-01

Euh, qu'est-ce que c'est ?

[invite45567c55]

Oups.

vec 1: -5.219e-01 -6.714e-01 -5.261e-01
vec2: -8.347e-01 +2.748e-01 +4.773e-01
vec3: -1.759e-01 +6.882e-01 -7.038e-01
a+

[invite45567c55]

Vraiment, je merde. La, c'est bon.

MAT entry:
+1.000e+00 +5.000e-01 0
+5.000e-01 +3.000e+00 +1.000e+00
0 +1.000e+00 +2.000e+00

D = eig values of MAT:
+3.686e+00 0 0
0 +1.500e+00 0
0 0 +8.139e-01

P = eig vectors of MAT:
Vec 1: -1.581e-01 -8.493e-01 -5.037e-01
Vec 2: +4.082e-01 +4.082e-01 -8.165e-01
Vec 3: -8.991e-01 +3.347e-01 -2.822e-01

[invite45567c55]

La mise en forme de V ne pose aucun probleme (coté émeteur).
S'il faut cette propriété (tri. sup.) , ce n'est pas un soucis du moment que le récepteur qui ne recevra que R(apres transformation adaptes) doit savoir retrouver V a partir de R sans ambiguité.
a+

[invite45567c55]

Question:

Avec la matrice d'exemple que tu m'as donné, j'ai fais ttes les combinaisons (6) et je ne retrouve pas l'originial (en prenant les dernieres valeurs que je t'ai envoyé et pas les boulettes des précedentes) !
combinaisons (0...2) des valeurs propres avec les vecteurs propres associés:
0,1,2
0,2,1
1,0,2
2,0,1
2,1,0
1,2,0

[invite45567c55]

Ok. Décomposition Cholesky.
a+