Relación entre Cholesky y de enfermedad vesicular porcina

Question

Cuando tenemos una matriz simétrica $A = LL^*$, podemos obtener L el uso de Cholesky de la descomposición de $A$ ($L^*$ es $L$ transpuesto).

¿Alguien puede decirme cómo podemos conseguir el mismo $L$ usando SVD o Eigen descomposición?

Gracias.

Answer 1

No estoy seguro de por qué alguien querría obtener una descomposición de Cholesky de una enfermedad vesicular porcina o un eigen-descomposición, pero de todos modos, vamos a decir $A$ es positiva definida:

• Como $A$ es positiva definida, si $A=U\Sigma V^\ast$ es un SVD de a $A$, debemos tener $U=V$ (ejercicio). Realizar una descomposición QR para $\sqrt{\Sigma}U^\ast$, es decir, escribir $\sqrt{\Sigma}U^\ast=QR$ para algunos unitario de la matriz $Q$ y algunos triangular superior de la matriz $R$. A continuación, $A=R^\ast R$ es una descomposición de Cholesky de a $A$.
• Si $A=PDP^{-1}$ es un eigendecomposition de $A$, realizar una descomposición QR o Gram-Schmidt orthogonalization para cada grupo de columnas de a $P$ que corresponden a un mismo autovalor. Por lo tanto, podemos obtener un conjunto de vectores propios ortonormales de $A$, es decir, tenemos algunos unitario de la matriz $U$ tal que $A=UDU^\ast$. Así que podemos aplicar el método anterior para obtener una descomposición de Cholesky $A=R^\ast R$.

Answer 2

Varias personas en este hilo se le preguntó por qué usted quiere hacer Cholesky, en un no-positivo-definida la matriz. He pensado que me gustaría mencionar un caso que motive a esta pregunta.

La descomposición de Cholesky es utilizado para generar aleatoria Gaussiana variantes dada una matriz de covarianza usando $x_i = \sum_j L_{ij} z_j$ donde cada una de las $z_j ~ Normal(0,1)$ $L$ es la descomposición de Cholesky de la matriz de covarianza.

Un problema surge cuando la matriz de covarianza de generar, cuando la variación aleatoria descrita por la covarianza contenida en un menor espacio tridimensional. Uno o más de los Valores propios es cero, la matriz no es positiva definida, las llamadas a la descomposición de Cholesky, rutinas de error. Cuando usted está cerca de este caso, las cosas tienden a ser extremadamente sensibles a los numéricos de redondeo (es decir, la covarianza es mal condicionado).

No debería haber ningún problema inherente con la generación de puntos en este "plano" de Gauss, pero el libro de texto basado en algoritmo de Cholesky se rompe.

Eigen la descomposición puede ser utilizado como una alternativa para este problema, si usted tiene una robusta implementación. Algunos Eigen de la descomposición de los algoritmos de no hacer bien en este caso, pero hay Eigen algoritmos que son robustos.

Answer 3

Hay una relación interesante entre los eigen-descomposición de una matriz simétrica y su factor de Cholesky: Decir $A = L L'$ $L$ el factor de Cholesky, y $A = E D E'$ el eigen-decompostion. A continuación, el eigen-decompostion de $L$$L= E D^{\frac{1}{2}} F$, $F$ algunos ortogonal de la matriz, es decir, el factor de Cholesky es una rotación del módulo de la matriz de vectores propios escala por la diagonal de la matriz de square-raíz eigen-valores. Así que usted puede conseguir $L$ $E D^{\frac{1}{2}}$ a través de una serie de rotaciones ortogonales destinada a hacer que los elementos por encima de la diagonal zero.

Answer 4

o puede usar la descomposición LU.

De todos modos, usted normalmente no calcular la descomposición de cholesky de la eigendecomposition o de enfermedad vesicular porcina - que el uso de eliminación gaussiana. Ver algo como la Matriz de Cálculos.

Answer 5

Siempre se puede aplicar SVD (a es Positiva Definida), da $$A = \sum \lambda_i v_i v_i^T$$ donde $v_i$ es una unidad autovector. Esto es debido a que a es simétrica.

Si usted toma $x_i = \sqrt{\lambda_i}v_i$, ($\lambda_i >0$ como es PD). A continuación, tome $X = [x_i]$, es decir, cada columna de $X$ es uno de los $x_i$. A continuación, $$A = \sum x_i x_i^T = X X^T $$

(Para demostrar que la $\sum x_i x_i^T = X X^T$, el uso de la cuadra de la multiplicación de la propiedad, con cada una de las $x_i$ tratado como un bloque)

En la práctica, es probablemente más rápido el uso de Eliminación Gaussiana.