2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Устойчивость сингулярного разложения
Сообщение11.01.2015, 07:22 


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

 Профиль  
                  
 
 Re: Устойчивость сингулярного разложения
Сообщение11.01.2015, 20:36 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Устойчивость сингулярного разложения
Сообщение11.01.2015, 22:34 


06/01/10
56
Евгений Машеров в сообщении #960131 писал(а):
Впрочем, что имел в виду автор данного высказывания, я не знаю, может, что-то совершенно иное.

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

 Профиль  
                  
 
 Re: Устойчивость сингулярного разложения
Сообщение12.01.2015, 09:43 
Заслуженный участник
Аватара пользователя


11/03/08
9490
Москва
Ну, возьмём разложение $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 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Устойчивость сингулярного разложения
Сообщение12.01.2015, 15:39 


06/01/10
56
Евгений Машеров в сообщении #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 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Устойчивость сингулярного разложения
Сообщение15.01.2015, 11:35 
Заслуженный участник
Аватара пользователя


11/03/08
9490
Москва
В общем, как справедливо заметил 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 


06/01/10
56
Евгений Машеров в сообщении #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 
Заслуженный участник
Аватара пользователя


11/03/08
9490
Москва
Ну, хотя бы через круги Гершгорина можно оценить.

 Профиль  
                  
 
 Re: Устойчивость сингулярного разложения
Сообщение19.01.2015, 03:49 


06/01/10
56
Евгений Машеров в сообщении #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 
Заслуженный участник


11/05/08
32166
djuuj в сообщении #964643 писал(а):
известно же, что устойчивость собственных чисел, в отличие от сингулярных, зависит от числа обусловленности матрицы.

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

 Профиль  
                  
 
 Re: Устойчивость сингулярного разложения
Сообщение19.01.2015, 22:05 
Заслуженный участник
Аватара пользователя


11/03/08
9490
Москва
Устойчивость собственных чисел может зависеть от коэффициентов перекоса
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 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group