Número de condição das formulações A'A e AA '

9

É mostrado (Yousef Saad, métodos iterativos para sistemas lineares esparsos , p. 260) que $cond(A'A) \approx cond(A)^2$

Isso também é verdade para ? $AA'$

No caso de ser com , observo que $A$ $N\times M$ $N \ll M$ $cond(A'A) \gg cond(AA')$

Isso significa que a formulação em termos de é preferível neste caso? $AA'$

linear-algebra condition-number Alexander
fonte

2

Você está comparando números de condição de duas matrizes com tamanhos muito diferentes. Sem uma explicação do porquê, parece que essa comparação provavelmente não é significativa. Certamente, se você pode conseguir o que precisa usando uma matriz muito menor, deve fazê-lo (mesmo que o condicionamento seja semelhante).

precisa saber é o seguinte

11

A nova resposta de Stefano M abaixo está correta. Por favor, leia e vote.

David Ketcheson

6

Se com , então modo que não pode ser posto completo, ie é 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}$

Consequentemente, o número da condição é . Devido à aritmética de precisão finita, se você computa no matlab, obtém um grande número, não . $\kappa_2(A^TA)=\infty$ cond(A'A)Inf

Stefano M
fonte

@OscarB: os valores singulares de

são apenas

, não existe o valor

singular! Sua derivação está correta, mas observe que se

,

são os sv's de

, então

, enquanto

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)$

com

zeros à direita.

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$

276 Stefano M

8

Bem, Vamos olhar por tem aproximadamente o número de condição quadrado de . Usando a decomposição SVD de , com , , , podemos expressar como $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$

Que chegamos ao notar que é orthonormal, tal que . Além disso, observamos que é uma matriz diagonal, de modo que a decomposição final de pode ser expressa como , com significando , produzindo uma matriz diagonal com os primeiros N valores singulares de ao quadrado na diagonal. Isto significa que uma vez que o número de condição é a razão entre o primeiro e o último valor singular, $U$ $U^T U=I$ $S$ $A^TA$ $V S^2 V^T$ $S^2$ $S^T S$ $S$ para, $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$

Agora, podemos realizar o mesmo exercício com : $AA^T$

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

O que significa que obtemos o resultado , uma vez queaqui significa, uma diferença subtil da notação acima. $cond(AA^T)=\frac{s_1^2}{s_N^2}$ $S^2$ $SS^T$

Mas observe essa diferença sutil! Para , o número da condição possui o M-ésimo valor singular no denominador, enquanto tem o N-ésimo valor singular. Isso explica por que você está vendo diferenças significativas no número de condição - vai realmente ser “melhor condicionado” de . $A^TA$ $AA^T$ $AA^T$ $A^TA$

Ainda assim, David Ketcheson estava correto - você está comparando números de condição entre duas matrizes muito diferentes. Em particular, o que você pode realizar com não será o mesmo que o que você pode realizar com . $A^TA$ $AA^T$

OscarB
fonte

Essa é uma ótima explicação! Eu vejo a diferença claramente agora. Matriz A é usado para construir equações normais e com ligeiras alterações, você também pode formulá-la como

, não clássica

. Você pode dizer também se é vantajoso usar o solucionador como LSQR em vez de resolver equações normais? Como o LSQR não requer a construção deste produto.

A A^{'}

$AA'$

A^{'} A

$A'A$

Alexander

Ainda bem que fazia sentido. Em geral, você precisa considerar o condicionamento do problema. Mas, se isso não for um problema, você poderá usar as equações normais / fatoração QR (de A) / LSQR, dependendo do tamanho do problema (entre outras coisas). A menos que seu problema seja grande ou mal condicionado, provavelmente aplicaria a fatoração QR, mas sem mais conhecimento do problema que você está tentando resolver, é difícil dizer. Estou certo de que outras pessoas com mais experiência poderiam fornecer conselhos mais detalhados.

OscarB

O A em si está mal condicionado (com número de condição de

), denso e grande. QR não é uma opção. Como está mal condicionado, tenho que adicionar alguma regularização de qualquer maneira. Agora, a simples regularização de Tikhonov parece ser suficiente. A questão é que se

(para o meu caso com

\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$ ), o uso do LSQR parece sempre preferível, pois você não precisa formar nenhum produto. A questão é se as soluções obtidas com equações normais e LSQR são idênticas?

Alexander

Bem, pelo que entendi, o LSQR fornecerá uma solução idêntica às equações normais após "infinitamente muitas" iterações com precisão exata. No entanto, para problemas incorretos, a solução de equações normais não é a que você deseja. Em vez disso, você deseja usar o LSQR para iterar até que a semi convergência seja alcançada. No entanto, controlar algoritmos iterativos em problemas incorretos é outro jogo de bola. Além disso, dependendo do custo do seu produto vetor de matriz e do número de iterações (e, portanto, do matvecs) necessárias, uma solução tikhonov direta com bidiagonalização pode ser melhor.

OscarB

Explicação impressionante. +1 para você, senhor!

precisa saber é

2

A afirmação que (para matrizes quadradas) ~~na pergunta e~~ [Edit: eu interpretei errado] na resposta de Artan é um absurdo. Contra-exemplo $\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 o qual você pode facilmente verificar que enquanto . $\cond A^T A = \bigO(\epsilon^{-4})$ $\cond A^2 = \bigO(\epsilon^{-2})$

Jed Brown
fonte

Ok ressaltar que

e

são, em geral, muito diferente como o que diz respeito eigs, SVD, número cond: mas na minha opinião a alegação da pergunta é sobre

.

A^{2}

$A^2$

A^{T} A

$A^T A$

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

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

24512 Stefano M

@StefanoM Obrigado, parece que eu li errado, embora a partir da discussão, não fosse o único.

Jed Brown

1

Em condições aritméticas exatas (A ^ 2) = cond (A'A) = cond (AA '), ver p. Golub e van Loan, 3ª ed., P. Isso não é verdade na aritmética de ponto flutuante se A for quase deficiente na classificação. O melhor conselho é seguir as receitas do livro acima ao resolver problemas com mínimos quadrados, sendo a abordagem mais segura a SVD, p257. Use \ varepsilon-rank ao calcular SVD, onde \ varepsilon é a resolução dos dados da matriz.

Artan
fonte

Sinto muito, olhei para Golub e Van Loan, 3ª ed p. 70, e não conseguiu encontrar nada que faça backup da instrução cond (A ^ 2) = cond (A ^ TA) = cond (AA ^ T). Você poderia ser mais específico com sua referência?

OscarB

Não há nenhuma declaração lá, mas você pode derivar do teorema 2.5.2 e do pseudo-inverso, seção 5.5.4 que cond (AA ') = cond (A'A). A razão pela qual considero pseudo-inverso é que é isso que importa para o problema dos mínimos quadrados em questão. A igualdade após cond (A ^ 2) deve ser \ aproximadamente, desculpe pelo erro de digitação.

Artan

Não, esta resposta está totalmente incorreta. Veja meu contra-exemplo.

precisa

Saad deve ter afirmado isso em algum contexto específico. O que é relevante para a questão em questão é o argumento do processo.

25412 Artan

Número de condição das formulações A'A e AA '

Respostas: