Número de condición de formulaciones A'A y AA '

9

Se muestra (Yousef Saad, Métodos iterativos para sistemas lineales dispersos , p. 260) que $cond(A'A) \approx cond(A)^2$

¿Es esto cierto también para $AA'$ ?

En caso de que $A$ sea $N\times M$ con $N \ll M$ , observo que $cond(A'A) \gg cond(AA')$

¿Eso significa que la formulación en términos de $AA'$ es preferible en este caso?

linear-algebra condition-number Alejandro
fuente

2

Estás comparando números de condición de dos matrices con tamaños muy diferentes. Sin una explicación de por qué, parece que esa comparación probablemente no sea significativa. Ciertamente, si puede lograr lo que necesita usando una matriz mucho más pequeña, debería (incluso si el acondicionamiento fuera similar).

David Ketcheson el

1

La nueva respuesta de Stefano M a continuación es correcta. Léalo y vote.

David Ketcheson

6

Si con , entonces para que no puede ser rango completo, es decir, es singular. $A\in\mathbb{R}^{N\times M}$ $N<M$

r a n k (A^{T} A) = r a n k (A A^{T}) = r a n k (A) \leq N < M

$\mathop{\mathrm{rank}}(A^TA) = \mathop{\mathrm{rank}}(AA^T) = \mathop{\mathrm{rank}}(A) \leq N < M$

A^{T} A \in R^{M \times M}

$A^TA \in \mathbb{R}^{M\times M}$

En consecuencia, el número de condición es . Debido a la aritmética de precisión finita, si calcula en matlab obtiene un gran número, no . $\kappa_2(A^TA)=\infty$ cond(A'A)Inf

Stefano M
fuente

@OscarB: los valores singulares de

son solo

, ¡no existe el

valor singular! Su derivación es correcta, pero tenga en cuenta que si

,

son los sv de

, entonces

, mientras que

A

$A$

N

$N$

M

$M$

σ_{i}

$\sigma_i$

i = 1 \dots N

$i=1\dots N$

A

$A$

S S^{T} = d i a g (σ_{1}^{2}, \dots, σ_{n}^{2})

$SS^T=\mathop{\mathrm{diag}}(\sigma_1^2,\dots,\sigma_n^2)$

con

ceros al final.

S^{T} S = d i a g (σ_{1}^{2}, \dots, σ_{n}^{2}, 0, \dots, 0)

$S^TS = \mathop{\mathrm{diag}}(\sigma_1^2,\dots,\sigma_n^2, 0, \dots, 0)$

M - N

$M-N$

Stefano M

8

$A^TA$ $A$ $A=USV^T$ $U \in \mathbb{R}^{N \times N}$ $S \in \mathbb{R}^{N \times M}$ $V \in \mathbb{R}^{M \times M}$ $A^T A$

$A^T A=(USV^T)^T USV^T=VS^T U^T U S V^T=V S^T S V^T$

$U$ $U^T U=I$ $S$ $A^TA$ $V S^2 V^T$ $S^2$ $S^T S$ $S$ $cond(A)=\frac{s_1}{s_N}$ $A \in \mathbb{R}^{N \times M}$

$cond(A^T A)=\frac{s_1^2}{s_M^2}=(\frac{s_1}{s_M})^2=cond(A)^2$

$AA^T$

$AA^T=USV^T (USV^T)^T=USV^T V S^T U^T=U S^2 U^T$

$cond(AA^T)=\frac{s_1^2}{s_N^2}$ $S^2$ $SS^T$

$A^TA$ $AA^T$ $AA^T$ $A^TA$

$A^TA$ $AA^T$

OscarB
fuente

A A^{'}

$AA'$

A^{'} A

$A'A$

Me alegro de que tuviera sentido. En general, debe considerar el condicionamiento del problema. Pero, si eso no es un problema, puede usar ecuaciones normales / factorización QR (de A) / LSQR, dependiendo del tamaño del problema (entre otras cosas). A menos que su problema sea grande o esté mal condicionado, probablemente aplicaría la factorización QR, pero sin más conocimiento del problema que está tratando de resolver, es difícil saberlo. Estoy seguro de que otras personas con más experiencia podrían proporcionar consejos más detallados.

OscarB

\approx 10^{7}

$\approx 10^7$

c o n d (A) < c o n d (A A^{T}) < c o n d (A^{T} A)

$cond(A) < cond(AA^T) < cond(A^T A)$

N < M

$N < M$ ), parece preferible utilizar LSQR, ya que no es necesario que forme ningún producto. La pregunta es si las soluciones obtenidas con ecuaciones normales y LSQR son idénticas.

Alexander

Bueno, según tengo entendido, LSQR proporcionará una solución idéntica a las ecuaciones normales después de "infinitas" iteraciones con precisión exacta. Sin embargo, para problemas mal planteados, la solución de ecuaciones normales no es la que desea. En su lugar, desea utilizar LSQR para iterar hasta que se logre la semiconvergencia. Sin embargo, controlar algoritmos iterativos en problemas mal planteados es un juego de pelota completamente diferente. Además, dependiendo del costo de su producto matriz-vector y el número de iteraciones (y, por lo tanto, matvecs) necesarias, una solución directa de tikhonov con bidiagonalización podría ser mejor.

OscarB

Impresionante explicación. +1 para usted señor!

meawoppl

2

$\DeclareMathOperator{\cond}{cond} \cond A^2 \approx \cond A^T A$

A = (\begin{matrix} ϵ & 1 \\ 0 & ϵ \end{matrix}), ϵ ≪ 1

$\newcommand\bigO{\mathcal{O}}A = \begin{pmatrix} \epsilon & 1 \\ 0 & \epsilon \end{pmatrix}, \quad \epsilon \ll 1$

para lo cual puede verificar fácilmente que mientras que . $\cond A^T A = \bigO(\epsilon^{-4})$ $\cond A^2 = \bigO(\epsilon^{-2})$

Jed Brown
fuente

Bien, para enfatizar que y son en general muy diferentes en cuanto a eigs, svds, cond number: pero en mi opinión, la afirmación de la pregunta es sobre .

A^{2}

$A^2$

A^{T} A

$A^T A$

[c o n d (A)]^{2}

$[\mathrm{cond}(A)]^2$

Stefano M

@StefanoM Gracias, parece que leí mal, aunque de la discusión, no fue el único.

Jed Brown

1

En aritmética exacta cond (A ^ 2) = cond (A'A) = cond (AA '), ver por ejemplo. Golub y van Loan, 3a ed., P70. Esto no es cierto en la aritmética de coma flotante si A es casi deficiente en rango. El mejor consejo es seguir las recetas de libros anteriores al resolver problemas de mínimos cuadrados, siendo el enfoque SVD más seguro, p257. Use \ varepsilon-rank en su lugar cuando calcule SVD, donde \ varepsilon es la resolución de sus datos de matriz.

Artan
fuente

Lo siento, miré a Golub y Van Loan 3rd ed p. 70, y no pude encontrar nada que respalde la declaración cond (A ^ 2) = cond (A ^ TA) = cond (AA ^ T). ¿Podría ser más específico con su referencia?

OscarB

No hay ninguna declaración allí, pero puede derivar del teorema 2.5.2 y el pseudoinverso, sección 5.5.4, que cond (AA ') = cond (A'A). La razón por la que tomo pseudoinverso es que esto es lo que importa para el problema de mínimos cuadrados en la mano. La igualdad después de cond (A ^ 2) debería ser \ aprox, perdón por el error tipográfico.

Artan

No, esta respuesta es totalmente incorrecta. Ver mi contraejemplo.

Jed Brown

Saad debe haber hecho tal punto en algún contexto específico. Lo relevante para la pregunta en cuestión es el argumento del procedimiento.

Artan

Número de condición de formulaciones A'A y AA '

Respuestas: