Diagonalisation simultanée de matrices incomplètes et applications

Soient P et Q des matrices de taille p x n, resp. q x n, et de rangs respectifs p, q (<=n) et {U_i}_i une liste finie de matrices diagonales de dimension n.

Dans cet exposé, nous allons nous intéresser au problème de l’algèbre linéaire suivant: récupérer les éléments diagonaux des matrices {U_i}_i à partir des matrices {W_i}_i (de taille p x q) satisfaisant W_i = P*U_i*Q. Nous interprétons ce problème comme un problème de diagonalisation simultanée de matrices incomplètes.

Nous allons d’abord motiver l’étude de ce problème et ensuite décrire un algorithme pour le résoudre. Finalement, nous mentionnons des applications reliées à la cryptographie, et nous discutons en détail le problème du diviseur commun approché basé sur le théorème des restes chinois, et un meilleur algorithme se basant sur nos techniques.

L’exposé est basé sur un article commun avec Jean-Sébastien Coron et Gabor Wiese.