Correlaciones extrañas en los resultados SVD de datos aleatorios; ¿tienen una explicación matemática o es un error de LAPACK?

Observo un comportamiento muy extraño en el resultado SVD de datos aleatorios, que puedo reproducir tanto en Matlab como en R. Parece un problema numérico en la biblioteca LAPACK; ¿Lo es?

Extraigo muestras de la Gaussiana dimensional con media cero y covarianza de identidad: . Les reunir en un datos de la matriz . (Opcionalmente, puedo centrar o no, no influye en lo siguiente). Luego realizo una descomposición de valores singulares (SVD) para obtener . Vamos a tomar unos dos elementos particulares de , por ejemplo y , y preguntar qué es la correlación entre ellos a través de diferentes sorteos de . Esperaría que si el número $n=1000$ $k=2$ $X\sim \mathcal N (0, \mathbf I)$ $1000 \times 2$ $\mathbf X$ $\mathbf X$ $\mathbf X=\mathbf{USV}^\top$ $\mathbf U$ $U_{11}$ $U_{22}$ $\mathbf X$ $N_\mathrm{rep}$ de los sorteos es razonablemente grande, entonces todas estas correlaciones deben ser alrededor de cero (es decir, las correlaciones de población deben ser cero, y las correlaciones de muestra serán pequeñas).

Sin embargo, observo algunas correlaciones extrañamente fuertes (alrededor de ) entre , , y , y solo entre estos elementos. Todos los demás pares de elementos tienen correlaciones alrededor de cero, como se esperaba. Así es como se ve la matriz de correlación para los elementos "superiores" de (primeros elementos de la primera columna, luego los primeros elementos de la segunda columna): $\pm0.2$ $U_{11}$ $U_{12}$ $U_{21}$ $U_{22}$ $20$ $\mathbf U$ $10$ $10$

SVD correlaciones extrañas

Observe valores extrañamente altos en las esquinas superiores izquierdas de cada cuadrante.

Fue el comentario de este @ whuber lo que me llamó la atención sobre este efecto. @whuber argumentó que la PC1 y la PC2 no son independientes y presentó esta fuerte correlación como evidencia de ello. Sin embargo, mi impresión es que descubrió accidentalmente un error numérico en la biblioteca LAPACK. ¿Que esta pasando aqui?

Aquí está el código R de @ whuber:

stat <- function(x) {u <- svd(x)$u; c(u[1,1], u[2, 2])};
Sigma <- matrix(c(1,0,0,1), 2);
sim <- t(replicate(1e3, stat(MASS::mvrnorm(10, c(0,0), Sigma))));
cor.test(sim[,1], sim[,2]);

Aquí está mi código de Matlab:

clear all
rng(7)

n = 1000;     %// Number of variables
k = 2;        %// Number of observations
Nrep = 1000;  %// Number of iterations (draws)

for rep = 1:Nrep
    X = randn(n,k);
    %// X = bsxfun(@minus, X, mean(X));
    [U,S,V] = svd(X,0);

    t(rep,:) = [U(1:10,1)' U(1:10,2)'];
end

figure
imagesc(corr(t), [-.5 .5])
axis square
hold on
plot(xlim, [10.5 10.5], 'k')
plot([10.5 10.5], ylim, 'k')

pca svd linear-algebra numerics ameba dice Reinstate Monica
fuente

Si usa n = 4 yk = 3, también verá las correlaciones.

Aksakal

@ Aksakal: sí, de hecho, gracias. Edité para eliminar la diferencia reclamada entre k = 2 yk = 3.

ameba dice Reinstate Monica

Respuestas:

Esto no es un error.

Como hemos explorado (ampliamente) en los comentarios, hay dos cosas que suceden. La primera es que las columnas de están obligadas a cumplir con los requisitos de SVD: cada una debe tener una longitud de unidad y ser ortogonal a todas las demás. Visualización de como una variable aleatoria creado a partir de una matriz aleatoria a través de un algoritmo de SVD particular, por lo tanto en cuenta que estos restricciones funcionalmente independientes crear dependencias estadísticas entre las columnas de . $U$ $U$ $X$ $k(k+1)/2$ $U$

