Algorithmes de Monte-Carlo rapides pour trouver des approximations de faible rang

Nous considérons le problème d'approximer une matrice m × n donnée A par une autre matrice de rang spécifié k, qui est plus petite que m et n. La décomposition en valeurs singulières (SVD) peut être utilisée pour trouver la "meilleure" telle approximation. Cependant, cela prend un temps polynomial en m, n, ce qui est prohibitif pour certaines applications modernes. Dans cet article, nous développons un algorithme qui est qualitativement plus rapide, à condition que nous puissions échantillonner les entrées de la matrice conformément à une distribution de probabilité naturelle. Dans de nombreuses applications, un tel échantillonnage peut être effectué efficacement. Notre résultat principal est un algorithme randomisé pour trouver la description d'une matrice D* de rang au plus k de sorte que cela soit vrai avec une probabilité d'au moins 1 − δ (où |·| F est la norme de Frobenius). L'algorithme prend un temps polynomial en k, 1/ϵ, log(1/δ) seulement et est indépendant de m et n. En particulier, cela implique qu'en temps constant, il peut être déterminé si une matrice donnée de taille arbitraire a une bonne approximation de faible rang.