¿Cuáles deberían ser los criterios para aceptar / rechazar valores singulares?

Estoy resolviendo un sistema usando la descomposición de valores singulares. Los valores singulares (antes de escalar) son:

1.82277e+29
1.95011e+27
1.15033e+23
1.45291e+21
4.79336e+17
7.48116e+15
8.31087e+12
1.71838e+11
5.63232e+08
2.17863e+08
9.02783e+07
1.72345e+07
1.73889e+05
8.09382e+02
2.16644e+00

He descubierto que aceptar todos los valores singulares y su contribución asociada a mi vector de solución produce malos resultados. Los escalo por el número más grande, produciendo valores singulares de:

1.0
1.06986e-02
6.31091e-07
7.97089e-09
2.62971e-12
4.10428e-14
4.55948e-17
9.42732e-19
3.08998e-21
1.19523e-21
4.95281e-22
9.45510e-23
9.53980e-25
4.44040e-27
1.18854e-29

La mejor solución solo comienza a ser mala si incluyo los dos últimos, y solo se vuelve buena alrededor del término . $10^{-19}$

Hay una fuerte caída en la precisión cuando incluyo los últimos 2 términos. ¿Porqué es eso? ¿Cuáles son los criterios para incluir / no incluir valores singulares?

Mi ecuación matricial proviene de un ajuste lineal de mínimos cuadrados donde estoy usando un conjunto de bases polinómicas para ajustar algunos datos ruidosos que creé. Estoy resolviendo el sistema sobredeterminado estándar ( matrix donde ) multiplicando cada lado ( ) por la transposición de ( ) y realizando SVD en eso. $m \times n$ $m \gg n$ $A\cdot X = B$ $A$ $A^\top A X = A^\top X$

Estoy juzgando las respuestas a mis soluciones por lo bien que se aproxima a mis datos ruidosos.

También he notado que, incluso en los ajustes "buenos", no estoy ajustando muy bien cerca de cero (mis datos oscilan entre y ). ¿Porqué es eso? $-10$ $10$

linear-algebra regression svd drjrm3
fuente

Si menciona qué etiquetas le gustaría crear en la publicación o en un comentario, alguien con mayor reputación puede encargarse de eso.

David Z

@DavidKetcheson: No estoy muy seguro si realmente necesitamos estas etiquetas específicas ... todavía. Tal vez cuando tenemos muchas preguntas SVD ... pero creo que el álgebra lineal debería ser una etiqueta suficiente por ahora.

Respuestas:

$\max(m,n) \epsilon \|A\|_2$ $A$ $m \times n$ $\epsilon$ $\|A\|_2$ $A$

Dicho esto, como mencionó JM, es mucho más estable evitar formar : $A^H A$

Primero, necesitamos calcular la descomposición del valor singular luego, podemos definir el pseudoinverso a través de donde

[U, Σ, V] = s v d (A)

$[U,\Sigma,V] = \mathrm{svd}(A)$

A^{†} = V f (Σ) U^{H},

$A^\dagger = V\; f(\Sigma)\; U^H,$

