Наименьшие квадраты в синус или угловой норме

[ilghiz]

Добрый день,

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

Дана $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]$.

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

Спасибо!

Pphantom:

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

[svv]

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

[ilghiz]

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

[svv]

То есть $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||$ (в смысле Вашей нормы).
(Разложить-то известную матрицу мы всегда сможем.)

[ilghiz]

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

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

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

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

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

[svv]

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

[ilghiz]

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

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

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

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

[svv]

ilghiz в сообщении #1391432 писал(а):

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

Я Вас понял.
Я бы сказал, что классическое понятие ранга матрицы плохо соответствует Вашей норме, заточенной под тор, с её периодичностью. Оно, по-моему, вообще неадекватно Вашей задаче.

[ilghiz]

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

-- 07.05.2019, 08:54 --

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

[svv]

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

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

[ilghiz]

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

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

[ilghiz]

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

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