Récupér les matrices unitaires de la SVD en utilisant leurs

[Skynet_5345]

Bonjour,

J'ai besoin de votre aide pour résoudre un petit problème qui concerne la décomposition en valeurs singulières SVD. Considérons la SVD d'une matrice connue comme suit :



Où et sont des matrices unitaires et orthogonales, et où signifie la transposée de la matrice.

Maintenant, considérons que les matrices et sont des inconnues, mais leurs produit et aussi les matrices et sont connus, comment peut on retrouver les matrices et ?. J'ai essayer d'utiliser une décomposition matricielle pour avoir un système d'équations linéaires à résoudre mais sans résultats, j'ai pensé aussi à utiliser peut être des matrices de commutation avec la décomposition, brefs, j'ai besoin de votre aide s'il vous plait, des conseils sont les bienvenus.

Merci.

[arnaud32]

es tu sure qu'il ya unicite de la solution?
quelles sont les dimenssions des matrices?

[Skynet_5345]

Oui, la matrice est une matrice carrée à coefficients réels. La Matrice ainsi que la matrice sont des matrices unitaires à coefficients réels ce qui fait qu'ils sont orthogonaux où et .

Je corrige une chose, c'est le produit qui est donné et non .

[fatal_error]

slt,

ya un truc que je comprends pas, sur wiki
U(mxm) et V(nxn)
comment peux-tu écrire le produit UV (ou UV') ?

edit: ah: M est carrée :D

Du coup, si on part de la def, on a
M(m,n)=U(m,m)S(m,n)V'(n,n)
or M est carrée donc m==n, on a donc
M(n,n)=U(n,n)S(n,n)V'(n,n)
M=USV'
MV=US
MVU'=USU'
or (UV')=(VU')' donc si on pose K=UV', on a
MVU'=M(UV')'=MK', et si on pose A=MK', il reste à trouver
A=USU', avec S diagonale.

c'est juste une diagonalisation classique, plus orthonormalisation de U après!

Enfin, je pense

[Skynet_5345]

slt,

ya un truc que je comprends pas, sur wiki
U(mxm) et V(nxn)
comment peux-tu écrire le produit UV (ou UV') ?

edit: ah: M est carrée

Du coup, si on part de la def, on a
M(m,n)=U(m,m)S(m,n)V'(n,n)
or M est carrée donc m==n, on a donc
M(n,n)=U(n,n)S(n,n)V'(n,n)
M=USV'
MV=US
MVU'=USU'
or (UV')=(VU')' donc si on pose K=UV', on a
MVU'=M(UV')'=MK', et si on pose A=MK', il reste à trouver
A=USU', avec S diagonale.

c'est juste une diagonalisation classique, plus orthonormalisation de U après!

Enfin, je pense

Merci pour votre réponse.

C'est une bonne idée, sauf que A = U S U' avec S diagonale je n’ai pas compris comment tu peux avoir la matrice inconnue U de cette expression en utilisant une diagonalisation? et si on considère S non diagonale par exemple ?

[fatal_error]

mais si tu fais une SVD, ta matrice S est censee etre composee des valeurs singulieres sur la diagonale nan?

[Skynet_5345]

mais si tu fais une SVD, ta matrice S est censee etre composee des valeurs singulieres sur la diagonale nan?

En effet, c'est un problème de cryptanalyse, U et V ce sont des clés de cryptage, S c'est la matrice à cryptée, et M c'est la matrice S cryptée par les clés U et V, comme l'opération est linéaire, elle est réversible. J'ai pu avoir le produit UV' et l'exploité dans une décomposition polaire, sauf que je n'arrive toujours pas à avoir U ou V, sachant qu'en connaissant l'un d'eux je peux déduire l'autre.

[fatal_error]

ben pour moi ca m a l air immediat, a partir du moment ou on a A, on la diagonalise, puis avec les valeurs propres donnees de S, on deduit les vecteurs propres associes. On obtient donc la matrice de passage P qu on orthonormalise pour avoir U orthogonale, mais peut etre que je passe complement a cote, je regarderai ca ce soir.

[fatal_error]

un exemple simpliste avec octave:
je decompose M avec U et V.
Je cree K=UV'

et je pars du principe que je connais que :
K, S et M.
Puis on retrouve bien U et V

Code: Tout sélectionner

M=[1 2;
3 4];
[U S V]=svd(M);

% USV'==M

