Algoritmo PCA mais rápido para dados de alta dimensão

Eu gostaria de executar um PCA em um conjunto de dados composto por aproximadamente 40.000 amostras, cada uma exibindo cerca de 10.000 recursos.

O uso da função princomp do Matlab leva consistentemente mais de meia hora; nesse ponto, eu mato o processo. Gostaria de encontrar uma implementação / algoritmo que seja executado em menos de 10 minutos. Qual seria o algoritmo mais rápido? Quanto tempo levaria em um i7 dual core / 4GB de RAM?

Primeiro de tudo, você deve especificar se deseja todos os componentes ou os mais significativos?

Indique sua matriz sendo N o número de amostras e a dimensionalidade $A \in \mathbb{R}^{N \times M}$$N$$M$

Caso você deseje todos os componentes, o caminho clássico a seguir é calcular a matriz de covariância (que possui complexidade de tempo de O ( N M 2 ) ) e depois aplicar SVD a ela ( O ( M 3 adicional ) ). Em termos de memória isso levaria O ( 2 H 2 ) (matriz de covariância + vectores singulares e valores que formam base ortogonal) ou ≈ 1,5 GB de dupla precisão para o seu determinado Um .$C \in \mathbb{R}^{M\times M}$$O(NM^2)$$O(M^3)$$O(2M^2)$$\approx 1.5$$A$

Você pode aplicar SVD diretamente à matriz se normalizar cada dimensão anterior a essa e pegar vetores singulares à esquerda. No entanto, praticamente eu esperaria que o SVD da matriz A levasse mais tempo.$A$$A$

Se você precisar de apenas uma fração dos componentes (talvez o mais significativo), convém aplicar o PCA iterativo . Até onde eu sei, todos esses algoritmos estão intimamente relacionados ao processo de Lanczos, portanto, você depende do espectro do e praticamente será difícil obter a precisão do SVD para os vetores obtidos e se degradará com o número de vetores singulares.$C$

Eu acho que você só precisa de alguns (ou algumas centenas) pares de valores / vetores singulares dominantes. Então é melhor usar um método iterativo, que será muito mais rápido e consumirá muito menos memória.

No Matlab, consulte

help svds

Você pode verificar minha resposta em Validação cruzada . Eu não queria copiá-lo aqui. Basicamente, você pode usar SVD rápido e aleatório para calcular a base e os coeficientes do PCA.

Você pode tentar o algoritmo Fast PCA, baseado em uma maneira iterativa de calcular alguns autovetores. Ver A.Sharma e KK Paliwal, análise rápida de componentes principais usando análise de ponto fixo, Pattern Recognition Letters, 28, 1151-1155, 2007 .