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 ] 

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



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

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


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

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