Estas dependencias pueden revelarse en mayor o menor medida al estudiar las correlaciones entre los componentes de , pero surge un segundo fenómeno : la solución SVD no es única. Como mínimo, cada columna de se puede negar independientemente, dando al menos soluciones distintas con columnas. Se pueden inducir fuertes correlaciones (superiores a ) cambiando los signos de las columnas de manera apropiada. (Una forma de hacerlo se da en mi primer comentario a la respuesta de Amoeba en este hilo: todos los $U$ $U$ $2^k$ $k$ $1/2$ $u_{ii},i=1,\ldots, k$ tener el mismo signo, haciéndolos todos negativos o todos positivos con la misma probabilidad.) Por otro lado, todas las correlaciones pueden desaparecer eligiendo los signos al azar, independientemente, con iguales probabilidades. (Doy un ejemplo a continuación en la sección "Editar").

Con cuidado, podemos discernir en parte estos dos fenómenos al leer diagramas de dispersión matriciales de los componentes de . Ciertas características, como la aparición de puntos distribuidos de manera casi uniforme dentro de regiones circulares bien definidas, creen una falta de independencia. Otros, como los diagramas de dispersión que muestran correlaciones claras distintas de cero, obviamente dependen de las elecciones realizadas en el algoritmo, pero tales elecciones son posibles solo debido a la falta de independencia en primer lugar. $U$

La prueba final de un algoritmo de descomposición como SVD (o Cholesky, LR, LU, etc.) es si hace lo que dice. En esta circunstancia, es suficiente comprobar que cuando SVD devuelve el triple de matrices , que el producto recupera , hasta el error de punto flotante previsto ; que las columnas de y de son ortonormales; y que es diagonal, sus elementos diagonales no son negativos y están dispuestos en orden descendente. He aplicado tales pruebas al algoritmo en $(U, D, V)$ $X$ $UDV^\prime$ $U$ $V$ $D$ svdRy nunca lo he encontrado por error. Aunque eso no es una garantía de que sea perfectamente correcto, tal experiencia, que creo que es compartida por muchas personas, sugiere que cualquier error requeriría algún tipo de entrada extraordinaria para manifestarse.

Lo que sigue es un análisis más detallado de los puntos específicos planteados en la pregunta.

Usando Rel svdprocedimiento, primero puede verificar que a medida que aumenta, las correlaciones entre los coeficientes de debilitan, pero aún son distintas de cero. Si simplemente realizara una simulación más grande, descubriría que son significativos. (Cuando , 50000 iteraciones deberían ser suficientes). Al contrario de lo que afirma la pregunta, las correlaciones no "desaparecen por completo". $k$ $U$ $k=3$

En segundo lugar, una mejor manera de estudiar este fenómeno es volver a la cuestión básica de la independencia de los coeficientes. Aunque las correlaciones tienden a ser cercanas a cero en la mayoría de los casos, la falta de independencia es claramente evidente. Esto se hace más evidente mediante el estudio de la distribución multivariada completo de los coeficientes de . La naturaleza de la distribución emerge incluso en pequeñas simulaciones en las que las correlaciones distintas de cero no pueden (todavía) detectarse. Por ejemplo, examine una matriz de diagrama de dispersión de los coeficientes. Para que esto sea factible, configuré el tamaño de cada conjunto de datos simulado en y mantuve , dibujando así realizaciones de $U$ $4$ $k=2$ $1000$ $4\times 2$ Matriz , creando una matriz . Aquí está su matriz de diagrama de dispersión completa, con las variables enumeradas por sus posiciones dentro de : $U$ $1000\times 8$ $U$

Figura

