¿Por qué no puedo obtener un válido SVD de X a través de autovalor de la descomposición de XX' y X X?

Question

Estoy tratando de hacer SVD con la mano:

m<-matrix(c(1,0,1,2,1,1,1,0,0),byrow=TRUE,nrow=3)

U=eigen(m%*%t(m))$vector
V=eigen(t(m)%*%m)$vector
D=sqrt(diag(eigen(m%*%t(m))$values))

U1=svd(m)$u
V1=svd(m)$v
D1=diag(svd(m)$d)

U1%*%D1%*%t(V1)
U%*%D%*%t(V)

Pero la última línea de no retorno m de nuevo. Por qué? Parece que tiene algo que ver con los signos de estos vectores propios... O no me entienden mal el procedimiento?

Answer 1

Análisis del Problema

El SVD de la matriz nunca es único. Vamos matriz $A$ tiene dimensiones de la $n\times k$ y deje que su enfermedad vesicular porcina ser

$$A = U D V^\prime$$

for an $n\times p$ matrix $U$ with orthonormal columns, a diagonal $p\times p$ matrix $D$ with non-negative entries, and a $k\times p$ matrix $V$ with orthonormal columns.

Now choose, arbitrarily, any diagonal $p\times p$ matrix $S$ having $\pm 1$s on the diagonal, so that $S^2 = I$ is the $p\times p$ identity $I_p$. Then

$$A = U D V^\prime = U I D I V^\prime = U (S^2) D (S^2) V^\prime = (US) (SDS) (VS)^\prime$$

is also an SVD of $A$ because $$(US)^\prime(US) = S^\prime U^\prime U S = S^\prime I_p S = S^\prime S = S^2 = I_p$$ demonstrates $US$ has orthonormal columns and a similar calculation demonstrates $VS$ has orthonormal columns. Moreover, since $S$ and $D$ are diagonal, they commute, whence $$S D S = DS^2 = D$$ shows $D$ still has non-negative entries.

The method implemented in the code to find an SVD finds a $U$ that diagonalizes $$AA^\prime = (UDV^\prime)(UDV^\prime)^\prime = UDV^\prime V D^\prime U^\prime = UD^2 U^\prime$$ and, similarly, a $V$ that diagonalizes $$A^\prime A = VD^2V^\prime.$$ It proceeds to compute $D$ in terms of the eigenvalues found in $D^2$. The problem is this does not assure a consistent matching of the columns of $U$ with the columns of $V$.

A Solution

Instead, after finding such a $U$ and such a $V$, use them to compute

$$U^\prime A V = U^\prime (U D V^\prime) V = (U^\prime U) D (V^\prime V) = D$$

directly and efficiently. The diagonal values of this $D$ are not necessarily positive. (That is because there is nothing about the process of diagonalizing either $A^\el primer A$ or $AA^\prime$ that will guarantee that, since those two processes were carried out separately.) Make them positive by choosing the entries along the diagonal of $S$ to equal the signs of the entries of $D$, so that $SD$ has all positive values. Compensate for this by right-multiplying $U$ by $S$:

$$A = U D V^\prime = (US) (SD) V^\prime.$$

That is an SVD.

Example

Let $n=p=k=1$ with $A=(-2)$. An SVD is

$$(-2) = (1)(2)(-1)$$

with $U=(1)$, $D=(2)$, and $V=(-1)$.

If you diagonalize $A^\primer A = (4)$ you would naturally choose $U=(1)$ and $D=(\sqrt{4})=(2)$. Likewise if you diagonalize $AA^\prime=(4)$ you would choose $V=(1)$. Unfortunately, $$UDV^\prime = (1)(2)(1) = (2) \ne A.$$ Instead, compute $$D=U^\prime A V = (1)^\prime (-2) (1) = (-2).$$ Because this is negative, set $S=(-1)$. This adjusts $U$ to $Estados Unidos = (1)(-1)=(-1)$ and $D$ to $SD = (-1)(-2)=(2)$. You have obtained $$A = (-1)(2)(1),$$ que es uno de los dos posibles SVDs (pero no el mismo que el original!).

Código

Aquí es el código modificado. Su salida se confirma

1. El método recrea m correctamente.
2. $U$ $V$ realmente todavía son ortonormales.
3. Pero el resultado no es el mismo de enfermedad vesicular porcina devuelto por svd. (Ambos son igualmente válidas.)

m <- matrix(c(1,0,1,2,1,1,1,0,0),byrow=TRUE,nrow=3)

U <- eigen(tcrossprod(m))$vector
V <- eigen(crossprod(m))$vector
D <- diag(zapsmall(diag(t(U) %*% m %*% V)))
s <- diag(sign(diag(D)))  # Find the signs of the eigenvalues
U <- U %*% s              # Adjust the columns of U
D <- s %*% D              # Fix up D.  (D <- abs(D) would be more efficient.)

U1=svd(m)$u
V1=svd(m)$v
D1=diag(svd(m)$d,n,n)

zapsmall(U1 %*% D1 %*% t(V1)) # SVD
zapsmall(U %*% D %*% t(V))    # Hand-rolled SVD
zapsmall(crossprod(U))        # Check that U is orthonormal
zapsmall(tcrossprod(V))       # Check that V' is orthonormal

Answer 2

Como indiqué en un comentario a @whuber la respuesta de este método para el cálculo de la SVD no funciona para cada matriz. El problema no está limitado a los signos.

El problema es que no se puede repetir autovalores, y en este caso el eigendecomposition de $A'A$ $AA'$ no es único y no todas las opciones de $U$ $V$ puede ser utilizado para recuperar la diagonal factor de la enfermedad vesicular porcina. Por ejemplo, si usted toma cualquier no-diagonal de la matriz ortogonal (es decir, $A=\begin{bmatrix}3/5&4/5\\-4/5&3/5\end{bmatrix}$),$AA'=A'A=I$. Entre todas las opciones posibles para el vector propio de la matriz de $I$, eigen volverá $U=V=I$, por lo tanto, en este caso, $U'AV=A$ no es diagonal.

Intuitivamente, esta es otra manifestación del mismo problema que @whuber contornos, que no tiene que ser un "matching" entre las columnas de a$U$$V$, y de computación, dos eigendecompositions por separado no la aseguran.

Si todos los valores propios de a $A$ son distintos, entonces el eigendecomposition es único (hasta el escalado/signos) y de que el método funciona. Comentario: es que todavía no es una buena idea usar en el código de producción en un equipo con aritmética de punto flotante, ya que cuando se forman los productos de $A'A$ $AA'$ el resultado calculado puede ser perturbado por una cantidad de la orden de $\|A\|^2u$ donde $u \approx 2\times 10^{-16}$ es la precisión de la máquina. Si las magnitudes de los valores singulares de diferir considerablemente (de más de $10^{-8}$, aproximadamente), esto es perjudicial para la precisión numérica de los más pequeños.

El cómputo de la enfermedad vesicular porcina desde los dos eigendecompositions es un gran ejemplo de aprendizaje, pero en la vida real siempre use R svd función para calcular la descomposición de valor singular.