2014 dxdy logo

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

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


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


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Ортогональная матрица для которой норма Фробениуса минимальн
Сообщение09.10.2024, 08:28 


08/10/24
2
Добрый день! Помогите, пожалуйста, решить задачу.

Для двух заданных матриц A и B одного размера найдите ортогональную матрицу Q, для которой норма Фробениуса разности $\left\lVert{QA-B}\right\rVert_{F}$ минимальна.
Hint: воспользуйтесь SVD.

Мой ход решения.
Воспользовавшись подсказкой, я расписал норму Фробениуса через SVD.
Получил следующее:

$\left\lVert{QA-B}\right\rVert_{F} = \sqrt{tr((U \Sigma V')'U \Sigma V')} = \sqrt{tr(\Sigma' \Sigma)} = \sqrt{\sum\limits_{1}^{n} \sigma ^{2}_{n}  } = \sqrt{\sum\limits_{1}^{n} \lambda_{n}  } $

Где:
$\sigma$ - сингулярные значения для $(QA-B)$ ;
$\lambda$ - собственные значения для $(QA-B)^{T}(QA-B)$;
$' = T$ - транспонирование;
$n$ - размерность матриц A и B (для простоты будем считать, что матрицы квадратные, хотя они могут быть произвольного размера)

На этом моё решение зашло в тупик. Не понимаю, что делать дальше. Как мне найти ортогональную матрицу Q, чтобы норма Фробениуса была минимальной?

 Профиль  
                  
 
 Re: Ортогональная матрица для которой норма Фробениуса минимальн
Сообщение09.10.2024, 15:36 
Заслуженный участник
Аватара пользователя


23/07/08
10887
Crna Gora
С помощью сингулярного разложения Вы можете, по крайней мере, свести Вашу задачу к более простой, где вместо $A$ будет стоять диагональная матрица. Пусть $A=U\Sigma V'$. Обозначим $\tilde Q=QU,\;\tilde B=BV$. Тогда
$$\|QA-B\|_{F} = \|QAV-BV\|_{F} = \|QU\Sigma V'V-BV\|_{F}=\|\tilde Q\Sigma-\tilde B\|_{F}$$Любой ортогональной $Q$ нужного размера в левой части взаимно однозначно соответствует некоторая ортогональная $\tilde Q$ в правой части, при том что нормы левой и правой части равны. Поэтому новая задача (с $\Sigma,\tilde B$ вместо $A, B$) эквивалентна старой.

 Профиль  
                  
 
 Posted automatically
Сообщение09.10.2024, 16:37 
Админ форума


02/02/19
2470
 i  Тема перемещена из форума «Математика (общие вопросы)» в форум «Помогите решить / разобраться (М)»
Причина переноса: темы, в которых нужно что-то объяснить или подсказать в пределах учебных курсов, создаются в этом разделе.

 Профиль  
                  
 
 Re: Ортогональная матрица для которой норма Фробениуса минимальн
Сообщение09.10.2024, 17:31 
Заслуженный участник
Аватара пользователя


23/07/08
10887
Crna Gora
Оказывается, это «Orthogonal Procrustes problem», и её общее решение было дано только в 1964 году. Посмотрите в английской Википедии статью с таким названием.

 Профиль  
                  
 
 Re: Ортогональная матрица для которой норма Фробениуса минимальн
Сообщение09.10.2024, 18:08 


08/10/24
2
svv в сообщении #1658064 писал(а):
Оказывается, это «Orthogonal Procrustes problem», и её общее решение было дано только в 1964 году. Посмотрите в английской Википедии статью с таким названием.

Большое вам спасибо! Весь интернет перерыл и ни разу не наткнулся на эту страницу в Википедии)

 Профиль  
                  
 
 Re: Ортогональная матрица для которой норма Фробениуса минимальн
Сообщение09.10.2024, 22:39 


01/09/14
19/11/24
500
Вдогонку решение от ИИ.
GPT писал(а):
Давайте подробнее разберем задачу.

### Постановка задачи

Для двух заданных матриц $\( A \)$ и $\( B \)$ одного размера необходимо найти ортогональную матрицу $\( Q \)$, которая минимизирует норму Фробениуса разности:

$\left\lVert{QA - B}\right\rVert_{F}$

### Ваш ход решения

Вы воспользовались сингулярным разложением (SVD), что является верным шагом для данной задачи. Сначала напомню определение нормы Фробениуса:

$\left\lVert M \right\rVert_{F} = \sqrt{\sum_{i,j} |M_{ij}|^2} = \sqrt{\text{tr}(M^T M)}$

Теперь, если мы применим это к выражению $\( \left\lVert{QA - B}\right\rVert_{F} \)$, то получим:

$\left\lVert{QA - B}\right\rVert_{F} = \sqrt{\text{tr}\left((QA - B)^T (QA - B)\right)}$

### Следующий шаг: применение SVD

Мы можем представить матрицы $\( A \)$ и $\( B \)$ через их сингулярные разложения. Рассмотрим сингулярное разложение матрицы $\( A \)$:

$A = U_A \Sigma_A V_A^T$

где:
- $\( U_A \)$ и $\( V_A \)$ — ортогональные матрицы,
- $\( \Sigma_A \)$ — диагональная матрица, содержащая сингулярные значения матрицы $\( A \)$.

Теперь разложим $\( QA \)$ как:

$QA = Q U_A \Sigma_A V_A^T$

Пусть матрица $\( B \)$ также имеет сингулярное разложение:

$B = U_B \Sigma_B V_B^T$

### Минимизация нормы Фробениуса

Нам нужно минимизировать выражение:

$\left\lVert{QA - B}\right\rVert_{F} = \left\lVert{Q U_A \Sigma_A V_A^T - U_B \Sigma_B V_B^T}\right\rVert_{F}$

Чтобы минимизировать это выражение, нам необходимо выбрать матрицу \( Q \), которая минимизирует норму разности $\( Q U_A \)$ и $\( U_B \)$.

### Решение с использованием матрицы поворота

Из теоремы об ортогональной проксимальности (Procrustes problem), известно, что ортогональная матрица $\( Q \)$, минимизирующая норму Фробениуса, может быть найдена с использованием сингулярного разложения матрицы произведения $\( A^T B \)$. Рассмотрим следующую матрицу:

$A^T B = V_A \Sigma_A U_A^T U_B \Sigma_B V_B^T$

Пусть SVD разложения этой матрицы имеют вид:

$A^T B = U \Sigma V^T$

Тогда оптимальная ортогональная матрица $\( Q \)$, минимизирующая норму Фробениуса, задается как:

$Q = UV^T$

### Заключение

Таким образом, решение задачи сводится к вычислению SVD для матрицы $\( A^T B \)$ и построению ортогональной матрицы $\( Q = UV^T \)$, которая минимизирует норму Фробениуса разности $\( \left\lVert{QA - B}\right\rVert_{F} \)$.

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

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



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

Сейчас этот форум просматривают: DariaRychenkova


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

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