Escanear la primera columna revela una interesante falta de independencia entre y el otro : observe cómo el cuadrante superior del diagrama de dispersión con está casi vacante, por ejemplo; o examine la nube elíptica con pendiente ascendente que describe la relación y la nube con pendiente descendente para el . Una mirada cercana revela una clara falta de independencia entre casi todos estos coeficientes: muy pocos de ellos parecen remotamente independientes, aunque la mayoría de ellos exhiben una correlación cercana a cero. $u_{11}$ $u_{ij}$ $u_{21}$ $(u_{11}, u_{22})$ $(u_{21}, u_{12})$

(Nota: la mayoría de las nubes circulares son proyecciones de una hiperesfera creada por la condición de normalización que obliga a la suma de cuadrados de todos los componentes de cada columna a ser la unidad).

Matrices diagrama de dispersión con y patrones similares de exposición: estos fenómenos no se limitan a , ni hacer que dependen del tamaño de cada conjunto de datos simulados: que acaba de obtener más difícil generar y examinar. $k=3$ $k=4$ $k=2$

Las explicaciones para estos patrones van al algoritmo utilizado para obtener en la descomposición del valor singular, pero sabemos que tales patrones de no independencia deben existir por las propiedades definitorias de : dado que cada columna sucesiva es (geométricamente) ortogonal a la anterior En estos casos, estas condiciones de ortogonalidad imponen dependencias funcionales entre los coeficientes, lo que se traduce en dependencias estadísticas entre las variables aleatorias correspondientes. $U$ $U$

Editar

En respuesta a los comentarios, puede valer la pena comentar en qué medida estos fenómenos de dependencia reflejan el algoritmo subyacente (para calcular una SVD) y cuánto son inherentes a la naturaleza del proceso.

Los patrones específicos de correlaciones entre coeficientes dependen en gran medida de elecciones arbitrarias realizadas por el algoritmo SVD, porque la solución no es única: las columnas de siempre pueden multiplicarse independientemente por o . No hay forma intrínseca de elegir el signo. Por lo tanto, cuando dos algoritmos SVD realizan elecciones de signo diferentes (arbitrarias o incluso aleatorias), pueden dar lugar a diferentes patrones de diagramas de dispersión de los . Si desea ver esto, reemplace la función en el código a continuación por $U$ $-1$ $1$ $(u_{ij}, u_{i^\prime j^\prime})$ stat

stat <- function(x) {
  i <- sample.int(dim(x)[1]) # Make a random permutation of the rows of x
  u <- svd(x[i, ])$u         # Perform SVD
  as.vector(u[order(i), ])   # Unpermute the rows of u
}

Este primero reordena aleatoriamente las observaciones x, realiza SVD, luego aplica el orden inverso para uque coincida con la secuencia de observación original. Debido a que el efecto es formar mezclas de versiones reflejadas y rotadas de los diagramas de dispersión originales, los diagramas de dispersión en la matriz se verán mucho más uniformes. Todas las correlaciones de muestra serán extremadamente cercanas a cero (por construcción: las correlaciones subyacentes son exactamente cero). Sin embargo, la falta de independencia seguirá siendo obvia (en las formas circulares uniformes que aparecen, particularmente entre y ). $u_{i,j}$ $u_{i,j^\prime}$

La falta de datos en algunos cuadrantes de algunos de los diagramas de dispersión originales (que se muestran en la figura anterior) surge de cómo el Ralgoritmo SVD selecciona signos para las columnas.

Nada cambia sobre las conclusiones. Debido a que la segunda columna de es ortogonal a la primera, (considerada como una variable aleatoria multivariada) depende de la primera (también considerada como una variable aleatoria multivariada). No puede hacer que todos los componentes de una columna sean independientes de todos los componentes de la otra; todo lo que puede hacer es mirar los datos de manera que oscurezcan las dependencias, pero la dependencia persistirá. $U$