f (σ) = {\begin{cases} 1 / σ, σ \geq max (m, n) ϵ ‖ A ‖_{2}, \\ 0, otherwise \end{cases}

$f(\sigma) = \begin{cases}1/\sigma,\quad\sigma \ge \max(m,n) \epsilon \|A\|_2,\\ 0,\quad\text{otherwise}\end{cases}$

La solución se puede calcular como

X = A^{†} B .

$X = A^\dagger B.$

Jack Poulson
fuente

Creo que es mejor ser explícito y decir que la matriz 2-norma es exactamente la misma que el valor singular más grande ... también, no necesita ser cuadrado para aplicar el criterio de umbral (pero uno reemplaza el con para una matriz ).

A

$\mathbf A$

n

$n$

max (m, n)

$\max(m,n)$

m \times n

$m\times n$

en lugar de A † = U f (Σ) * VH ¿no debería ser A † = V f (Σ) * U '?

drjrm3

Sí, gracias a los dos. Hace unos días escribí una rutina pseudoinversa paralela para matrices hermitianas, y aparentemente no pensé lo suficiente en las diferencias relativas al caso general.

Jack Poulson

Las pseudoinversiones no son una cura para problemas mal condicionados, aunque tienden a ayudar. La interpolación polinómica de alto orden está notoriamente mal acondicionada y es mejor evitarla. Le recomiendo que lea el artículo de Wiki sobre el fenómeno de Runge y luego cambie a una base diferente para su interpolación (por ejemplo, polinomios por partes o splines).

Jack Poulson

Esta discusión ya no está relacionada con su pregunta original; si su implementación de una aproximación de mínimos cuadrados cuestionable converge no es relevante para su pregunta original. Le sugiero que publique otra pregunta si todavía está confundido.

Jack Poulson

Augh !! ¡No, no , mil veces, no !

¡La razón por la que las personas usan SVD es precisamente para evitar tener que formar la matriz de productos cruzados , ya que la formación de esta matriz es una buena receta para formar sistemas lineales mal condicionados! La descomposición está destinado a ser aplicado directamente a . (Ver también algunas de mis respuestas anteriores ). $\mathbf A^\top\mathbf A$ $\mathbf A$

Les he mencionado antes que el criterio habitual para poner a cero los valores singulares es compararlos con el producto del valor singular más grande y la máquina épsilon. Sin embargo, esto se vuelve discutible por su formación de la matriz de productos cruzados. Intente ejecutar la descomposición nuevamente, pero esta vez, en la matriz de diseño en lugar de la matriz de productos cruzados. Cualquier otra forma es el abuso flagrante de la descomposición.

JM
fuente

No puedo votar esto lo suficiente ... este es el punto más importante sobre el uso correcto de las técnicas SVD. ¡Recuerde que los valores singulares de son los cuadrados de los valores singulares de !

A^{T} A

$A^T A$

A

$A$

khinsen

Precisamente. Cuadrar un número pequeño da como resultado un número aún más pequeño. Teniendo en cuenta el hecho de que el número de condición de 2 normas es la relación del valor singular más grande al más pequeño, esta es una forma de ver por qué el enfoque de ecuaciones normales puede ser una mala idea para sistemas grandes.

Creo que varias personas aquí han proporcionado valiosos consejos para su problema.

Sin embargo, para referencia futura, su pregunta sobre cómo resolver un problema de mínimos cuadrados lineales mal planteados podría responderse mirando el inmenso cuerpo de literatura sobre este problema.

Específicamente, podría usar la TSVD (Descomposición de valor singular truncado) como un método simple para obtener la solución: donde es el i-ésimo valor singular, y son la ésima columna en las matrices y de la factorización , es el lado derecho de su problema, y la notación significa el complejo conjugado de las entradas y luego se convirtió en una fila vector, de modo que

x_{k} = \sum_{i = 1}^{k} \frac{u_{i}^{H} b}{σ_{i}} v_{i}

$\mathbf{x}_k = \sum_{i=1}^{k} \frac{\mathbf{u}_i^H \mathbf{b}}{\sigma_i}\mathbf{v}_i$

σ_{i}

$\sigma_i$

u_{i}

$\mathbf{u}_i$

v_{i}

$\mathbf{v}_i$

U

$U$

V

$V$

U S V^{H} = A

$USV^H=A$

b

$\mathbf{b}$

u^{H}

$\mathbf{u}^H$

u^{H} b

$\mathbf{u}^H \mathbf{b}$ produce un escalar (producto de punto). Su solución es, por lo tanto, el vector .

x_{k}

$\mathbf{x}_k$

El principal problema en esta configuración, además de verse obligado a calcular el SVD que es bastante costoso, es cómo elegir el número de valores singulares que se utilizarán, es decir, . Una vez más, hay varias maneras de hacerlo, pero las más populares serían el principio de discrepancia, el método de validación cruzada generalizada y la curva en L. $k$

Todo esto (y mucho más) se implementa, en Matlab, en la excelente caja de herramientas Herramientas de regularización , escrita por el profesor Per Christian Hansen, quien también ha publicado varios artículos y algunos libros sobre problemas inversos. La caja de herramientas es fácil de usar y debería ser bastante fácil de traducir a otros lenguajes de programación.

En conclusión, mientras que otros han proporcionado información importante sobre su aplicación que sugiere que otros enfoques son más apropiados, lo anterior es un resumen rápido sobre cómo podría resolver el problema si aún lo necesita.

OscarB
fuente

gracias, soy consciente de la mayoría de esto. He buscado muchos recursos; el problema es que mis soluciones empeoran cada vez más a medida que crezco mi conjunto de bases que se utiliza. He llegado a la conclusión de que esto se debe a que el número de valores singulares que se rechazan a medida que aumenta mi conjunto base aumenta en relación con el número de funciones básicas que se utilizan. es decir, cuando utilicé n = 100 funciones básicas, debo arrojar 95 de los valores singulares y esto arroja un resultado peor que si utilizo 10 conjuntos básicos y solo arrojo un valor singular.

drjrm3

Correcto, bueno, como han sugerido otros, debe mirar sus funciones básicas y quizás encontrar una base que se aproxime mejor a sus datos. Splines podría ser una opción. Kriging también podría hacerlo, aunque ese es un enfoque completamente diferente, que me ha dado buenos resultados en varias ocasiones.

OscarB