Jak skaluje się różne techniki statystyczne (regresja, PCA itp.) Wraz z wielkością i rozmiarem próbki?

Czy istnieje znana ogólna tabela technik statystycznych, która wyjaśnia, w jaki sposób skalują się w zależności od wielkości i wymiaru próbki? Na przykład mój przyjaciel powiedział mi kiedyś, że czas obliczeń po prostu szybkiego sortowania jednowymiarowych danych o rozmiarze n jest równy n * log (n).

Na przykład, jeśli cofniemy y względem X, gdzie X jest zmienną d-wymiarową, to czy będzie to O (n ^ 2 * d)? Jak skaluje się, jeśli chcę znaleźć rozwiązanie za pomocą dokładnego rozwiązania Gaussa-Markowa w porównaniu do najmniejszych kwadratów metodą Newtona? A może po prostu otrzymujesz rozwiązanie w porównaniu z testami istotności?

Chyba bardziej chcę dobrego źródła odpowiedzi (takiego jak artykuł podsumowujący skalowanie różnych technik statystycznych) niż dobrej odpowiedzi tutaj. Jak, powiedzmy, lista obejmująca skalowanie regresji wielokrotnej, regresji logistycznej, PCA, regresji proporcjonalnej hazardu Coxa, grupowanie K-średnich itp.

Większość wydajnych (i nietrywialnych) algorytmów statystycznych ma charakter iteracyjny, więc analiza najgorszego przypadku O()jest nieistotna, ponieważ najgorszym przypadkiem jest „brak zbieżności”.

Niemniej jednak, gdy masz dużo danych, nawet algorytmy liniowe ( O(n)) mogą być powolne, a następnie musisz skupić się na stałej „ukrytej” za notacją. Na przykład obliczenie wariancji pojedynczego wariantu wykonuje się naiwnie dwukrotnie skanując dane (raz w celu obliczenia szacunkowej średniej, a następnie raz w celu oszacowania wariancji). Ale można to również zrobić za jednym razem .

W przypadku algorytmów iteracyjnych ważniejsze jest tempo konwergencji i liczba parametrów w funkcji wymiarowości danych, element, który ma duży wpływ na konwergencję. W wielu modelach / algorytmach rośnie liczba parametrów wykładniczych wraz z liczbą zmiennych (np. Splajny), podczas gdy inne rosną liniowo (np. Maszyny wektorów wsparcia, losowe lasy, ...)

W tytule wspomniałeś o regresji i PCA, a dla każdego z nich jest jednoznaczna odpowiedź.

Asymptotyczna złożoność regresji liniowej zmniejsza się do O (P ^ 2 * N), jeśli N> P, gdzie P jest liczbą cech, a N jest liczbą obserwacji. Więcej szczegółów w złożoności obliczeniowej operacji regresji metodą najmniejszych kwadratów .

Waniliowy PCA to O (P ^ 2 * N + P ^ 3), jak w najszybszym algorytmie PCA dla danych wielowymiarowych . Czy istnieją jednak szybkie algorytmy dla bardzo dużych matryc, wyjaśnione w tej odpowiedzi i najlepszy algorytm PCA dla ogromnej liczby funkcji? .

Jednak nie sądzę, aby ktokolwiek skompilował choć jedną recenzję, referencję lub książkę na ten temat. To może nie być zły projekt dla mojego wolnego czasu ...

Udzieliłem bardzo ograniczonej częściowej odpowiedzi na pakiet analizy czynnikowej, który opracowałem dla Staty w tym artykule Stata Journal, w oparciu o czas rzeczywistych symulacji. Analiza czynnikowa potwierdzająca została wdrożona jako technika szacowania maksymalnego prawdopodobieństwa i bardzo łatwo mogłem zobaczyć, jak czas obliczeń rośnie z każdym wymiarem (wielkość próby n, liczba zmiennych p, liczba czynników k). Ponieważ jest to w dużej mierze zależne od tego, jak Stata myśli o danych (zoptymalizowana do obliczeń w kolumnach / obserwacjach zamiast w wierszach), zauważyłem, że wydajność jestO(n^{0.68} (k+p)^{2.4})gdzie 2.4 jest najszybszą asymptotyczną inwersją macierzy (a jest tego sporo w potwierdzającej iteracyjnej maksymalizacji analizy czynnikowej). Nie podałem odniesienia do tego drugiego, ale myślę, że dostałem to z Wikipedii .

X'X$10^8$