Aquí hay un Rcódigo actualizado para manejar los casos y dibujar una porción de la matriz de diagrama de dispersión. $k\gt 2$

k <- 2    # Number of variables
p <- 4    # Number of observations
n <- 1e3  # Number of iterations
stat <- function(x) as.vector(svd(x)$u)
Sigma <- diag(1, k, k); Mu <- rep(0, k)
set.seed(17)
sim <- t(replicate(n, stat(MASS::mvrnorm(p, Mu, Sigma))))
colnames(sim) <- as.vector(outer(1:p, 1:k, function(i,j) paste0(i,",",j)))
pairs(sim[, 1:min(11, p*k)], pch=".")

whuber
fuente

La correlación ocurre entre los primeros componentes de las columnas de porque así es como funciona el algoritmo SVD. Que las filas de son gaussianas es irrelevante: estoy seguro de que has notado que los coeficientes de no son gaussianos.

U

$U$

X

$X$

U

$U$

whuber

Por cierto, ¡acabo de descubrir que el simple reemplazo svd(X,0)de svds(X)mi código Matlab hace que el efecto desaparezca! Hasta donde sé, estas dos funciones usan diferentes algoritmos SVD (ambas son rutinas LAPACK, pero aparentemente diferentes). No sé si R tiene una función similar a la de Matlab svds, pero me pregunto si aún va a mantener que es un efecto "real" y no un problema numérico.

ameba dice Reinstate Monica

Señores, esperen un minuto. ¿Por qué no estás hablando de la señal? El signo de un vector propio es básicamente arbitrario. Pero el programa de svd no lo asigna al azar, el signo depende de la implementación de svd y de los datos. Si, después de extraer U, decide aleatoriamente si cada una de sus columnas permanecerá como está o si cambiará su signo, ¿no se desvanecerán las correlaciones de las que está hablando?

ttnphns

@ttnphns Eso es correcto, como se explica en mi edición. Aunque eso hace que las correlaciones desaparezcan, las dependencias entre las columnas de no desaparecen. (La versión mejorada de I suministrada es equivalente a cambiar aleatoriamente los signos de las columnas.)

U

$U$ stat

whuber

