Номер условия составов A'A и AA '

9

Показано (Юсеф Саад, Итерационные методы для разреженных линейных систем , стр. 260), что $cond(A'A) \approx cond(A)^2$

Это правда и для ? $AA'$

В случае , если является с , заметим , что я $A$ $N\times M$ $N \ll M$ $cond(A'A) \gg cond(AA')$

Означает ли это, что формулировка в терминах предпочтительнее в этом случае? $AA'$

linear-algebra condition-number Александр
источник

2

Вы сравниваете номера условий двух матриц с очень разными размерами. Без объяснения причин кажется, что сравнение, вероятно, не имеет смысла. Конечно, если вы можете выполнить то, что вам нужно, используя гораздо меньшую матрицу, вы должны это сделать (даже если условия были схожими).

Дэвид Кетчесон

1

Новый ответ Стефано М ниже верен. Пожалуйста, прочитайте и проголосуйте.

Дэвид Кетчон

6

Если с , то , так что не может быть полный ранг, т.е. единственном числе. $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}$

Соответственно, номер условия . Из-за арифметики конечной точности, если вы вычисляете в Matlab, вы получите большое число, а не . $\kappa_2(A^TA)=\infty$ cond(A'A)Inf

Стефано М
источник

@OscarB: сингулярные значения - это просто , нет такого понятия, как е сингулярное значение! Ваш вывод правильный, но, пожалуйста, обратите внимание, что если , являются sv для , то , в то время как с конечными нулями .

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

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$

Стефано М

8

Ну, взгляд давайте, почему имеет приблизительно квадрат числа обусловленности . Используя SVD-разложение , с , , , мы можем выразить как $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$

Что мы приходим, отметив , что ортонормальна, так что . Далее отметим, что является диагональной матрицей, так что окончательное разложение может быть выражено как , где означает , что дает диагональную матрицу с первыми N единичными значениями из квадрате по диагонали. Это означает, что, поскольку число условий является отношением первого и последнего единственного значения, для , $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$

Но обратите внимание на эту тонкую разницу! Для номер условия имеет M-е единственное значение в знаменателе, в то время как имеет N-е единственное значение. Это объясняет, почему вы видите значительные различия в числе условий - действительно будет «лучше подготовлен», чем . $A^TA$ $AA^T$ $AA^T$ $A^TA$

Тем не менее, Дэвид Кетчес был прав: вы сравниваете числа условий между двумя совершенно разными матрицами. В частности, то , что вы можете достичь с не будет таким же , как то , что вы можете сделать с . $A^TA$ $AA^T$

OscarB
источник

Это отличное объяснение! Теперь я ясно вижу разницу. Матрица A используется для построения нормальных уравнений, и с небольшими изменениями вы также можете сформулировать ее как , а не как классическую . Можете ли вы также сказать, выгодно ли использовать решатель типа LSQR вместо решения нормальных уравнений? Поскольку LSQR не требует создания этого продукта вообще.

A A^{'}

$AA'$

A^{'} A

$A'A$

Александр

Рад, что это имело смысл. В общем, вам необходимо учитывать обусловленность проблемы. Но, если это не проблема, вы можете использовать либо нормальные уравнения / QR-факторизацию (из A) / LSQR, в зависимости от размера проблемы (среди прочего). Если ваша проблема не является большой или плохо обусловленной, я бы, вероятно, применил QR-факторизацию, но без дополнительных знаний о проблеме, которую вы пытаетесь решить, трудно сказать. Я уверен, что другие с большим опытом могли бы дать более подробный совет.

OscarB

Само А плохо обусловлено (с условным числом

\approx 10^{7}

$\approx 10^7$ ), плотный и большой. QR не вариант. Так как это плохо обусловлено, я все равно должен добавить некоторую регуляризацию. Теперь простой тихоновской регуляризации кажется достаточно. Дело в том, что если

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$ ) тогда использование LSQR представляется предпочтительным, поскольку вам вообще не нужно создавать какой-либо продукт. Вопрос в том, совпадают ли решения, полученные с помощью нормальных уравнений и LSQR?

Александр

Ну, насколько я понимаю, LSQR обеспечит идентичное решение для нормальных уравнений после «бесконечного числа» итераций с точной точностью. Однако для некорректных задач решение нормальных уравнений не то, которое вам нужно. Вместо этого вы хотите использовать LSQR для итерации, пока не будет достигнута полусходимость. Однако управление итерационными алгоритмами в некорректных задачах - это совсем другая игра с мячом. Кроме того, в зависимости от стоимости вашего матрично-векторного произведения и количества необходимых итераций (и, следовательно, матвек), прямое решение Тихонова с бидиагонализацией может быть лучше.

OscarB

Потрясающее объяснение. +1 для вас, сэр!

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$

для которого вы можете легко проверить, что $\cond A^T A = \bigO(\epsilon^{-4})$ пока $\cond A^2 = \bigO(\epsilon^{-2})$ ,

Джед браун
источник

Хорошо, чтобы подчеркнуть, что

A^{2}

$A^2$ а также

A^{T} A

$A^T A$ в целом очень отличаются от того, что касается eigs, svds, cond number: но, на мой взгляд, вопрос о

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

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

Стефано М

@ StefanoM Спасибо, кажется, я неправильно прочитал, хотя из обсуждения, не был единственным.

Джед Браун

1

В точной арифметике cond (A ^ 2) = cond (A'A) = cond (AA '), см., Например. Голуб и Ван Лоан, 3-е изд., Стр. 70. Это не верно в арифметике с плавающей запятой, если A почти не имеет ранга. Лучший совет - следовать вышеприведенным рецептам книг при решении задач наименьших квадратов, самым безопасным из которых является метод SVD, стр. 257. Вместо этого используйте \ varepsilon-rank при вычислении SVD, где \ varepsilon - это разрешение ваших данных матрицы.

Артан
источник

Извините, я посмотрел на Голуба и Ван Лоан 3-е изд. 70, и не смог найти ничего, подтверждающего утверждение cond (A ^ 2) = cond (A ^ TA) = cond (AA ^ T). Не могли бы вы быть более конкретным с вашей ссылкой?

OscarB

Там нет никакого утверждения, но вы можете вывести из теоремы 2.5.2 и псевдообратного, раздел 5.5.4, что cond (AA ') = cond (A'A). Причина, по которой я выбираю псевдообратное, состоит в том, что именно это имеет значение для решения проблемы наименьших квадратов. Равенство после cond (A ^ 2) должно быть \ прибл., Извините за опечатку.

Артан

Нет, этот ответ совершенно неверный. Смотрите мой контрпример.

Джед Браун

Саад, должно быть, высказал такую точку зрения в каком-то конкретном контексте. Что касается рассматриваемого вопроса, это исходящий аргумент.

Артан

Номер условия составов A'A и AA '

Ответы: