Cholesky para matrices definidas no positivas

Question

Estoy tratando de aproximar una matriz NPD con la forma PD más cercana y calcular su descomposición Cholesky.

Sé que el método habitual es realizar una descomposición de valores propios, eliminar los valores propios negativos y volver a calcular la descomposición de valores propios. Sin embargo, no quiero hacer ninguna descomposición de valores propios, y quiero tratar este tema dentro del algoritmo de Cholesky.

Para aquellos que estén familiarizados con el algoritmo Cholesky, hay un paso en el que se calcula la diagonal de la matriz diagonal inferior como la raíz cuadrada de un valor (digamos x). Si x<0 entonces, esto significa que la matriz es NPD.

Una forma sencilla de solucionar esto podría ser poner x = 0 o x = 10^-10, sólo para sortear este problema. Sin embargo, carece de rigor matemático.

Mi pregunta es, ¿alguno de ustedes ha escuchado un método de este tipo, o algo similar al método anterior, que esté publicado o algo probado?

Gracias.

Answer 1

Deberías precisar un poco más lo que entiendes por NPD. Mi opinión es: una matriz simétrica/hermitiana (por tanto, indefinida).

Existe una factorización de Cholesky para los positivos semi matrices definidas en un artículo de N.J.Higham, " Análisis de la descomposición Cholesky de una matriz semidefinida ". No conozco ninguna variante que funcione con matrices indefinidas y que encuentre la matriz (semi)definida positiva más cercana, pero lee este artículo y ve si puedes resolver algo.

También podría interesarle la descomposición indefinida simétrica de Bunch-Parlett descrita en su documento clásico " Métodos directos para resolver sistemas indefinidos simétricos de ecuaciones lineales ".

Hasta donde yo sé, las aproximaciones más cercanas como ésta han salido a la luz hace relativamente poco tiempo y hay problemas menos exigentes que aún no están resueltos, así que dudo que encuentres algo ya hecho para lo que te interesa.

Editar

Por supuesto, si se utiliza la descomposición de valores propios, se puede obtener la matriz semidefinida más cercana. Sin embargo, ten en cuenta que no es necesario multiplicar los factores obtenidos. Digamos que tienes $A = U \Lambda U^T$ , donde $U$ es ortogonal y $\Lambda$ es diagonal. Obtenga un valor no negativo $\Lambda'$ sustituyendo los elementos negativos en $\Lambda$ por cero y obtener la aproximación semidefinida más cercana de $A$ : $A' = U \Lambda' U^T$ .

Ahora, toma QR de $(U\sqrt{\Lambda'})^T$ . De este modo, se obtendrá un $Q$ y el triángulo superior $R$ tal que $QR = (U\sqrt{\Lambda'})^T$ . Ahora, lo tienes: $$A' = (U\sqrt{\Lambda'}) (U\sqrt{\Lambda'})^T = (QR)^T (QR) = R^T R,$$ que es una descomposición Cholesky(-como) que quieres.

No sé por qué quieres evitar la descomposición de valores propios. Esto parece bastante limpio para mí.