Złożoność znalezienia składowej składowej macierzy * symetrycznej *

To jest wyspecjalizowana wersja poprzedniego pytania: Złożoność znalezienia składowej macierzy .

W przypadku macierzy symetrycznych NxN wiadomo, że czas O (N ^ 3) wystarcza do obliczenia rozkładu własnego. Pytanie brzmi: czy możemy osiągnąć sub-sześcienną złożoność? Dzięki.

— Lihong Li
źródło

Czy to naprawdę wymaga osobnego pytania? Z pewnością, gdyby ktoś znał odpowiedź na ten szczególny przypadek, powiedziałby to w innym pytaniu.

— Warren Schudy,

Podkreśliłem najgorszy przypadek w moim pytaniu, więc myślę, że to jest sprawiedliwe ...

— Lev Reyzin

Czy jesteś pewien, że czas O (N ^ 3) jest ograniczony? Zobacz moje powiązane pytanie dotyczące eliminacji Gaussa.

— Jeffε

Wygląda na to, że można uzyskać z mathoverflow.net/questions/24287/ ...

O (n^{3})

$O(n^3)$ dla przybliżonego rozwiązania.

— Lew Reyzin

Moim zdaniem ten szczególny przypadek nie jest łatwiejszy niż ogólny. Czysto symbolicznie można zredukować problem znajdowania rozkładu wartości pojedynczej (SVD) do problemu diagonalizacji macierzy symetrycznej. SVD M można odczytać z wektorów własnych i wartości własnych M * M. Zwróć uwagę, że redukcja obejmuje jedynie mnożenie macierzy do obliczenia M * M. Nie wydaje się, aby istniały jakiekolwiek poważne problemy numeryczne.