Un punto menor (¡a este gran hilo!) La SVD no necesita que los elementos en la diagonal de Sestén en un orden particular; Es una cuestión de conveniencia. Otras rutinas lo garantizan (por ejemplo, MATLAB's svds) pero ese no es un requisito general. @amoeba: Al observar svds(lo que parece estar libre de este comportamiento problemático), el cálculo se basa en el cálculo real de los valores propios primero (por lo que no utiliza las rutinas estándar dgesdd/ dgesvdLAPACK; sospecho que usa dsyevr/ dsyevxal principio).

usεr11852 dice Reinstate Monic

Esta respuesta presenta una réplica de los resultados de @ whuber en Matlab, y también una demostración directa de que las correlaciones son un "artefacto" de cómo la implementación de SVD elige el signo para los componentes.

Dada la larga cadena de comentarios potencialmente confusos, quiero enfatizar para los futuros lectores que estoy totalmente de acuerdo con lo siguiente:

En el contexto de esta discusión, ciertamente es una variable aleatoria. $\mathbf U$
Las columnas de deben ser de longitud . Esto significa que los elementos dentro de cada columna no son independientes; sus cuadrados suman uno. Sin embargo, esto no implica ninguna correlación entre y para , y la correlación de la muestra debe ser pequeña para un gran número de sorteos aleatorios. $\mathbf U$ $1$ $U_{i1}$ $U_{j1}$ $i\ne j$ $N_\mathrm{rep}$
Las columnas de tienen que ser ortogonales. Esto significa que los elementos de diferentes columnas no son independientes; su producto punto es cero. Nuevamente, esto no implica ninguna correlación entre y , y la correlación de la muestra debe ser pequeña. $\mathbf U$ $U_{i1}$ $U_{j2}$

Mi pregunta fue: ¿por qué vemos altas correlaciones de incluso para un gran número de sorteos aleatorios ? $\sim 0.2$ $N_\mathrm{rep}=1000$

Aquí hay una réplica del ejemplo de @ whuber con , y en Matlab: $n=4$ $k=2$ $N_\mathrm{rep}=1000$

SVD

A la izquierda está la matriz de correlación, a la derecha - diagramas de dispersión similares a los de @ whuber. El acuerdo entre nuestras simulaciones parece perfecto.

Ahora, siguiendo una sugerencia ingeniosa de @ttnphns, asigno signos aleatorios a las columnas de , es decir, después de esta línea: $U$

[U,S,V] = svd(X,0);

Añado las dos líneas siguientes:

U(:,1) = U(:,1) * sign(randn(1));
U(:,2) = U(:,2) * sign(randn(1));

Aquí está el resultado:

SVD con signos aleatorios

¡Todas las correlaciones desaparecen, exactamente como esperaba desde el principio !

Como dice @whuber, la falta de independencia se puede ver en la forma circular perfecta de algunos gráficos de dispersión (debido a que la longitud de cada columna debe ser igual a , la suma de cuadrados de cualquiera de los dos elementos no puede exceder ). Pero las correlaciones desaparecen. $1$ $1$

$\mathbf U$ $\mathbf U$

PD. ¡Felicitaciones a @whuber por pasar 100k reputación hoy!

ameba dice Reinstate Monica
fuente

statstat <- function(x) { u <- svd(x)$u; as.vector(sign(runif(1) - 1/2)*u %*% diag(sign(diag(u)))) }

U

$U$

(u_{11}, u_{22}, \dots, u_{k k})

$(u_{11}, u_{22}, \ldots, u_{kk})$

U

$U$

U

$U$

svdssvd

U

$U$

U

$U$

R

\pm 2 / 3

$\pm 2/3$

0.2

$0.2$

U

$U$

Intuitivamente, eso es justo. Tan pronto como el primer eje principal se define en el espacio, el resto pr. los ejes obtienen libertad reducida. En el caso de datos 2D, la segunda (última) PC está vinculada por completo, excepto el signo. Prefiero llamarlo restricción, no dependencia en sentido estadístico.

ttnphns

$x$ $y$

x^{2} + y^{2} = 1

$x^2+y^2=1$

C o v [x, y] = V a r [x y] = E [x^{2} y^{2}] - E [x y]^{2}

$Cov[x,y]=Var[xy]=E[x^2y^2]-E[xy]^2$

$x$ $y$

Aksakal
fuente

k (k + 1) / 2

$k(k+1)/2$

U

$U$

U

$U$

D

$D$

U

$U$

U D

$UD$

k (k - 1) / 2

$k(k-1)/2$

U

$U$

1

$1$

U

$U$

n

$n$

k

$k$

n > k

$n>k$

U

$U$

n

$n$

n = 1000

$n=1000$

n = 4

$n=4$

x^{2} + y^{2} = 1

$x^2+y^2=1$

U

$U$

x

$x$

U

$U$

y

$y$

x^{2} + y^{2} = 1

$x^2+y^2=1$

Cov (x, y) = 0

$\text{Cov}(x,y)=0$

x = \cos (θ)

$x=\cos(\theta)$

y = \sin (θ)

$y=\sin(\theta)$

θ

$\theta$

[0, 2 π)

$[0,2\pi)$

U

$U$

U_{i j}

$U_{ij}$

0

$0$

1 / n

$1/n$

n

$n$

n \cdot 1 / n = 1

$n \cdot 1/n = 1$

U

$U$

X

$X$

U_{11}

$U_{11}$

U_{21}

$U_{21}$

ρ

$\rho$

n

$n$

ρ

$\rho$

ρ

$\rho$

ρ = 0

$\rho=0$

ameba dice Reinstate Monica