Максимумы по невязке при повороте в сферических координатах

[ilghiz]

Добрый день,

имеется две функции $f(r,a,b), g(r,a,b),$, $r \in [0,\infty], a,b \in [-180^o,+180^o]$, для которых известно что производные ограничены, при $r \to \infty$ : $f(r,a,b) \to 0$ и $g(r,a,b) \to 0$.

Мне надо найти несколько самых маленьких минимумов невязки для всех значений углов, то есть найти несколько решений $(p,q)$ для

$$\min_{p,q} \int_0^{\intfy} \int_{-180^o}^{180^o} \int_{-180^o}^{180^o} ||f(r,a,b)-g(r,a+q,b+q)||_2^2 da db dr$$

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

Сами функции заданы в декартовых координатах на конечных элементах.

Понимаю, как решить перебором, считая в лоб минимизируемую функцию для всех $(p,q)$ на какой-то сетке. Но асимптотика такого решения будет порядка $O(N^5)$, если $N$ - число дискретов по каждой размерности, да и точность сходимости по углам будет очень плохая... Хочу элегантного решения, типа Фурье, но вроде Фурье на таких сетках не бывает.

Скажите, пожалуйста, в какую сторону смотреть?

Спасибо!

[svv]

Я не знаю, в какую сторону смотреть, но есть несколько замечаний.
1) Если $||f-g||^2_2$ — квадрат нормы функции $f-g$, то эта штука уже подразумевает интегрирование по $\mathbb R^3$.
2) Вместо $g(r,a+{\color{magenta}q},b+q)$, скорее всего, должно быть $g(r,a+{\color{magenta}p},b+q)$.
3) Если $r,a,b$ действительно сферические координаты, их лучше обозначить стандартно: $(r,\theta,\varphi)$.
4) Причём угол $\theta$ меняется только в диапазоне $[0,\pi]$.
5) И подинтегральная функция должна содержать ещё якобиан $r^2\sin \theta$.
6) Бесконечность $\infty$ «не пропечаталась» в верхнем пределе интеграла по $r$, потому что вместо \infty набрано \intfy.
7) Конструкция интеграла намекает, что Вы ищете такой «поворот функции $g$ вокруг центра», после которого $g$ наилучшим образом совпадёт с $f$. Но $g(r,\theta+\Delta\theta,\varphi+\Delta\varphi)$ описывает не поворот, а что-то совсем другое. Для простоты возьмите $\Delta\varphi=0$. Сдвиг точек на $\Delta\theta$ вдоль меридианов — это не поворот. А вот сдвиг вдоль параллелей на $\Delta\varphi$ — это поворот.

[ilghiz]

svv
полностью с Вашими замечаниями согласен! Да, путаница у меня какая-то вышла, хотел вначале в декартовых координатах задачу сформулировать, а потом как-то совсем криво в спешке перезаписал, каюсь, простите.

Да, ищется именно унитарная трансформация, которая бы переводила бы $g$ так, получаемое значение наилучшим образом совпадало бы с $f$.

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

PS: а как переформулировать исходное сообщение, чтобы исправить ошибки?

[svv]

Ок.
Можно ещё добавить
8) Вращающаяся вокруг центра сфера (к которой "прицеплена" функция $g$) имеет не две, а три степени свободы. Две степени нужны, чтобы задать положение северного и южного полюса, но после этого сферу можно ещё крутить вокруг оси, проходящей через них. Соответственно, подбирать придётся три параметра (например, углы Эйлера).

[vpb]

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

-- 05.03.2021, 01:22 --

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

а как переформулировать исходное сообщение, чтобы исправить ошибки?

Для начала неплохо бы узнать, что такое углы Эйлера, и как элемент объема в сферических координатах записывается.

[svv]

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

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

Сначала в бескоординатном виде. Найти матрицу поворота $A$, при которой достигается минимум интеграла
$I(A)=\int\limits_{\mathbf r\in\mathbb R^3}\left(f(\mathbf r)-g(A\mathbf r)\right)^2\,dV\;.$
Здесь
$f,g$ — заданные функции,
$\mathbf r$ — радиус-вектор,
$A$ — матрица размера $3\times 3$, ортогональная, $\det A=1$,
$dV$ — элемент объёма.

Раскройте скобки под интегралом, разбейте интеграл на сумму трёх интегралов и скажите, какие интегралы не зависят от матрицы $A$ (и потому их можно "выбросить").

[ilghiz]

Спасибо большое, svv за советы!

svv в сообщении #1507922 писал(а):

