2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Наименьшие квадраты в синус или угловой норме
Сообщение07.05.2019, 00:31 


11/08/18
363
Добрый день,

имеется незадачка.

Дана $A \in C^{N \times M}$, надо найти $U \in C^{N \times R}, V \in C^{M \times R}, R \le \min(M,N)$, так, чтобы $\min_{U,V} ||A-UV^*||_c^2$, где $||x_{ij}||_c^2 = \sum_i \sum_j \sin^2(x_{ij})$.

В обычной Евклидовой норме мне все понятно как решать, но надо именно в такой угловой норме решить. На крайняк, в какой-то другой похожей угловой норме, но только с учетом того, что все, что за пределами $[-\pi,\pi]$ перенаправляется в $[-\pi,\pi]$.

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

Спасибо!

 i  Pphantom:
Надо бы все формулы набирать правильно. Поправил очевидно недостающее.

 Профиль  
                  
 
 Re: Наименьшие квадраты в синус или угловой норме
Сообщение07.05.2019, 01:48 
Заслуженный участник


23/07/08
10626
Crna Gora
Добрый вечер.
Я не увидел интриги. Пусть для определённости $N\geqslant M$, тогда возьмём $R=M, U=A, V=E$, получим $A-UV^*=0$. Я чего-то не заметил?

 Профиль  
                  
 
 Re: Наименьшие квадраты в синус или угловой норме
Сообщение07.05.2019, 02:08 


11/08/18
363
Интрига-то то простая - $R$ - меньше числа ненулевых сингулярных чисел матрицы $A$. Иначе - да, интриги нет. Как-то подумал, что если речь о наименьших квадратах, то мысль у всех в эту сторону пойдет. Ну и понятно, что $U$ - унитарной и $V$ с ортогональными столбцами бы хотелось бы иметь, или как в классике с SVD: $||A-UDV^*||_c^2$ c диагональной $D$.

 Профиль  
                  
 
 Re: Наименьшие квадраты в синус или угловой норме
Сообщение07.05.2019, 02:11 
Заслуженный участник


23/07/08
10626
Crna Gora
То есть $R$, фактически, задано, а не подбирается? Тогда надо формулировать так:
Дана матрица $A \in \mathbb C^{N \times M}$ и число $R\leqslant\min(N,M)$. Найти матрицы $U \in \mathbb C^{N \times R}, V \in \mathbb C^{M \times R}$, которые минимизируют $||A-UV^*||_c^2$, где $||X||_c^2 = \sum\limits_{i,j}\sin^2 x_{ij}$.

P.S. Обратите внимание на замечание модератора. Пара знаков доллара по бокам от любой формулы, включая одиночную переменную. Жаль, если тема окажется в Карантине.

-- Вт май 07, 2019 02:50:25 --

Наверное, наиболее «чистая» постановка задачи такая.
Дана матрица $A$. Найти матрицу $B$ того же размера и заданного ранга $r<\operatorname{rank}A$, минимизирующую $||A-B||$ (в смысле Вашей нормы).
(Разложить-то известную матрицу мы всегда сможем.)

 Профиль  
                  
 
 Re: Наименьшие квадраты в синус или угловой норме
Сообщение07.05.2019, 02:54 


11/08/18
363
Спасибо, да, ранг надобно подобрать, но я сомневаюсь, что тут все будет гладко, как в Евклидовой норме и перебором сингулярных чисел и отбрасыванием их по порогу все решится. А так, да, надо, чтоб как-то не сильно откланялось, с наперед заданным эпсилоном и минимизировало в том числе и ранг.

Не хотелось бы изобретать велосипед. То есть я как-то это методом грубой силы решаю, но, ИМХО, такие задачи должны были уже возникать и хотелось бы почитать как их люди решали, и что достигали. На крайняк, сослаться чтоб было на кого.

Подсобите, пожалуйста, ссылками и названиями.

После Вашей модификации, добавлю.

Да, согласен, если говорить про двухмерные варианты, то да, Вы правы. Я в общем-то решаю задачи, когда $U$ - может быть специальной. Один из примеров, разложение 3 и более мерного объекта на минимальную или псевдоминимальную сумму тензоров. В Евклидовой там уже есть свои проблемы, но мне они понятны, а вот когда все работает на таком торе - до этого не встречал. То есть ИМХО, люди должны были на эту тему уже топтаться, все-таки даже не начало 21 века на дворе, но почему-то не находится ничего, думаю из-за того, что это как-то очень специфично называется.

 Профиль  
                  
 
 Re: Наименьшие квадраты в синус или угловой норме
