Qual é a complexidade computacional do cálculo da matriz de variância-covariância?

8

Estou usando um cálculo da matriz Variância-Covariância em um programa que escrevi (para Análise de Componentes Principais) e fico imaginando qual é a complexidade dela. Embora obviamente a decomposição do Eigenvector esteja causando o maior impacto no desempenho, estou me perguntando quanto desse impacto é causado pelo cálculo da matriz de Covariance.

O tempo de execução assintótico que eu estimo usar é O(Nn2) usando um algoritmo ingênuo, porque ele precisa usar todos os dados de tamanho N e, em seguida, precisa fazer isso para todas as dimensões (onde n é o número de dimensões) em uma iteração aninhada e, assim, produz um n2 matriz de tamanho.

Minha suposição está correta ou, se não, qual é a complexidade assintótica?

Ainda outro geek
fonte

Respostas:

2

Sua conjectura está correta.

E se XRN×n com N como número de pontos de dados e n sendo o número de recursos, você pode obter a matriz de covariância XTX (além da subtração média que pode ser ignorada de uma perspectiva de complexidade).

Assim, covariance matrix computação é matriz de multiplicação que é ingenuamente, de facto, vê aqui , já que você tem que fazer cerca de operações para preencher cada um dos posições em sua matriz de covariância . Na prática, a multiplicação de matrizes é acelerada para para matrizes quadráticas (veja o link).O(Nn²) 2Nn²XO(n2,73)

dopexxx
fonte