2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Устойчивость сингулярного разложения
Сообщение11.01.2015, 07:22 
Вычитал в сети, что сингулярное разложение всегда устойчиво к шумам в исходной матрице, даже в вырожденном случае. Почему так?

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

 
 
 
 Re: Устойчивость сингулярного разложения
Сообщение11.01.2015, 22:34 
Евгений Машеров в сообщении #960131 писал(а):
Впрочем, что имел в виду автор данного высказывания, я не знаю, может, что-то совершенно иное.

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

 
 
 
 Re: Устойчивость сингулярного разложения
Сообщение12.01.2015, 09:43 
Аватара пользователя
Ну, возьмём разложение $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 (которые являются собственными числами корреляционной матрицы).

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

 
 
 
 Re: Устойчивость сингулярного разложения
Сообщение12.01.2015, 15:39 
Евгений Машеров в сообщении #960410 писал(а):
Тогда $A_1=S(V+S^T\Psi D^T)D$, а ортогональные преобразования квадратичной нормы не меняют. То есть возмущение V порядка элементов $\Psi$

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

 
 
 
 Re: Устойчивость сингулярного разложения
Сообщение15.01.2015, 10:33 
Аватара пользователя
Приводим к диагональной и видим, что возмущения сингулярных чисел того же порядка, что внедиагональные элементы матрицы.

 
 
 
 Re: Устойчивость сингулярного разложения
Сообщение15.01.2015, 11:35 
Аватара пользователя
В общем, как справедливо заметил 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 измерены с (немалой) ошибкой, и надо от неё сперва избавиться. Сингулярное разложение можно использовать и для этого, но другим способом (и используя априорную информацию).

 
 
 
 Re: Устойчивость сингулярного разложения
Сообщение18.01.2015, 22:29 
Евгений Машеров в сообщении #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$?

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

 
 
 
 Re: Устойчивость сингулярного разложения
Сообщение18.01.2015, 23:07 
Аватара пользователя
Ну, хотя бы через круги Гершгорина можно оценить.

 
 
 
 Re: Устойчивость сингулярного разложения
Сообщение19.01.2015, 03:49 
Евгений Машеров в сообщении #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.

 
 
 
 Re: Устойчивость сингулярного разложения
Сообщение19.01.2015, 21:41 
djuuj в сообщении #964643 писал(а):
известно же, что устойчивость собственных чисел, в отличие от сингулярных, зависит от числа обусловленности матрицы.

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

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

 
 
 
 Re: Устойчивость сингулярного разложения
Сообщение19.01.2015, 22:27 
Ошибся, невнимательно прочитал в сети. Спасибо за разъяснения.

 
 
 [ Сообщений: 14 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group