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ą lub , gdzie jest transpozycją sprzężoną od . W szczególności, zakłada czas do znalezienia pseudoinverse z . $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?

algorithms linear-algebra

— Chao Xu
źródło

Mam kontynuację, może to być zbyt proste, ale czy możesz potwierdzić, co jest n w równaniu złożoności. Czy jest to wymiar macierzy, a co jeśli matryca nie jest kwadratem?

— Mike Pomp

W twierdzeniu, że odwrotność można znaleźć w czasie

jest rzeczywiście wymiarem macierzy kwadratowej; jeśli macierz nie jest kwadratowa, prawdopodobnie możesz przyjąć, że

jest większym wymiarem.

O (n^{ω})

$O(n^\omega)$

n

$n$

n

$n$

— David Richerby

Ponieważ jest to łatwe pytanie, odpowiedziałem tutaj. Jeśli jednak masz dodatkowe pytania, zadaj je samodzielnie jako stronę za pomocą przycisku „zadaj pytanie” u góry strony. Możesz podać link do tej strony, aby podać kontekst. Ta strona jest skonfigurowana tylko dla jednego pytania na stronę: nie ma wątków, a posty poruszają się zgodnie z otrzymanymi głosami, więc sprawy stają się strasznie nieporządne z więcej niż jednym pytaniem na stronie. Więcej informacji znajduje się na naszej krótkiej prezentacji oraz w naszym centrum pomocy .

— David Richerby

Przede wszystkim ludzie zapominają, że jest wartością minimalną. Ilekroć piszemy , faktycznie mamy na myśli, że dla wszystkich istnieje algorytm działający w czasie . $\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 . Jeżeli ma rangę , to normalną formą rangi jest dla niektórych odwracalnych 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$

S (\begin{matrix} I_{r} & 0 \\ 0 & 0 \end{matrix}) T

$S \begin{pmatrix} I_r & 0 \\ 0 & 0 \end{pmatrix} T$

S, T

$S,T$

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

— Yuval Filmus
źródło

Dziękuję za Twoją odpowiedź! Dostałem papier i okazało się, że brakuje mi tła. Czy są jakieś dobre wprowadzenie / ankieta na temat tego rodzaju wyników? Wiem, że teoria złożoności algebraicznej jest dobra, ale obecnie jest wypisana z biblioteki ...

— Chao Xu

Mogą istnieć odpowiednie notatki z wykładów, choć prawdopodobnie najlepiej jest zajrzeć do książki. CLRS (Wprowadzenie do algorytmów) zawiera także pewien istotny materiał, taki jak równoważność między mnożeniem macierzy a odwrotnością macierzy.

— Yuval Filmus

O (n^{ω})

$O(n^ω)$

w

$w$

ω

$\omega$

ω < 2.3728639

$\omega < 2.3728639$

ω = 2

$\omega = 2$