Устойчивость сингулярного разложения

[djuuj]

Вычитал в сети, что сингулярное разложение всегда устойчиво к шумам в исходной матрице, даже в вырожденном случае. Почему так?

[Евгений Машеров]

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

[djuuj]

Евгений Машеров в сообщении #960131 писал(а):

Впрочем, что имел в виду автор данного высказывания, я не знаю, может, что-то совершенно иное.

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

[Евгений Машеров]

Ну, возьмём разложение $A=SVD$, где S и D ортогональные, а V - диагональная (прямоугольная) матрицы. И внесём возмущение $A_1=A+\Psi$, где $\Psi$ - малое возмущение.
Тогда $A_1=S(V+S^T\Psi D^T)D$, а ортогональные преобразования квадратичной нормы не меняют. То есть возмущение V порядка элементов $\Psi$
Далее мы можем, например, предаться регрессионному анализу. И обращать будем V (псевдообращать, поскольку она прямоугольная). Если среди элементов V будут близкие по порядку к возмущению, то обратные к ним будут искажены сильно. Но это всё же лучше, чем использовать обычное обращение корреляционной матрицы, поскольку там сильное искажение появится, если возмущения одного порядка с квадратами элементов V (которые являются собственными числами корреляционной матрицы).

[ewert]

Ну если речь о $V$, то никакой анализ вообще не нужен. Сингулярные числа всё-таки суть корни из собственных чисел матрицы $A^*A$, а спектр в любом случае устойчив к малым возмущениям. По тривиальным причинам (например, по принципу аргумента).

[djuuj]

Евгений Машеров в сообщении #960410 писал(а):

Тогда $A_1=S(V+S^T\Psi D^T)D$, а ортогональные преобразования квадратичной нормы не меняют. То есть возмущение V порядка элементов $\Psi$

Но ведь.. $V+S^T\Psi D^T$ не диагональна.. Как она связана с сингулярными числами матрицы $A_1$?

[Евгений Машеров]

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

[Евгений Машеров]

В общем, как справедливо заметил ewert, из того, что задача сингулярного разложения матрицы X эквивалентна задаче разложения по собственным векторам и собственным числам матрицы Грама $X^TX$, следует оценка возмущений сингулярных чисел через оценку возмущений собственных чисел матрицы Грама, а также оценка возмущений входящих в сингулярное разложение ортогональных матриц.
Поэтому хотелось бы уточнить, в каком смысле интересуются "устойчивостью", и что понимается под "шумами в исходной матрице".
Есть, например, задача построения регрессии в условиях мультиколлинеарности и при наличии ошибок вычисления.
Если $X=S\Lambda C$ и $y=Xa+\varepsilon$, то обычная оценка МНК имеет вид $\hat{a}=(X^T)^{-1}X^Ty=C^T\Lambda^{-2}Cy$. Собственные значения матрицы $X^TX$ могут быть весьма малы, порядка ошибок вычисления, и в силу того, что используются обратные им величины, результат окажется лишь игрой этих ошибок. Если расчёт делается через сингулярное разложение, $\hat{a}==C^T\Lambda^{-1}S^Ty$, что в точной арифметике то же самое, то ошибки округления будут того же порядка, но их влияние на $\Lambda$ будет меньшим, чем на $\Lambda^2$, так что ответ будет менее подвержен ошибкам.
Другая задача - если сами значения регрессоров X измерены с (немалой) ошибкой, и надо от неё сперва избавиться. Сингулярное разложение можно использовать и для этого, но другим способом (и используя априорную информацию).

[djuuj]

Евгений Машеров в сообщении #962443 писал(а):

через оценку возмущений собственных чисел матрицы Грама

Можете уточнить какая оценка имеется в виду?

Евгений Машеров в сообщении #962443 писал(а):

Поэтому хотелось бы уточнить, в каком смысле интересуются "устойчивостью", и что понимается под "шумами в исходной матрице".

Ну то, что Вы доказывали в

Евгений Машеров в сообщении #960410 писал(а):

Ну, возьмём разложение $A=SVD$, где S и D ортогональные, а V - диагональная (прямоугольная) матрицы. И внесём возмущение $A_1=A+\Psi$, где $\Psi$ - малое возмущение.
Тогда $A_1=S(V+S^T\Psi D^T)D$, а ортогональные преобразования квадратичной нормы не меняют. То есть возмущение V порядка элементов $\Psi$

но вопрос

djuuj в сообщении #960566 писал(а):

$V+S^T\Psi D^T$ не диагональна.. Как она связана с сингулярными числами матрицы $A_1$?

остался. Приводим её к диагональной и опять приходим к вопросу устойчивости сингулярных чисел.. Только на этот раз диагональной матрицы.

[Евгений Машеров]

Ну, хотя бы через круги Гершгорина можно оценить.

[djuuj]

Евгений Машеров в сообщении #964561 писал(а):

Ну, хотя бы через круги Гершгорина можно оценить.

Как? Пусть $\Phi = S^T\Psi D^T, \tilde V = V+\Phi$. Теорема Гершгорина утверждает, что собственные числа лежат в объединении кругов $D_i$. Возмущение кругов у матрицы $\tilde V^T \tilde V$ порядка $\Phi^T V + V^T\Phi$ но как меняется расположение самих чисел в объединении кругов при возмущениях непонятно.. Может они "перескакивают" из одних кругов в другие?

А вообще, известно же, что устойчивость собственных чисел, в отличие от сингулярных, зависит от числа обусловленности матрицы.

Впрочем, я нашёл нужный результат с доказательством в книге Horn, Johnson "Matrix Analysis", 2nd ed., теорема 7.4.9.1.

[ewert]

djuuj в сообщении #964643 писал(а):

известно же, что устойчивость собственных чисел, в отличие от сингулярных, зависит от числа обусловленности матрицы.

Нэд. От того числа зависит устойчивость решений (ну т.е., при случае, и собственных векторов). Но отнюдь не собственных чисел.

[Евгений Машеров]

Устойчивость собственных чисел может зависеть от коэффициентов перекоса
http://num-anal.srcc.msu.ru/lib_na/int_ae/int_ae5.htm
но не от числа обусловленности.
Однако для симметричных матриц, а задача нахождения сингулярных чисел матрицы A эквивалентна задаче о собственных значениях матрицы $A^TA$ (ну, или $AA^T$) все числа перекоса равны 1.

[djuuj]

Ошибся, невнимательно прочитал в сети. Спасибо за разъяснения.