Złożoność znalezienia macierzy pseudoinwersyjnej


11

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ω)ω

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 .AA(AA)1(AA)1AAAO(nω)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(n3) . Czy istnieją algorytmy, które wykorzystują mniej operacji?


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 , n jest rzeczywiście wymiarem macierzy kwadratowej; jeśli macierz nie jest kwadratowa, prawdopodobnie możesz przyjąć, że n jest większym wymiarem. O(nω)nn
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

Odpowiedzi:


7

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 γ ) .ωO(nω)γ>ωOγ(nγ)

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.AO(nω)ArA

S(Ir000)T
S,T

A=XYXrYrXrSYrTO(nω)


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

1
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ω)w

ωω<2.3728639ω=2
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.