Complexité de la recherche de la matrice pseudoinverse

Combien d'opérations arithmétiques sont nécessaires pour trouver une matrice pseudoinverse de Moore – Penrose d'un champ arbitraire?

Si la matrice est inversible et de valeur complexe, alors c'est juste l'inverse. Trouver l'inverse prend temps, où est la constante de multiplication de la matrice. Il s'agit du Théorème 28.2 dans Introduction to Algorithms 3rd Edition.$O(n^\omega)$$\omega$

Si la matrice a des lignes ou des colonnes linéairement indépendantes et une valeur complexe, alors la matrice pseudo-inverse peut être calculée avec ou respectivement , où est la transposée conjuguée de . En particulier, cela implique un du temps pour trouver la pseudo d' .$A$$A^*(A A^*)^{-1}$$(A A^*)^{-1}A^*$$A^*$$A$$O(n^\omega)$$A$

Pour la matrice générale, les algorithmes que j'ai vus utilisent la décomposition QR ou SVD, qui semble prendre les opérations arithmétiques dans le pire des cas. Existe-t-il des algorithmes qui utilisent moins d'opérations?$O(n^3)$

Tout d'abord, les gens ont tendance à oublier que est un infimum. Chaque fois que nous écrivons$\omega$ , nous voulons dire que pour tout γ > ω , il y a un algorithme fonctionnant dans le temps O γ ( n γ ) .$O(n^\omega)$$\gamma > \omega$$O_\gamma(n^\gamma)$

Keller-Gehrig a montré (entre autre) la manière de présenter une matrice de rang forme normale dans le temps O ( n ω ) . Si A a un rang r , alors une forme normale de rang A est S ( I r 0 0 0 ) T pour un certain S , T inversible de dimensions appropriées; voir aussi Théorie de la complexité algébrique, proposition 16.13, page 435.$A$$O(n^\omega)$$A$$r$$A$

La forme normale du rang est similaire à la décomposition du rang mentionnée dans l'article de Wikipedia, oùacolonnes etalignes. En effet, nous pouvons prendrepour être les premierscolonnes deetpour être les premiersrangées de. Compte tenu de cette décomposition, Wikipedia donne une formule pour le pseudoinverse en utilisant uniquement l'adjoint hermitien, la multiplication matricielle et l'inverse matriciel. Le pseudoinverse peut donc être calculé en temps.X r Y r X r S Y r T O ( n ω$A = XY$$X$$r$$Y$$r$$X$$r$$S$$Y$$r$$T$$O(n^\omega)$