Wydajne pod względem pamięci implementacje częściowych dekompozycji wartości osobliwych (SVD)

10

W celu zmniejszenia modelu chcę obliczyć lewe wektory osobliwe związane z - powiedzmy 20 - największymi wartościami osobliwymi macierzy , gdzie i . Niestety moja matryca będzie gęsta bez żadnej struktury. $A \in \mathbb R^{N,k}$ $N\approx 10^6$ $k\approx 10^3$ $A$

Jeśli po prostu wywołam svdprocedurę z numpy.linalgmodułu w Pythonie dla losowej macierzy tego rozmiaru, napotkam błąd pamięci. Wynika to z podziału dla rozkładu . $V\in \mathbb R^{N,N}$ $A = VSU$

Czy istnieją jakieś algorytmy, które pozwalają uniknąć tej pułapki? Np. Przez ustawienie tylko wektorów pojedynczych powiązanych z niezerowymi wartościami pojedynczymi.

Jestem gotowy na wymianę czasu obliczeń i dokładności.

— Jan
źródło

1

Interesujące wydaje się, że Numpy nie wie, jak zrobić cienkie SVD ...

— JM

Dzięki za podpowiedź. Rzeczywiście, numpy.linalg.svd ma opcję, full_matricesktóra może być ustawiona na False, tak aby obliczane były tylko części „niezerowe”. Niemniej jednak czy istnieje sposób na dalsze ograniczenie obliczeń?

— stycznia 13

3

numpyBackend używa kodu FORTRAN w LAPACKE_dgesvdrutynę dla standardowych SVD. Jednak zazwyczaj macierz jest C_CONTIGOUS(sprawdź za pomocą matrix.flags). Dlatego kopiuje dane do wyrównania fortran. Dodatkowo, podczas uruchamiania procedury lapack dgesvd potrzebna jest kolejna kopia macierzy (lub przynajmniej jej pamięć). Możesz pozbyć się jednej kopii, jeśli od samego początku upewnisz się, że wyrównanie pamięci jest w stylu fortran.

— Bort

6

Jeśli chcesz tylko kilka pojedynczych wartości / wektorów, ARPACK powinien załatwić sprawę . Dokumenty SVD nie są świetne, a ta dystrybucja jest bardziej aktualna.

EDYCJA: Jeśli chcesz to zrobić w Pythonie, SciPy ma opakowanie . Ponieważ macierz jest gęsta, możesz wypróbować format bloku rzadkich wierszy (BSR).

— Max Hutchinson
źródło

Zobaczę, jak ARPACK integruje się z pythonem ...

— Jan

1

Wygląda na to, że scipy ma opakowania. Dodam je, aby odpowiedzieć na ciało.

— Max Hutchinson

2

Spójrz na sklearn.decomposition.TruncatedSVD w scikit-learn 0.14-rc.
(Wierzę, że ludzie uczący się dzięki scikit śledzą stackoverflow.com/questions/tagged/scikit-learn , więc zadam tam szczegółowe pytania).

$^{6+3}$

— denis
źródło

10^{6} \times 10^{3}

$10^6 \times 10^3$

2

Może możesz tego spróbować.

https://github.com/jakevdp/pypropack

Jest to opakowanie Pythona dla pakietu PROPACK, który implementuje efektywne dekompozycje częściowej liczby pojedynczej dużych rzadkich macierzy i operatorów liniowych.

— Mass Zhou
źródło

2

Intel MKL implementuje nowy algorytm Jacobi-SVD. Oto szczegóły implementacji: http://www.netlib.org/lapack/lawnspdf/lawn169.pdf http://www.fernuni-hagen.de/MATHPHYS/veselic/downloads/j02.pdf

I procedura LAPACK: http://software.intel.com/sites/products/documentation/hpc/mkl/mklman/GUID-732F9EE1-BCEC-4D9B-9B93-AF5499B21140.htm#DRMAC08-1

Rozmiar pracy jest oczywiście regulowany. Możesz łatwo wywoływać funkcje C z Pythona za pomocą Cython, SWIG lub dowolnego innego mechanizmu owijania.

— Tolga Birdal
źródło