Por qué PCA de datos por medio de la SVD de los datos?

Question

Esta pregunta es acerca de una manera eficiente para calcular las componentes principales.

1. Muchos de los textos en lineal PCA defienden el uso de singular valor de la descomposición de la casewise de datos. Es decir, si tenemos los datos de $\bf X$ y desea reemplazar las variables ( columnas) por componentes principales, hacemos SVD: $\bf X=USV'$, valores singulares (sq. las raíces de los autovalores) a ocupar la diagonal principal de a $\bf S$, derecho autovectores $\bf V$ son la rotación ortogonal de la matriz de ejes-variables en los ejes de los componentes, a la izquierda autovectores $\bf U$ como $\bf V$, sólo para los casos. Entonces podemos calcular los valores de los componentes como $ \bf C=XV=US$.

2. Otra forma de hacer PCA de las variables es a través de la descomposición de la $\bf R=X'X$ matriz cuadrada (es decir, $\bf R$ puede ser correlaciones o covarianzas etc., entre las variables ). La descomposición puede ser eigen-descomposición o de singular valor de descomposición: cuadrada simétrica positiva semidefinite de la matriz, se le dará el mismo resultado $\bf R=VLV'$ con valores propios como la diagonal de $\bf L$, e $\bf V$ como se describió anteriormente. Los valores de los componentes se $\bf C=XV$.

Ahora, mi pregunta: si los datos de $\bf X$ es una matriz grande, y el número de casos es (que es a menudo el caso) mucho mayor que el número de variables, entonces (1) se espera que sea mucho más lenta que la forma (2), porque (1) se aplica una bastante caro algoritmo (como el SVD) para una matriz grande; calcula y almacena la enorme matriz $\bf U$ que realmente no necesita en nuestro caso (el de la PCA de variables). Si es así, entonces ¿por qué tantas texbooks parecen abogar o simplemente mencionar única manera de (1)? Tal vez es eficiente y que me estoy perdiendo algo?

Answer 1

Aquí es lo que está escrito en la de MATLAB pca función de ayuda, énfasis añadido:

Componente Principal algoritmo que pca se utiliza para realizar el análisis de componentes principales [...]:

'enfermedad vesicular porcina' -- por Defecto. La descomposición de valor Singular (SVD) de X.

'-' -- Autovalor de descomposición (EIG) de la matriz de covarianza. La AIE algoritmo es más rápido que el SVD cuando el número de observaciones, $n$, supera el número de variables, $p$, pero es menos precisa debido a la condición de número de la covarianza es la plaza de la condición de X.

