matrix - ¿Cómo es la complejidad de PCA O(min(p ^ 3, n ^ 3))?
machine-learning time-complexity (3)
He estado leyendo un artículo sobre PCA escasa, que es: http://stats.stanford.edu/~imj/WEBLIST/AsYetUnpub/sparse.pdf
Y establece que, si tiene n puntos de datos, cada uno representado con p características, entonces, la complejidad de PCA es O(min(p^3,n^3)) .
¿Puede alguien explicar cómo / por qué?
A continuación se muestra el código de látex actualizado michaelt proporcionado en png y en el código de látex. Espero que esto ayude. introduzca la descripción de la imagen aquí
Suponiendo que su conjunto de datos es $ X / en R ^ {n / times p} $ donde n: número de muestras, p: dimensiones de una muestra, está interesado en el análisis propio de $ X ^ TX $, que es el costo computacional principal de PCA. Ahora las matrices $ X ^ TX / in / R ^ {p / times p} $ y $ XX ^ T / in / R ^ {n / n / n} $ tienen los mismos valores propios no negativos (n, p) y vectores propios no negativos. Suponiendo que p sea menor que n, puede resolver el análisis propio en $ O (p ^ 3) $. Si p es mayor que n (por ejemplo, en la visión por computadora, en muchos casos la dimensionalidad de la muestra (número de píxeles) es mayor que la cantidad de muestras disponibles), puede realizar un análisis propio en tiempo de $ O (n ^ 3) $. En cualquier caso, puede obtener los vectores propios de una matriz a partir de los valores propios y los vectores propios de la otra matriz y hacerlo en $ O (min (p, n) ^ 3) tiempo.
El cálculo de la matriz de covarianza es O (p 2 n); su descomposición del valor propio es O (p 3 ). Entonces, la complejidad de PCA es O (p 2 n + p 3 ).
O (min (p 3 , n 3 )) implicaría que podría analizar un conjunto de datos bidimensionales de cualquier tamaño en un tiempo fijo, lo que es claramente falso.
Suponiendo que su conjunto de datos es $ X / in / R ^ {nxp} $ donde n: número de muestras, d: dimensiones de una muestra, está interesado en el análisis propio de $ X ^ TX $, que es el costo computacional principal de PCA. Ahora las matrices $ X ^ TX / in / R ^ {pxp} $ y $ XX ^ T / in / R ^ {nxn} $ tienen los mismos valores propios no negativos (n, p) y vectores propios no negativos. Suponiendo que p sea menor que n, puede resolver el análisis propio en $ O (p ^ 3) $. Si p es mayor que n (por ejemplo, en la visión por computadora, en muchos casos la dimensionalidad de la muestra (número de píxeles) es mayor que la cantidad de muestras disponibles), puede realizar un análisis propio en tiempo de $ O (n ^ 3) $. En cualquier caso, puede obtener los vectores propios de una matriz a partir de los valores propios y los vectores propios de la otra matriz y hacerlo en $ O (min (p, n) ^ 3) tiempo.
$$ X ^ TX = V / Lambda V ^ T $$
$$ XX ^ T = U / Lambda U ^ T $$
$$ U = XV / Lambda ^ {- 1/2} $$