PCA jest zbyt wolny, gdy oba n, p są duże: alternatywy?

Konfiguracja problemu

Mam punkty danych (obrazy) o wysokim wymiarze (4096), które próbuję zwizualizować w 2D. W tym celu używam t-sne w sposób podobny do poniższego przykładowego kodu autorstwa Karpathy .

Dokumentacja scikit-learn zaleca użycie PCA, aby najpierw obniżyć wymiar danych:

Zdecydowanie zaleca się stosowanie innej metody redukcji wymiarów (np. PCA dla danych gęstych lub TruncatedSVD dla danych rzadkich) w celu zmniejszenia liczby wymiarów do rozsądnej ilości (np. 50), jeśli liczba cech jest bardzo wysoka.

Używam tego kodu od Darks.Liu do wykonania PCA w Javie:

//C=X*X^t / m
DoubleMatrix covMatrix = source.mmul(source.transpose()).div(source.columns);
ComplexDoubleMatrix eigVal = Eigen.eigenvalues(covMatrix);
ComplexDoubleMatrix[] eigVectorsVal = Eigen.eigenvectors(covMatrix);
ComplexDoubleMatrix eigVectors = eigVectorsVal[0];
//Sort sigen vector from big to small by eigen values 
List<PCABean> beans = new ArrayList<PCA.PCABean>();
for (int i = 0; i < eigVectors.columns; i++) {
    beans.add(new PCABean(eigVal.get(i).real(), eigVectors.getColumn(i)));
}
Collections.sort(beans);
DoubleMatrix newVec = new DoubleMatrix(dimension, beans.get(0).vector.rows);
for (int i = 0; i < dimension; i++) {
    ComplexDoubleMatrix dm = beans.get(i).vector;
    DoubleMatrix real = dm.getReal();
    newVec.putRow(i, real);
}
return newVec.mmul(source);

Używa jblas do operacji algebry liniowej, co z tego, co przeczytałem, powinno być najszybszą dostępną opcją. Jednak obliczanie wektorów własnych i wartości własnych (linie 3,4) okazuje się ogromnym wąskim gardłem (~ 10 minut, co jest znacznie dłuższe, niż mogę sobie pozwolić na ten etap).

Czytałem o jądrze PCA, które powinno być dobre w przypadkach, w których wymiar jest bardzo duży, ale jego środowisko wykonawcze jest $O(n^3)$co może być problematyczne, ponieważ chcę również zająć się sprawami o dużym wymiarze i liczbie przykładów.

Według mnie, moimi opcjami jest albo „optymalizacja” PCA, albo wybranie innej metody redukcji wymiarów, która jest z natury szybsza.

Moje pytania

1. Czy jest jakaś nadzieja, że ​​PCA może być używane w trybie „offline”? tzn. używając dużego zestawu danych obrazów, wykonaj na nich PCA, a następnie użyj obliczonych dla nich głównych składników, aby zmniejszyć wymiar innych (nowych!) punktów danych?
2. Czy mogę przyspieszyć obliczanie wektorów własnych, zakładając, że wiem z wyprzedzeniem, że interesują mnie tylko, powiedzmy, 100 najważniejszych składników?
3. Czy istnieje alternatywna metoda redukcji wymiarów, która jest odpowiednia w moim przypadku (tj. Przed zastosowaniem t-sne), która będzie szybsza niż PCA? Szukam czegoś, co można łatwo zaimplementować w Javie.

Pytanie 1: Powiedzmy, że zaobserwowałeś macierz danych $X \in \mathbb R^{n \times p}$. Na tej podstawie możesz obliczyć skład eigend$X^T X = Q \Lambda Q^T$. Pytanie brzmi: czy otrzymamy nowe dane pochodzące od tej samej populacji, być może zgromadzone w matrycy$Z \in \mathbb R^{m \times p}$, będzie $ZQ$ być blisko idealnego obrotu prostopadłego do $Z$? Tego rodzaju pytanie rozwiązuje twierdzenie Davisa-Kahana i ogólna teoria perturbacji macierzy (jeśli można uzyskać kopię, standardowy podręcznik Stewarta i Sun z 1990 r.).

Pytanie 2: zdecydowanie możesz przyspieszyć, jeśli wiesz, że potrzebujesz tylko góry $k$wektory własne. W RI użyj rARPACKdo tego; Jestem pewien, że istnieje odpowiednik Javy, ponieważ i tak są to wszystkie opakowania fortran.

Pytanie 3: Nic nie wiem o implementacjach Java, ale ten wątek omawia przyspieszenie PCA, podobnie jak ten wątek CV. Istnieje mnóstwo badań tego rodzaju i istnieje mnóstwo metod wykorzystujących takie rzeczy, jak przybliżenia niskiej rangi lub randomizacja.

Używany kod odwróci całą macierz. Jest to prawdopodobnie już O (p ^ 3). Możesz przybliżyć wynik do O (p ^ 2), ale nadal będzie on wolny (ale prawdopodobnie 100 razy szybszy). Zasadniczo weź dowolny wektor i wykonaj iteracje mocy. Z dużym prawdopodobieństwem otrzymasz dobre przybliżenie pierwszego wektora własnego. Następnie usuń ten czynnik z matrycy, powtórz, aby uzyskać drugi. Itp.

Ale czy próbowałeś, czy szybkie implementacje Barnes Hut tSNE w ELKI mogą po prostu działać na twoich danych z indeksem, takim jak drzewo okładki? Miałem tę implementację działającą dobrze, gdy inni zawiedli.

Jeśli Twoim celem jest tylko proste i bezpośrednie zmniejszenie wymiarów, możesz wypróbować technikę naprzemiennej najmniejszych kwadratów (ALS). Na przykład Apache Spark mlibma implementację ALS i wierzę, że oferuje interfejs Java. To powinno ci dać$n \times K$ macierz i a $K \times p$matryca. The$K \times p$ macierz będzie zawierać widoczne wektory wierszowe.