Esto pone de relieve dos consideraciones importantes que uno tiene que mantener en mente. En cuanto a la velocidad: tienes razón en que en $N \gg p$ situación svd(X) (y también svd(X')) es más lento de lo eig(X'*X). Sin embargo, cuando se $N\ll p$, entonces el opuesto es la verdad, y la diferencia puede ser drástica. Aquí está un ejemplo rápido usando MATLAB:

>> X = randn([100000 1000]);
>> tic; svd(X); toc
Elapsed time is 11.602513 seconds.
>> tic; svd(X'); toc
Elapsed time is 30.863609 seconds.
>> tic; eig(X'*X); toc
Elapsed time is 4.084554 seconds.

>> X = randn([100 10000]);
>> tic; svd(X); toc
Elapsed time is 0.095350 seconds.
>> tic; eig(X'*X); toc
Elapsed time is 177.499974 seconds.
>> tic; eig(X*X'); toc
Elapsed time is 0.017370 seconds.

Por supuesto, en el último caso también se puede utilizar eigendecomposition de la matriz de Gram (véase la última línea), que es incluso más rápido después de la enfermedad vesicular porcina. Así cuando comparamos SVD a un eigendecomposition de covarianza o de Gram de la matriz, a continuación, SVD es generalmente más lento, pero no demasiado lento.

Sin embargo, la ayuda de MATLAB indica que hay otra razón por la que todavía prefieren el SVD: a saber, la estabilidad numérica. El muy cálculo de la matriz de covarianza las plazas de la condición de número de $X$, por lo que especialmente en el caso de al $X$ tiene algunos casi colineales columnas (es decir, algunas de las variables están altamente correlacionadas), primer computación en la matriz de covarianza y, a continuación, calcular sus eigendecomposition resultará en la pérdida de precisión en comparación con los directos de enfermedad vesicular porcina.

Answer 2

Aquí están mis 2ct sobre el tema

• La quimiometría conferencia donde por primera vez me enteré de la PCA, se utiliza la solución de (2), pero no fue numéricamente orientado, y mi numerics conferencia fue solo una introducción y no hablar de enfermedad vesicular porcina, tan lejos como puedo recordar.

• Si entiendo Holmes: Rápido de enfermedad vesicular porcina para los Grandes Matrices correctamente, su idea ha sido utilizada para obtener un cálculo rápido de la enfermedad vesicular porcina de largo matrices.
  Eso significaría que un buen SVD aplicación internamente podemos seguir (2) si se encuentra apto matrices (no sé si todavía hay mejores posibilidades). Esto significaría que para una implementación de alto nivel es mejor utilizar la enfermedad vesicular porcina (1) y dejar que el BLAS cuidar el algoritmo que se utiliza internamente.

• Rápida práctico de verificación: OpenBLAS de la enfermedad vesicular porcina parece no hacer esta distinción, en una matriz de 5e4 x 100, svd (X, nu = 0) toma mediana de 3,5 s, mientras que svd (crossprod (X), nu = 0) lleva 54 ms (llamado a partir de R microbenchmark).
  La cuadratura de los autovalores de curso es rápido, y hasta que los resultados de ambas llamadas son equvalent.

  timing  <- microbenchmark (svd (X, nu = 0), svd (crossprod (X), nu = 0), times = 10)
  timing
  # Unit: milliseconds
  #                      expr        min         lq    median         uq        max neval
  #            svd(X, nu = 0) 3383.77710 3422.68455 3507.2597 3542.91083 3724.24130    10
  # svd(crossprod(X), nu = 0)   48.49297   50.16464   53.6881   56.28776   59.21218    10
  

---

actualización: echa un vistazo a Wu, W.; Massart, D. & de Jong, S.: El kernel PCA algoritmos para muchas de datos. Parte I: Teoría y algoritmos , la Quimiometría Inteligentes y Sistemas de Laboratorio , 36, 165 - 172 (1997). DOI: http://dx.doi.org/10.1016/S0169-7439(97)00010-5

En este documento se analizan numérico y computacional de las propiedades de los 4 diferentes algoritmos para la PCA: SVD, eigen descomposición (EVD), NIPALS y el PODER.

Están relacionadas como sigue:

computes on      extract all PCs at once       sequential extraction    
X                SVD                           NIPALS    
X'X              EVD                           POWER

El contexto del trabajo son distintos $\mathbf X^{(30 \times 500)}$, y trabajan en $\mathbf{XX'}$ (kernel PCA) - este es justo el contrario situación como la que usted pregunta. Para responder a su pregunta acerca de la matriz de comportamiento, que es necesario cambiar el significado de "kernel" y "clásica".

No es de extrañar, EVD y de enfermedad vesicular porcina el cambio de lugares, dependiendo de si la clásica o el kernel que se utilizan los algoritmos. En el contexto de esta pregunta, esto significa que uno o el otro puede ser mejor dependiendo de la forma de la matriz.

Pero a partir de su discusión de los "clásicos" de enfermedad vesicular porcina y la EVD es claro que la descomposición de la $\mathbf{X'X}$ es muy usual para calcular el PCA. Sin embargo, no especifican que SVD, se utiliza el algoritmo para que cumplan con el uso de Matlab svd () función.

---

    > sessionInfo ()
    R version 3.0.2 (2013-09-25)
    Platform: x86_64-pc-linux-gnu (64-bit)

    locale:
     [1] LC_CTYPE=de_DE.UTF-8       LC_NUMERIC=C               LC_TIME=de_DE.UTF-8        LC_COLLATE=de_DE.UTF-8     LC_MONETARY=de_DE.UTF-8   
     [6] LC_MESSAGES=de_DE.UTF-8    LC_PAPER=de_DE.UTF-8       LC_NAME=C                  LC_ADDRESS=C               LC_TELEPHONE=C            
    [11] LC_MEASUREMENT=de_DE.UTF-8 LC_IDENTIFICATION=C       

    attached base packages:
    [1] stats     graphics  grDevices utils     datasets  methods   base     

    other attached packages:
    [1] microbenchmark_1.3-0

loaded via a namespace (and not attached):
[1] tools_3.0.2

---

$ dpkg --list libopenblas*
[...]
ii  libopenblas-base              0.1alpha2.2-3                 Optimized BLAS (linear algebra) library based on GotoBLAS2
ii  libopenblas-dev               0.1alpha2.2-3                 Optimized BLAS (linear algebra) library based on GotoBLAS2