Сообщение07.05.2019, 02:58 
Заслуженный участник


23/07/08
10626
Crna Gora
Вот с рангом всё-таки непонятно: мы имеем право его подбирать (в каких пределах? чтобы был меньше ранга $A$?), или он задан?

 Профиль  
                  
 
 Re: Наименьшие квадраты в синус или угловой норме
Сообщение07.05.2019, 03:06 


11/08/18
363
В первом приближении - пусть он задан. Во втором - нужны оценки.

Примерные размеры моих задач N=100000, M=1000, R - от 2 до 100, но это пока тестовое, а в реальности может будет и больше.

В Евклидовой ранг-ревеалинг позволит довольно быстро схлопнуть задачу в малоганговую.

В этом случае есть произвол в том, что пусть даже все значения $A$ лежат в диапазоне $[-\pi,\pi]$, оптимальным решением может быть такое, в котором некоторые значения $U$ и $V$ будут за этим диапазоном, но разложение будет малоранговым.

 Профиль  
                  
 
 Re: Наименьшие квадраты в синус или угловой норме
Сообщение07.05.2019, 03:16 
Заслуженный участник


23/07/08
10626
Crna Gora
ilghiz в сообщении #1391432 писал(а):
пусть даже все значения $A$ лежат в диапазоне $[-\pi,\pi]$, оптимальным решением может быть такое, в котором некоторые значения $U$ и $V$ будут за этим диапазоном, но разложение будет малоранговым.
Я Вас понял.
Я бы сказал, что классическое понятие ранга матрицы плохо соответствует Вашей норме, заточенной под тор, с её периодичностью. Оно, по-моему, вообще неадекватно Вашей задаче.

 Профиль  
                  
 
 Re: Наименьшие квадраты в синус или угловой норме
Сообщение07.05.2019, 09:43 


11/08/18
363
Не знаю на сколько адекватно или нет тут обозначение ранга, но ведь рангом всегда обозначают ранг тензорного или, так называемого мультилинейного разложения. А мне честно говоря, не шашечки нужны, а понимания, как люди такую задачу решали. Ведь тут можно множество задач наформулировать в области наименьших квадратов.

-- 07.05.2019, 08:54 --

EDIT: Вот, например, если взять квадратную матрицу, элементы которой будут сделаны так: $a_{ij}=\arcsin(\sin(i*j)), i=1,\dots,N, j=1,\dots,N$, то она будет полноранговая, правда плохо обусловленная, хотя почти все ее сингулярные числа распределены более-менее равномерно, а вот такой синус ранг - всего-то единица, причем тождественно.

 Профиль  
                  
 
 Re: Наименьшие квадраты в синус или угловой норме
Сообщение07.05.2019, 19:20 
Заслуженный участник


23/07/08
10626
Crna Gora
Я имел в виду, что если $\|A-B\|=0$ (что означает, что $|a_{ij}-b_{ij}|$ кратно $\pi$), то было бы желательно, чтобы $\operatorname{rank}A=\operatorname{rank}B$, но обычный ранг этому требованию не удовлетворяет.

Стоит ещё заметить, что Ваша угловая норма нарушает аксиомы матричных норм:
1) $\|A\|>0$, если $A\neq 0$
2) $\|cA\|=|c|\|A\|$
Так что лучше называть её просто скалярной функцией от матрицы.

 Профиль  
                  
 
 Re: Наименьшие квадраты в синус или угловой норме
Сообщение07.05.2019, 19:45 


11/08/18
363
Спасибо, да, конечно, согласен на счет замечания по поводу нормы, я вчера, кажется, погорячился это нормой назвать.

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

 Профиль  
                  
 
 Re: Наименьшие квадраты в синус или угловой норме
Сообщение16.05.2019, 01:14 


11/08/18
363
Если кому-то интересно, называется это наименьшие квадраты на многообразии или на торе. Теоретической литературы достаточно много, а когда дело касается только реальных задач и сходимости и численных методов, то находятся только задачи о вращении деталей роботов или аппроксимации чего-то наснятого на сферах.

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

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

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



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

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


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

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