¿Es mejor hacer QR, Cholesky o SVD para resolver la estimación de mínimos cuadrados y por qué?

Answer 1

Asumiendo que [math] X [/ math] es una matriz [[math] m \ times n [/ math]]:

Cholesky es útil si no necesita la matriz de covarianza. Entonces, más rápido que el ingenuo Gauss-Jordan (GJ es de orden [matemática] O (mn ^ 2) [/ matemática], Cholesky es más rápido por un factor de 3). Pero inestable (para matrices casi singulares y deficientes de rango).

QR es más estable que Cholesky (¿no puede manejar la deficiencia de rango?), [Matemáticas] O (mn ^ 2 -n ^ 3/3) [/ matemáticas]. Depende del enfoque particular para calcular la matriz triangular superior (el número de complejidad aquí se calcula usando el enfoque de transformación Householder).

SVD es el más estable, pero el más lento, [matemáticas] O (mn ^ 2 + n ^ 3) [/ matemáticas]. SVD resuelve problemas subdeterminados (deficientes en rango) y sobredeterminados (más datos que ecuaciones) en un sentido de mínimos cuadrados.

Aquí hay una referencia: Página en princeton.edu (Proporciona una estimación de estabilidad en términos de número de condición a la precisión de la máquina)

Y mis notas se basan en recetas numéricas PTVF.

Answer 2

La recomendación estándar para los mínimos cuadrados lineales es usar la factorización QR (¡es un algoritmo muy estable y agradable!) De [math] X [/ math]. La factorización de Cholesky de [matemáticas] X ^ TX [/ matemáticas] es más rápida, pero su uso para el problema de mínimos cuadrados generalmente se desaconseja debido a la afirmación de que “cuadra el número de condición”.

Sin embargo, realmente no compro ese argumento. El condicionamiento del problema lineal de mínimos cuadrados en sí es el número de condición de [math] X ^ TX [/ math] y esta propiedad no se puede cambiar cambiando el algoritmo de factorización. Si el número de condición es tan grande que el algoritmo de factorización es importante, es un signo de un problema casi mal planteado. Para obtener resultados razonables en tales casos, la formulación del problema debe cambiarse, por ejemplo (y esto es muy común) mediante la introducción de la regularización . Una forma de regularizar es usar SVD en [math] X [/ math], monitorear los valores singulares e ignorar los componentes de la solución asociados con los valores singulares pequeños. Una forma más simple, muy estándar y un método que da resultados muy similares, es introducir la regularización de Tichonov; las ecuaciones normales serán típicamente de la forma [matemática] \ epsilon I + X ^ TX [/ matemática]. (Se pueden usar otras opciones que [matemáticas] I [/ matemáticas], dependiendo de los detalles del problema). La factorización de Cholesky es perfectamente adecuada para la matriz regularizada.

Otra opción para la regularización que a veces se promueve es usar el algoritmo de gradiente conjugado en las ecuaciones normales (sin regularización). En muchos casos importantes (es decir, cuando las ecuaciones normales se aproximan a un operador compacto), el algoritmo CG se está regularizando, por lo que el usuario puede monitorear la solución y detenerse antes de que el ruido comience a afectar demasiado la solución.

Answer 3

En estos días, QR parece ser el consenso para la mayoría de los problemas prácticos. SVD es computacionalmente más costoso pero tiene algunas ventajas numéricas, mientras que Cholesky es más barato pero sufre de “condicionamiento al cuadrado” debido al hecho de que tiene que operar en [matemáticas] (X ^ {‘} X) [/ matemáticas], no [matemáticas ] X [/ matemáticas].