$A$ — матрица размера $3\times 3$, ортогональная, $\det A=1$,

так как раз в ней-то и будет 3 степени свободы,

svv в сообщении #1507922 писал(а):

Раскройте скобки под интегралом, разбейте интеграл на сумму трёх интегралов и скажите, какие интегралы не зависят от матрицы $A$ (и потому их можно "выбросить").

и после раскрытия скобок вроде ничего не выбросить...

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

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

[svv]

$I(A)$ равен сумме трёх слагаемых:
$\int(f(\mathbf r))^2\,dV$ очевидно не зависит от $A$;
$\int(g(A\mathbf r))^2\,dV$ на первый взгляд зависит от $A$, на самом деле сводится к $\int(g(\mathbf r))^2\,dV$ заменой $A\mathbf r=\tilde{\mathbf r}$;
Эти два слагаемых постоянны при заданных $f,g$, так что их можно убрать из $I(A)$.

И только $-2\int f(\mathbf r) g(A\mathbf r)\,dV$ зависит от $A$, и эту зависимость нельзя устранить никакими заменами. Коэффициент $-2$ можно убрать, заменив в условии "минимум" на "максимум".

Так мы приходим к эквивалентной задаче: найти матрицу $A$ (со всеми упомянутыми свойствами), на которой интеграл
$\int\limits_{\mathbf r\in\mathbb R^3} f(\mathbf r) g(A\mathbf r)\,dV$
принимает максимальное значение. Иными словами, надо для корреляции $f$ и $g$, зависящей от матрицы поворота $A$, найти точку максимума.

[ilghiz]

svv в сообщении #1507929 писал(а):

Иными словами, надо для корреляции $f$ и $g$, зависящей от матрицы поворота $A$, найти точку максимума.

Спасибо, да, верно. Численно только это не сильно задачу облегчает, или невязку считать, или скалярное произведение - каждое такое вычисление будет стоить $N^3$ операций, а все это надо перебрать по всем возможным вариантам матрицы $A$. Вот если бы тут что-то типа Фурье сделать, чтобы посчитать все невязки или скалярные произведения.

[svv]

Вы правы.

[svv]

svv в сообщении #1507922 писал(а):

$A$ — матрица

Точнее, линейный оператор $\mathsf A$, c аналогичными свойствами, раз речь идёт о бескоординатной записи.

[arseniiv]

Можно заметить, что если мы имеем посчитанными $f\circ A_1,\ldots, f\circ A_m$ и $g\circ A_{m+1},\ldots, g\circ A_{m+n}$ (если $f, g$ это просто наборы значений функций в разных точках), то мы можем вычислить $m\times n$ интегралов, чуть меньше считая. То есть может быть можно подобрать какие-то такие $A_i$, которые вместе дают квадратичное количество более-менее равномерно расположенных по всей $\mathrm{SO}(3)$ операторов, ну и плюс если мы нашли пару хорошо выглядящих оптимумов, можно потом довычислять ещё немного маленьких других $A_i$ и пощупать окрестности минимумов в большей точностью.

[ilghiz]

arseniiv в сообщении #1508011 писал(а):

Можно заметить, что если мы имеем посчитанными $f\circ A_1,\ldots, f\circ A_m$ и $g\circ A_{m+1},\ldots, g\circ A_{m+n}$ (если $f, g$ это просто наборы значений функций в разных точках), то мы можем вычислить $m\times n$ интегралов, чуть меньше считая.

Спасибо за ответ.

Возможно я что-то не понимаю, или подзабыл.

Даже пусть у меня $f$ и $g$ - это одна и та же функция.

Пусть я посчитаю первые $m$ функций $f(A_i x)$, $i=1,...,m$. Пусть стоимость вычисления этих функций будет для меня бесконечно маленькой :)

И как я смогу пересчитать все возможные скалярные произведения, это всяко же $m^2 N^3$, где $N$ - дискретизация самих $g$ и $f$.

Или?

[arseniiv]

Эта часть никуда не денется, да, увы, но хоть меньше матриц умножать. Но да, это экономия сомнительная, просто вдруг какая-то идея отсюда ещё вылезет…

[ilghiz]

Спасибо за советы!

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

По сути исходные функции $f(x)$ и $g(x)$ относительно хорошо аппроксимируются тензорными формами, а именно

$$f(x_1,x_2,x_3) \simeq \sum_{i=1}^R a_i(x_1)^{(1)} a_i(x_2)^{(2)} a_i(x_3)^{(3)}$$

где $R$ существенно меньше дискретизации каждой из $x_1$, $x_2$ и $x_3$

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