K=U*V';
A=M*K';
[P lambda]=eig(A);
% il faut respecter l'ordre des valeurs propres de S
% lambda contient les meme valeurs mais pas forcement dans le meme ordre
[s, s_orderedIndex]=sort(diag(S));
[p, p_orderedIndex]=sort(diag(lambda));
n=length(orderedIndex);
U=zeros(n);
for i=1:n
  % vector associated to lambda_i of S
  s_vector_index=s_orderedIndex(i);
 
  % vector associated to lambda_i of lambda
  p_vector_index=p_orderedIndex(i);
  U(:,s_vector_index)=P(:,p_vector_index);
  U(:,s_vector_index)/=norm(U(:,s_vector_index));  %normalisation
end
expect0ForUOrthogonal=U-U'
%K'=VU'
%V'=U'inv(K')
%V=inv(K' )'U
V=inv(K' )'*U;
expect0ForUAndVFound=M-U*S*V'



[Skynet_5345]

un exemple simpliste avec octave:
je decompose M avec U et V.
Je cree K=UV'

et je pars du principe que je connais que :
K, S et M.
Puis on retrouve bien U et V

Code: Tout sélectionner

M=[1 2;
3 4];
[U S V]=svd(M);

% USV'==M

K=U*V';
A=M*K';
[P lambda]=eig(A);
% il faut respecter l'ordre des valeurs propres de S
% lambda contient les meme valeurs mais pas forcement dans le meme ordre
[s, s_orderedIndex]=sort(diag(S));
[p, p_orderedIndex]=sort(diag(lambda));
n=length(orderedIndex);
U=zeros(n);
for i=1:n
  % vector associated to lambda_i of S
  s_vector_index=s_orderedIndex(i);
 
  % vector associated to lambda_i of lambda
  p_vector_index=p_orderedIndex(i);
  U(:,s_vector_index)=P(:,p_vector_index);
  U(:,s_vector_index)/=norm(U(:,s_vector_index));  %normalisation
end
expect0ForUOrthogonal=U-U'
%K'=VU'
%V'=U'inv(K')
%V=inv(K' )'U
V=inv(K' )'*U;
expect0ForUAndVFound=M-U*S*V'



Je viens d'essayer ce programme sur Matlab, il récupére pas U et V,voici ce que j'ai obtenu:

Code: Tout sélectionner


expect0ForUOrthogonal =

     0     0
     0     0

expect0ForUAndVFound =

   -1.0000   -6.0000
    1.0000   -4.0000

U =

    1.0000    1.0000
    1.0000    1.0000

V =

    0.3430    0.3430
    1.3720    1.3720


[Skynet_5345]

J'ai pu obtenir U et V en supprimant l'étape de la normalisation nom() ?

Code: Tout sélectionner

M=[1 2;3 4];   
[U S V]=svd(M);   
K = U*V';
A = M*K';
[P lambda] = eig(A);

[s, s_orderedIndex] = sort(diag(S));
[p, p_orderedIndex] = sort(diag(lambda)); 
n = length(s_orderedIndex);
U = zeros(n); 

for i=1:n   
s_vector_index=s_orderedIndex(i);     
p_vector_index=p_orderedIndex(i);     
U(:,s_vector_index)=P(:,p_vector_index);   
end 

test=U-U' 
V=inv(K' )'*U 
expect0ForUAndVFound=M-U*S*V'


Merci pour le programme, en fait c'est que je souhaite réaliser, mais avec une matrice S aléatoire, qui représente la matrice secrète à cryptée avec les clés U et V. Si on prend S une matrice à coefficients aléatoires, on a M = U*S*V' où U et V sont déjà pré-calculées. Au final, on aura seulement M,S, et le produit UV' connues, et le but içi c'est de essayer de calculés les clés U et V à partir de ce qui a été donné afin de testé l'efficacité du cryptage.

[fatal_error]

ben c'est clair que U est pas bonne parce que elle est pas orthogonale.
Moi j'ai runné le code sous octave et les résultats m'ont l'air ok.

Normaliser une matrice c'est pas censer rendre les vecteurs colinéaires!

Et sinon, pour me donner M,S et UV' j'étais obligé de me créer S puis la decomp U et V.
Libre à toi de te créer une [U V] reverseCrypt(M,S,K) mais à priori t'as l'essentiel dans le script!

[Skynet_5345]

ben c'est clair que U est pas bonne parce que elle est pas orthogonale.
Moi j'ai runné le code sous octave et les résultats m'ont l'air ok.

Normaliser une matrice c'est pas censer rendre les vecteurs colinéaires!

Et sinon, pour me donner M,S et UV' j'étais obligé de me créer S puis la decomp U et V.
Libre à toi de te créer une [U V] reverseCrypt(M,S,K) mais à priori t'as l'essentiel dans le script!

Merci pour tes réponses.

Le programme Octave je l'ais bien essayer sur un compilateur en ligne et un compilateur interne, il me donne bien des résultats erronés dans les deux cas. Tu peux revoir ton code stp? http://www.compileonline.com/execute_matlab_online.php

[fatal_error]

non je ne revois pas mon code, c'est juste pour te donner une idée de la manière comment faire.
qui plus est parce que j'ai l'impression que t'essaies même pas de comprendre ce qui se passe.

[Skynet_5345]

non je ne revois pas mon code, c'est juste pour te donner une idée de la manière comment faire.
qui plus est parce que j'ai l'impression que t'essaies même pas de comprendre ce qui se passe.

Drole de façon amicale d'aider les autres, je suis un informaticien expérimenté et je fais de la cryptanalyse, ton code contient des erreurs de calcul et de compilation, mais la solution proposée est correcte, je t'ai demander de corriger ton code pour qu'on soit d'accord sur l'idée qu'on a pas besoin de normalisation, maintenant qu'on est arrivé là, j'ai seulement demandé l'aide d'un mathématicien sinon pourquoi je serais ici si je pouvais me débrouiller seul pour les problèmes purement mathématiques.

[fatal_error]

ton code contient des erreurs de calcul et de compilation, mais la solution proposée est correcte

si tu es d'accord avec la solution proposée, alors c'est bon. :lol3: Que mon code contient des erreurs de calculs, c'est pas important.

je t'ai demander de corriger ton code pour qu'on soit d'accord sur l'idée qu'on a pas besoin de normalisation

Ben non, le code ne montre rien. Si tu veux vérifier le besoin de normalisation c'est pas avec du code mais avec des maths.

Maintenant, si tu considères toujours la normalisation tu vois que dans une diagonalisation quelconque, tu cherches les vecteurs propres qui vont constituer U: Ax=lambda x, et que tout multiple de x est solution. Donc oui il faut la normalisation. C'est juste de la chance s'il s'avère que dans la décomposition d'octave, eig te retourne des vecteurs propres normés. Donc plutot voir l'API d'octave concernant eig pour t'assurer que les vecteurs sont normés auquel cas tu n'as pas besoin de les normer une fois de plus..

Drole de façon amicale d'aider les autres, je suis un informaticien expérimenté

Ben je t'ai proposé une solution. Un code pour illustrer. Tout ce que tu fais c'est dire: ton code ne marche pas. Tu checkes pas si la décomposition de eig est correcte. Tu checkes pas si la matrice U construite est correcte (vecteurs othogonaux). Et l'erreur glissée dans le script est tellement grosse que mon petit doigt me dit que t'as pas bien regardé longtemps le problème!

PS: je suis aussi informaticien, c'est ptet pour ca que ca m'a fait ticker.
PS2: ya une différence entre: tu as une idée? et tu peux revoir ton code?
la deuxième question est passive.

je te concède que j'étais peut etre un peu abrupte. :hum:

[Skynet_5345]

si tu es d'accord avec la solution proposée, alors c'est bon. :lol3: Que mon code contient des erreurs de calculs, c'est pas important.


Ben non, le code ne montre rien. Si tu veux vérifier le besoin de normalisation c'est pas avec du code mais avec des maths.

Maintenant, si tu considères toujours la normalisation tu vois que dans une diagonalisation quelconque, tu cherches les vecteurs propres qui vont constituer U: Ax=lambda x, et que tout multiple de x est solution. Donc oui il faut la normalisation. C'est juste de la chance s'il s'avère que dans la décomposition d'octave, eig te retourne des vecteurs propres normés. Donc plutot voir l'API d'octave concernant eig pour t'assurer que les vecteurs sont normés auquel cas tu n'as pas besoin de les normer une fois de plus..


Ben je t'ai proposé une solution. Un code pour illustrer. Tout ce que tu fais c'est dire: ton code ne marche pas. Tu checkes pas si la décomposition de eig est correcte. Tu checkes pas si la matrice U construite est correcte (vecteurs othogonaux). Et l'erreur glissée dans le script est tellement grosse que mon petit doigt me dit que t'as pas bien regardé longtemps le problème!

PS: je suis aussi informaticien, c'est ptet pour ca que ca m'a fait ticker.
PS2: ya une différence entre: tu as une idée? et tu peux revoir ton code?
la deuxième question est passive.

je te concède que j'étais peut etre un peu abrupte. :hum:

Tous mes retards de réponse c'est le temps passer à comprendre le problème et sa solution quand S n'est pas une matrice diagonale sur mon cahier de notes, bref, désolé si on s'est mal compris, c'est sans rancune, le problème reste ouvert, et toute aide est la bienvenue.