Złożoność znalezienia macierzy pseudoinwersyjnej

Ile operacji arytmetycznych jest wymaganych do znalezienia pseudo-odwrotnej macierzy Moore'a i Penrose'a o dowolnym polu?

Jeśli macierz jest odwracalna i ma złożoną wartość, to jest to tylko odwrotność. Znalezienie odwrotności zajmuje czas , gdzie jest stałą mnożenia macierzy. Jest to Twierdzenie 28.2 we Wstępie do Algorytmów 3. edycja.$O(n^\omega)$$\omega$

Jeśli macierz ma liniowo niezależne wiersze lub kolumny i wartość zespoloną, to macierz pseudo-odwrotną można obliczyć odpowiednio za pomocą A ∗ ( A A ∗ ) - 1 lub ( A A ∗ ) - 1 A ∗ , gdzie A ∗ jest transpozycją sprzężoną od A . W szczególności, zakłada O ( n omów ) czas do znalezienia pseudoinverse z A .$A$$A^*(A A^*)^{-1}$$(A A^*)^{-1}A^*$$A^*$$A$$O(n^\omega)$$A$

W przypadku ogólnej matrycy algorytmy, które widziałem, używają rozkładu QR lub SVD, który w najgorszym przypadku wydaje się przyjmować operacje arytmetyczne $O(n^3)$ . Czy istnieją algorytmy, które wykorzystują mniej operacji?

Przede wszystkim ludzie zapominają, że jest wartością minimalną. Ilekroć piszemy O ( n ω ) , faktycznie mamy na myśli, że dla wszystkich γ > ω istnieje algorytm działający w czasie O γ ( n γ ) .$\omega$$O(n^\omega)$$\gamma > \omega$$O_\gamma(n^\gamma)$

Keller-Gehrig pokazał (między innymi), jak przedstawić macierz w postaci normalnej rangi w czasie O ( n ω ) . Jeżeli A ma rangę r , to normalną formą rangi A jest S ( I r 0 0 0 ) T dla niektórych odwracalnych S , T o odpowiednich wymiarach; patrz także Algebraiczna teoria złożoności, Twierdzenie 16.13 na stronie 435.$A$$O(n^\omega)$$A$$r$$A$

$A = XY$$X$$r$$Y$$r$$X$$r$$S$$Y$$r$$T$$O(n^\omega)$