¿Cuál es la complejidad computacional de calcular la matriz de varianza-covarianza?

Estoy usando un cálculo de la matriz de varianza-covarianza en un programa que escribí (para el análisis de componentes principales), y me pregunto cuál es su complejidad. Aunque obviamente la descomposición del vector propio está causando el mayor impacto en el rendimiento, me pregunto cuánto de ese impacto es causado por el cálculo de la matriz de covarianza.

El tiempo de ejecución asintótico que calculo que usa es usando un algoritmo ingenuo, porque tiene que tomar los medios de todos los datos de tamaño N y luego debe hacerlo para cada dimensión (donde n es el número de dimensiones) en una iteración anidada y, por lo tanto, produce una matriz de tamaño n 2 .$O(N\cdot n^2)$$N$$n$$n^2$

¿Es correcta mi suposición, o si no, cuál es la complejidad asintótica?

Tu conjetura es correcta.

Si con N como número de puntos de datos yn siendo el número de características, entonces puede obtener la matriz de covarianza por X T X (aparte de la resta media que puede ignorarse desde una perspectiva de complejidad).$X\in \mathbb{R}^{N \times n}$$N$$n$$X^TX$

$\mathcal{O}(Nn²)$ $2N$$n²$$X$$\mathcal{O}(n^{2.73})$