Журнал вычислительной математики и математической физики, 2022, T. 62, № 8, стр. 1341-1359

3.1. Оптимальное транспортное отображение

Пусть $\Omega ,\Omega {\kern 1pt} * \subset {{\mathbb{R}}^{d}}$ – области в евклидовом пространстве, с вероятностными мерами $\mu $ и $\nu $ соответственно, удовлетворяющие условию равенства общей массы: $\mu (\Omega ) = \nu (\Omega {\kern 1pt} *).$ Транспортное отображение $T:\Omega \to \Omega {\kern 1pt} *$ является сохраняющим меру, если для любого множества Бореля $B \subset \Omega {\kern 1pt} *$, $\int_{{{T}^{{ - 1}}}(B)}^{} {d\mu (x)} = \int_B^{} {d\nu (y)} .$ Условие сохранения меры обозначим как ${{T}_{\# }}\mu = \nu $.

Монж поставил задачу оптимального транспортного отображения: учитывая функцию стоимости транспорта $c:\Omega \times \Omega {\kern 1pt} * \to {{\mathbb{R}}^{ + }}$, найти транспортное отображение $T:\Omega \to \Omega {\kern 1pt} *$, которое минимизирует общую стоимость транспорта,

Минимизатор называется оптимальным транспортным отображением. Стоимость транспорта оптимального транспортного отображения называется расстоянием Вассерштейна между мерами.

Теорема 1 (Бренье, см. [8]). Пусть для компактной области $\Omega \subset {{\mathbb{R}}^{d}}$ с абсолютно непрерывными вероятностными мерами $\mu $ и $\nu $, $\partial \Omega $ имеет нулевую меру Лебега, а стоимость транспортировки $c(x,y) = \frac{1}{2}{{\left| {x - y} \right|}^{2}}$. Тогда существует выпуклая функция $u:\Omega \to \mathbb{R}$ однозначная с точностью до константы, так называемый потенциал Бренье, и оптимальное транспортное отображение задается градиентом $u$, $T = \nabla u$.

Потенциал Бренье удовлетворяет уравнению Монжа–Ампера

с граничным условием $\nabla u(\Omega ) = \Omega {\kern 1pt} *$. Однозначное оптимальное транспортное отображение дается в виде $T = \nabla u$.

3.2. Решение Александрова

Для численных расчетов потенциал Бренье аппроксимируется кусочно-линейной выпуклой функцией, график которой представляет собой выпуклый многоугольник. Субградиент выпуклой функции $u$ в точке $x$ определяется как $\partial u(x): = \{ p \in {{\mathbb{R}}^{d}}:u(z) \geqslant \langle p,z - x\rangle + u(x),\;\forall z \in \Omega \} $.

Субградиент определяет отображение, принимающее множества как значения $\partial u:\Omega \to \Omega {\kern 1pt} *$, $x \mapsto \partial u(x)$. Мы можем использовать карту субградиента для замены карты градиента в уравнении Монжа–Ампера (1) и переписать его как

или, эквивалентно, $\forall {\text{Borel}} B \subset \Omega {\kern 1pt} *$, $\mu ((\partial u{{)}^{{ - 1}}}(B)) = \nu (B)$. Таким образом, здесь $u$ называется решением Александрова. На самом деле, решение Александрова эквивалентно политопу Александрова, а теорема Бренье эквивалентна теореме Александрова в выпуклой геометрии.

3.3. Теоремы Минковского и Александрова

Здесь мы кратко напомним основные понятия и теоремы Минковского и теоремы Александрова в выпуклой геометрии, которые могут быть описаны уравнением Монжа–Ампера и тесно связаны со степенными диаграммами и взвешенными триангуляциями Делоне в вычислительной геометрии. Эта внутренняя связь дает теоретический инструмент для изучения пространства политопов Александрова (подробнее см. [12], [13]).

Минковский доказал существование и единственность выпуклого многоугольника с заданными нормалями и площадями граней (фиг. 5).

Теорема 2 (Минковского). Предположим, что ${{n}_{1}}, \ldots ,{{n}_{k}}$ – единичные векторы, которые охватывают ${{\mathbb{R}}^{n}}$, и найдутся положительные числа ${{\nu }_{1}}, \ldots ,{{\nu }_{k}}$ такие, что $\sum\nolimits_{i = 1}^k \,{{\nu }_{i}}{{n}_{i}} = 0$. Тогда существует компактный выпуклый многоугольник $P \subset {{\mathbb{R}}^{n}}$, имеющий ровно $k$ граней ${{F}_{1}}, \ldots ,{{F}_{k}}$ коразмерности-1, такой, что ${{n}_{i}}$ – вектор внешней нормали к ${{F}_{i}}$ и ${{\nu }_{i}}$ – объем ${{F}_{i}}$. Более того, такой $P$ единственен с точностью до трансляции.

Доказательство Минковского является вариационным и предлагает алгоритм нахождения политопа. Теорема Минковского для неограниченных выпуклых многогранников была рассмотрена и решена А.Д. Александровым и его учеником А. Погореловым. В своей книге о выпуклых многогранниках [12] Александров доказал следующую фундаментальную теорему (см. [12, теоремы 7.3.2 и 6.4.2]).

Теорема 3 (Александрова, см. [12]). Предположим, что $\Omega $ – компактный выпуклый многоугольник с непустой внутренней частью в ${{\mathbb{R}}^{n}}$, ${{n}_{1}}, \ldots ,{{n}_{k}} \subset {{\mathbb{R}}^{{n + 1}}}$ представляют собой $k$ различных единичных векторов с отрицательными $(n + 1)$-ми координатами, и положительные числа ${{\nu }_{1}}, \ldots ,{{\nu }_{k}}$ таковы, что $\sum\nolimits_{i = 1}^k \,{{\nu }_{i}} = \operatorname{vol} (\Omega )$. Тогда существует выпуклый политоп $P \subset {{\mathbb{R}}^{{n + 1}}}$ с точно $k$ гранями коразмерности-1 ${{F}_{1}}, \ldots ,{{F}_{k}}$ такой, что ${{n}_{i}}$ – нормальный вектор к ${{F}_{i}}$ и пересечение $\Omega $ с проекцией ${{F}_{i}}$ имеет объем ${{\nu }_{i}}$. Более того, такой $P$ единственен с точностью до вертикальной трансляции.

Доказательство Александрова основано на алгебраической топологии и неконструктивно. Ауренхаммер (см. [14]) дал конструктивное доказательство с использованием степенной диаграммы. Гу и соавт. (см. [13]) дали другое вариационное доказательство обобщенной теоремы Александрова, изложенное в терминах выпуклых функций. Энергии в [14] и [15] являются двойственными друг другу по Лежандру.

Определение 1 (политоп Александрова). При заданных $Y = \{ {{y}_{1}}, \ldots ,{{y}_{k}}\} $, ${{y}_{i}} \in {{\mathbb{R}}^{n}},$ $i = 1,2, \ldots ,k$, и $h = ({{h}_{1}}, \ldots ,{{h}_{k}}) \in {{\mathbb{R}}^{k}}$ верхняя оболочка гиперплоскостей ${{\pi }_{i}}(x) = \langle x,{{y}_{i}}\rangle - {{h}_{i}}$ есть

где $\langle \,,\rangle $ представляет собой скалярное произведение. Граф ${{u}_{h}}$ называется политопом Александрова, обозначается как $P(Y,h)$.

Проекция политопа Александрова приводит к степенной диаграмме ${{\mathbb{R}}^{n}}$, каждая ячейка ${{W}_{i}}(h)$ является замкнутым выпуклым политопом:

где ${{W}_{i}}(h)$ называются степенными ячейками. Степенная диаграмма может быть сформулирована с помощью степенного расстояния где степенное расстояние между $x$ и ${{y}_{i}}$ определяется как где $r_{i}^{2}$ – степень, связанная с ${{y}_{i}}$, определяемая как Для меры вероятности $\mu $, определенной на $\Omega $, объем ${{W}_{i}}(h)$ определяется как

Гу и др. дали конструктивное доказательство теоремы Александрова.

Теорема 4 (Гу–Луо–Сун–Яу, см. [13]). Пусть $\Omega $ – компактная выпуклая область в ${{\mathbb{R}}^{n}}$, $Y = \{ {{y}_{1}}, \ldots ,{{y}_{k}}\} $ – множество отдельных точек в ${{\mathbb{R}}^{n}}$ и $\mu $ – мера вероятности на $\Omega $. Тогда для любых ${{\nu }_{1}}, \ldots ,{{\nu }_{k}} > 0$ с $\sum\nolimits_{i = 1}^k \,{{\nu }_{i}} = \mu (\Omega )$ существует $h = ({{h}_{1}}, \ldots ,{{h}_{k}}){\kern 1pt} {{\mathbb{R}}^{k}}$, единственное с точностью до аддитивной константы $(c, \ldots ,c)$, так что ${{w}_{i}}(h) = {{\nu }_{i}}$, для всех $i$. Векторы $h$ являются точными точками максимума вогнутой функции

на открытом выпуклом множестве (пространстве допустимых высот) Кроме того, $\nabla {{u}_{h}}$ минимизирует квадратичную стоимость $\int_\Omega {{{{\left| {x - T(x)} \right|}}^{2}}d\mu (x)} $ среди всех транспортных отображений ${{T}_{\# }}\mu = \nu $, где мера Дирака определена как $\nu = \sum\nolimits_{i = 1}^k \,{{\nu }_{i}}\delta (y - {{y}_{i}})$.

На фиг. 6 продемонстрировано оптимальное транспортное отображение, полученное методом политопа Александрова. Поверхность лица мужчины оцифрована в треугольную сетку $M$ (фиг. 6а). Поверхность конформно отображается на плоский единичный диск с помощью отображения Римана (фиг. 6б), плоские изображения вершин обозначаются как ${{y}_{1}}, \ldots ,{{y}_{k}}$. Для каждой вершины ${{v}_{i}}$ общая площадь прилегающих к ней треугольных граней обозначается как ${{\nu }_{i}}$. При масштабировании общая площадь $\sum\nolimits_{i = 1}^k \,{{\nu }_{i}} = \pi $. Затем вычисляем оптимальное транспортное отображение (фиг. 6в) из единичного диска с равномерным распределением $\nu = \sum\nolimits_{i = 1}^k \,{{\nu }_{i}}\delta (y - {{y}_{i}})$. Потенциал Бренье показан на фиг. 6г.

3.4. Вторичный политоп и вторичная степенная диаграмма

Кратко напомним основные понятия и теоремы теории вторичных политопов Гельфанда и его двойственной вторичной степенной диаграммы (подробнее см. [15]–[17]), которые показывают, что допустимое пространство решений ${{\mathcal{H}}_{\Omega }}(Y)$ имеет разложение по ячейкам.

Вторичный политоп. Пусть $Y = \{ {{y}_{1}}, \ldots ,{{y}_{k}}\} $ – конфигурация точек, а конечное множество отдельных точек в ${{\mathbb{R}}^{d}}$, $\operatorname{Conv} (Y)$ – выпуклая оболочка $Y$. Триангуляция $T$ из $(Y,\operatorname{Conv} (Y))$ разбивает внутренний объем, ограниченный $\operatorname{Conv} (Y)$, на симплексы с вершинами в $Y$. Некоторые ${{y}_{i}} \in Y$ могут не быть вершинами симплекса.

Учитывая триангуляцию $T$, частично линейная функция $g:\operatorname{Conv} (Y) \to \mathbb{R}$ является аффинно-линейной на каждом симплексе $T$. Более того, $g$ является вогнутой, если для любых $x,y \in \operatorname{Conv} (Y)$ $g(tx + (1 - t)y) \geqslant tg(x) + (1 - t)g(y)$.

Определение 2 (когерентная триангуляция). Триангуляция $T$ из $(Y,\operatorname{Conv} (Y))$ называется когерентной, если существует вогнутая кусочно-линейная функция, область линейности которой в точности является (максимальными) симплексами $T$.

Пусть $T$ – триангуляция $(Y,\operatorname{Conv} (Y))$. Характеристическая функция $T$, ${{\varphi }_{T}}:Y \to \mathbb{R}$, определяется следующим образом:

где суммирование ведется по всем (максимальным) симплексам $T$, для которых $\omega $ является вершиной. Если $\omega $ не является вершиной ни одного симплекса из $T$, то ${{\varphi }_{T}}(\omega ) = 0$.

Определение 3 (вторичный политоп). Вторичный политоп $\Sigma (Y)$ – это выпуклая оболочка в пространстве ${{\mathbb{R}}^{Y}}$ векторов ${{\phi }_{T}}$ для всех триангуляций $(Y,\operatorname{Conv} (Y))$ $T$.

Свойства вторичного политопа приведены в теореме 5.

Теорема 5. $1)$ Вторичный политоп $\Sigma (Y)$ имеет размерность $k - n - 1$, где $k = \# (Y)$.

$2)$ Если $T$ – когерентная триангуляция $(Y,{\text{Conv}}(Y))$, то ${{\varphi }_{T}} \ne {{\varphi }_{{T'}}}$ для любой другой триангуляции $(Y,{\text{Conv}}(Y))$ $T{\kern 1pt} '$. Вершины $\Sigma (Y)$ – это именно характеристические функции для всех связных триангуляций $(Y,{\text{Conv}}(Y))$ $T$.

Вторичная степенная диаграмма. Первичные взвешенные триангуляции Делоне дуальны к степенным диаграммам; вторичные политопы дуальны к вторичным степенным диаграммам. Вторичная степенная диаграмма – это разбиение на ячейки пространства допустимых высот в (8), где каждая ячейка соответствует взвешенной триангуляции Делоне (когерентной триангуляции) $Y$. Подробности можно найти в теории вторичных степенных диаграмм (см. [17]).

Фиксируя триангуляцию $(Y,\operatorname{Conv} (Y))$ $T$, симплекс $\sigma \in T$ имеет объем $\operatorname{vol} (\sigma )$. Учитывая вектор высоты ${\mathbf{h}}$, линейная функция ${{\pi }_{T}}({\mathbf{h}})$ определяется следующим образом:

Теорема 6 (вторичная степенная диаграмма). Для заданной конфигурации точек $Y = \{ {{y}_{1}}, \ldots ,{{y}_{k}}\} \subset {{\mathbb{R}}^{n}}$ выпуклая область $\Omega \subset {{\mathbb{R}}^{n}}$, содержащая начало координат, имеет следующие свойства: $1)$ Для каждой невырожденной взвешенной триангуляции Делоне $T \in \mathcal{T}(Y)$, если ячейка ${{D}_{T}}$ непустая, то она выпуклая. Более того, если $h \in {{D}_{T}}$, то $\lambda h \in {{D}_{T}}$ для всех $0 < \lambda < 1$. $2)$ Разбиение на ячейки пространства степенных диаграмм Александрова

есть степенная диаграмма, полученная проекцией верхней оболочки где гиперплоскость ${{\pi }_{T}}({\mathbf{h}}) \subset {{\mathbb{R}}^{{k + 1}}}$ – объем триангуляции $T$ в $(10)$. $3)$ Если $T$ – невырожденная когерентная триангуляция $T \in \mathcal{T}(Y)$, то ${{D}_{T}}$ непуста.

4.1. Сингулярное множество

Теорема 7 (регулярность Фигалли, см. [18]). Пусть $\Omega ,\Lambda \subset {{\mathbb{R}}^{d}}$ – два ограниченных открытых множества, $f,g:{{\mathbb{R}}^{d}} \to {{\mathbb{R}}^{ + }}$ – две плотности вероятности, которые равны нулю вне $\Omega ,\Lambda $ и ограничены от нуля и бесконечности на $\Omega ,\Lambda $ соответственно. Пусть $T = \nabla u:(\Omega ,fdx) \to (\Lambda ,gdy)$ – оптимальное транспортное отображение, определяемое теоремой Бренье. Тогда существуют два относительно замкнутых множества ${{\Sigma }_{\Omega }} \subset \Omega $ и ${{\Sigma }_{\Lambda }} \subset \Lambda $ с $\left| {{{\Sigma }_{\Omega }}} \right| = \left| {{{\Sigma }_{\Lambda }}} \right| = 0$ такие, что $T:\Omega {{\backslash }}{{\Sigma }_{\Omega }} \to \Lambda {{\backslash }}{{\Sigma }_{\Lambda }}$ является гомеоморфизмом класса $C_{{{\text{loc}}}}^{{0,\alpha }}$ для некоторого $\alpha > 0$.

Как показано на фиг. 7, область $\Omega $ – единичный диск, область $\Lambda $ имеет две связные компоненты. Обе функции плотности $f,\;g$ являются константами, а меры вероятности – равномерными распределениями. Оптимальное транспортное отображение $T$ является градиентным отображением потенциала Бренье $u:\Omega \to \mathbb{R}$. Множество сингулярностей ${{\Sigma }_{\Omega }}$ – это цикл внутри $\Omega $, образ $\Omega {{\backslash }}{{\Sigma }_{\Omega }}$ покрывает $\Lambda $. На виде снизу легко увидеть, что потенциал Бренье ${{C}^{1}}$ почти везде, кроме ${{\Sigma }_{\Omega }}$, где потенциал только ${{C}^{0}}$. Сингулярное множество ${{\Sigma }_{\Omega }}$ представляет собой граф, который можно разложить на дуги и точки ветвления. Возьмем точку сингулярного множества $x \in {{\Sigma }_{\Omega }}$, если $x$ находится внутри дуги, то субдифференциал $\partial u(x)$ – это отрезок прямой; если $x$ – точка ветвления, то $\partial u(x)$ – это выпуклое множество размерности $2$.

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

Определение 4 (степенная медиальная ось). Пусть $\Lambda \subset {{\mathbb{R}}^{d}}$ – область в евклидовом пространстве, $h:\Lambda \to \mathbb{R}$ – выпуклая функция, которая определяет степенное расстояние как в (5),

Для каждой точки $x \in {{\mathbb{R}}^{d}}$, ближайшая точка $\Lambda $ к $x$ определяется как степенная медиальная ось определяется как

Предложение 1 (сингулярное множество). Пусть $\Omega ,\Lambda \subset {{\mathbb{R}}^{d}}$ – компактные области с абсолютно непрерывными мерами $\mu $ и $\nu $, $\partial \Omega $ имеет нулевую меру Лебега. Стоимость транспортировки является квадратичным евклидовым расстоянием. Пусть $u:\Omega \to \mathbb{R}$ – потенциал Бренье, $\nabla u:\Omega \to \Lambda $ – оптимальное транспортное отображение. $u{\kern 1pt} *:\Lambda \to \mathbb{R}$ – дуал Лежандра для $u$, тогда сингулярное множество оптимального транспортного отображения задается следующим образом:

Доказательство. Пусть функция стоимости $c(x,y) = \langle x,y\rangle $. Пусть ${{x}_{0}} \in \Omega $, ${{y}_{0}} \in \Lambda $ и ${{y}_{0}} \in \partial u$, тогда

Поэтому для любого $y \in \Lambda $Это означает, что для всех $y \in \Lambda $, ${\text{po}}{{{\text{w}}}_{{u{\kern 1pt} *}}}({{x}_{0}},{{y}_{0}}) \leqslant {\text{po}}{{{\text{w}}}_{{u{\kern 1pt} *}}}({{x}_{0}},y)$, поэтому ${{y}_{0}} \in {\text{C}}{{{\text{l}}}_{\Lambda }}({{x}_{0}},u{\kern 1pt} *)$. А именно, ${{y}_{0}}$ является ближайшей точкой в $\Lambda $ (по степенному расстоянию) к ${{x}_{0}}$, оптимальное транспортное отображение $T$ отображает каждую точку ${{x}_{0}}$ в $\Omega $ на ближайшую точку ${{y}_{0}}$ в $\Lambda $. И наоборот, если ${{y}_{0}} \in \Lambda $ является ближайшей точкой к ${{x}_{0}} \in \Omega $, то ${{y}_{0}} \in \partial u({{x}_{0}})$.

Предположим, что $x \in \Omega $, и $x$ находится на степенной медиальной оси $\Lambda $, $x \in {{\mathcal{M}}_{\Lambda }}(u{\kern 1pt} *)$, тогда она имеет две ближайшие точки ${{y}_{1}},{{y}_{2}} \in \Lambda $, следовательно, ${{y}_{1}},{{y}_{2}} \in \partial u(x)$; $u$ не дифференцируема на $x$, $x$ является сингулярностью $u$. Тогда имеем

И наоборот, если предположить, что $x \in {{\Sigma }_{\Omega }}$, то $\partial u(x)$ имеет, по крайней мере, две точки ${{y}_{1}},{{y}_{2}} \in \Lambda $, которые ближе всего к $x$ и имеют равные степенные расстояния. Следовательно, $x$ лежит на степенной медиальной оси $\Lambda $, тогда имеем Следовательно, уравнение (13) выполняется. Предложение 1 доказано.

4.2. Алгоритм построения сингулярного множества

Предположим, что $\Omega ,\Lambda \subset {{\mathbb{R}}^{d}}$ – компактные области, $\Omega $ – выпуклая область. Мы плотно сэмплируем границу и внутренность $\Lambda $, выборки обозначаются как $Y = \{ {{y}_{1}}, \ldots ,{{y}_{n}}\} $. Граничные выборки триангулируются, образуя многогранную гиперповерхность, обозначаемую $\partial Y$. Тогда $\partial Y$ аппроксимирует граничную поверхность $\Lambda $, $\partial \Lambda $. При заданных степенях $\{ {{w}_{1}}, \ldots ,{{w}_{n}}\} $, или, эквивалентно, высоте ${\mathbf{h}} = ({{h}_{1}}, \ldots ,{{h}_{n}})$ степенная диаграмма обозначается ${{\mathcal{D}}_{Y}}({\mathbf{h}})$, как определено в уравнении (4). Степенная медиальная ось задается объединением граней ${{f}_{{ij}}}$ коразмерности $1$, которые являются пересечениями двух степенных ячеек Вороного ${{W}_{i}}({\mathbf{h}})$ и ${{W}_{j}}({\mathbf{h}})$, соответствующие ${{y}_{i}}$ и ${{y}_{j}}$ находятся в граничном многограннике $\partial Y$, но не являются смежными ${{y}_{i}}\not {\sim }{{y}_{j}}$ в $\partial Y$,

Сингулярное множество дискретного оптимального транспортного отображения есть

На фиг. 8 показана степенная медиальная ось, полученная с помощью этого алгоритма, где $\Omega $ – единичный диск, $\Lambda $ – плоский многоугольник в форме острова с двумя соединенными компонентами. Мы плотно сэмплируем внутреннюю часть и границу $\Lambda $, чтобы получить дискретное множество точек $Y = \{ {{y}_{i}}\} _{{i = 1}}^{n}$. Граничные выборки последовательно соединяются, образуя $\partial Y$. Определим все степени равными нулю, $\{ {{r}_{i}} = 0\} _{{i = 1}}^{n}$, что эквивалентно $\{ {{h}_{i}} = {\text{|}}{{y}_{i}}{\kern 1pt} {{{\text{|}}}^{2}}{\text{/}}2\} _{{i = 1}}^{n}$. Тогда на фиг. 8а показана диаграмма Вороного для $Y$, синий график – условная медиальная ось. На фиг. 8в, г красными линиями показаны недифференцируемые точки на графике потенциала Бренье. Если изменить высоту, то степенная медиальная ось (сингулярности оптимального транспортного отображения) может быть получена с помощью того же самого алгоритма.

4.3. Эквивалентность гомотопии сингулярного множества

Для оптимального транспортного отображения $T = \nabla u:(\Omega ,\mu ) \to (\Lambda ,\nu )$, если мы изменим целевую меру $\nu $, оптимальное транспортное отображение $T$ изменится соответствующим образом. Можно показать, что сингулярные множества оптимальных транспортных отображений гомотопны друг другу. Сначала покажем это в дискретной постановке, а затем обобщим на устойчивость оптимальных транспортных отображений.

Определение 5 (сумма Минковского). Предположим, что $A$ и $B$ – подмножества на ${{\mathbb{R}}^{n}}$. Их сумма Минковского определяется как $A \oplus B: = \{ p + q\,{\text{|}}\,p \in A,q \in B\} .$

Теорема 8 (гомотопия сингулярных множеств). Имея выпуклую область $\Omega \subset {{\mathbb{R}}^{d}}$ и дискретное множество точек $Y = \{ {{y}_{i}}\} _{{i = 1}}^{n}$, фиксируем исходную меру $\mu $, функция плотности которой абсолютно непрерывна. Целевая мера $\nu = \sum\nolimits_{i = 1}^n \,{{\nu }_{i}}\delta (y - {{y}_{i}})$, ${{\nu }_{i}} > 0$, $i = 1,2, \ldots ,n$, такая, что $\mu (\Omega ) = \sum\nolimits_{i = 1}^n \,{{\nu }_{i}}$. Если даны две целевые меры ${{\nu }_{0}}$ и ${{\nu }_{1}}$, соответствующие им высоты ${{{\mathbf{h}}}_{0}}$ и ${{{\mathbf{h}}}_{1}}$, то их сингулярные множества гомотопически эквивалентны друг другу: ${{\Sigma }_{\Omega }}({{{\mathbf{h}}}_{0}})\sim {{\Sigma }_{\Omega }}({{{\mathbf{h}}}_{{\mathbf{1}}}}).$

Теорема 4 показывает, что пространство допустимых высот ${{\mathcal{H}}_{Y}}$ в уравнении (8) выпукло, поэтому отрезок, соединяющий ${{{\mathbf{h}}}_{0}}$ и ${{{\mathbf{h}}}_{1}}$, содержится в ${{\mathcal{H}}_{Y}}$, $\gamma (t): = (1 - t){{{\mathbf{h}}}_{0}} + t{{{\mathbf{h}}}_{1}}$. Согласно теореме о вторичной степенной диаграмме 6, ${{\mathcal{H}}_{Y}}$ имеет разбиение на ячейки ${{\mathcal{H}}_{Y}} = \bigcup\nolimits_{T \in \mathcal{T}(Y)}^{} {{{\mathcal{D}}_{T}}} $, каждая ячейка соответствует взвешенной триангуляции Делоне (также комбинаторной структуре силовой диаграммы $\Omega $). Предположим, что прямая $\gamma (t)$ пересекает множество ячеек, соответствующих триангуляциям ${{T}_{0}}, \ldots ,{{T}_{k}}$. Тогда единичный интервал делится на отрезки $0 = {{t}_{0}} < \ldots < {{t}_{k}} = 1$, удовлетворяющие следующим условиям:

1) $\gamma (t) \in {{\mathcal{D}}_{{{{T}_{i}}}}}$ $\forall t \in [{{t}_{i}},{{t}_{{i + 1}}}]$,

2) $\gamma ({{t}_{i}}) \in {{\mathcal{D}}_{{{{T}_{i}}}}} \cap {{\mathcal{D}}_{{{{T}_{{i + 1}}}}}}$.

Шаг 1. Для любых $t \in ({{t}_{i}},{{t}_{{i + 1}}})$ все взвешенные триангуляции Делоне $T(\gamma (t))$ имеют одинаковую комбинаторную структуру. Все соответствующие степенные диаграммы также имеют одинаковую комбинаторную структуру. Потенциал Бренье ${{u}_{{\gamma (t)}}}(x) = \mathop {\max }\nolimits_{i = 1}^k \left\{ {\langle {{y}_{i}},r\rangle - \gamma {{{(t)}}_{i}}} \right\}$ может быть записан как линейная комбинация:

где $\lambda = ({{t}_{{i + 1}}} - t){\text{/}}({{t}_{{i + 1}}} - {{t}_{i}})$. Граф потенциала Бренье можно записать в виде линейной комбинации с помощью суммы Минковского: где $G(\gamma (t))$ –  граф функции ${{u}_{{\gamma (t)}}}$. Поэтому,  как  проекция  графов потенциалов Бренье, каждая степенная ячейка может быть представлена в виде суммы Минковского ${{W}_{i}}(\gamma (t)) = \lambda {{W}_{i}}(\gamma ({{t}_{i}})) \oplus (1 - \lambda ){{W}_{i}}(\gamma ({{t}_{{i + 1}}})).$

Это означает, что сингулярное множество также удовлетворяет соотношению линейной комбинации:

Шаг 2. В критической точке ${{t}_{i}}$ мы хотим показать, что

Сначала мы доказываем это для двумерного случая (фиг. 9), доказательство для случаев общей размерности очень похоже. Зададим взвешенную триангуляцию Делоне $T$, выберем два смежных треугольника $[{{v}_{i}},{{v}_{j}},{{v}_{k}}]$ и $[{{v}_{j}},{{v}_{i}},{{v}_{l}}]$. Степенная окружность, связанная с вершиной ${{v}_{i}}$ – $c({{v}_{i}},{{r}_{i}})$, мощность – $r_{i}^{2}$. Тогда для каждого треугольника существует единственная окружность $c(o,r)$ (красная), ортогональная ко всем трем вершинным окружностям, так называемая силовая окружность грани. Степенной центр $o$ и степенной радиус $r$ удовлетворяют следующим условиям:

Как показано на фиг. 9, степенными центрами двух граней являются ${{o}_{k}}$ и ${{o}_{l}}$ соответственно. Отрезок прямой, соединяющий два степенных центра $[{{o}_{k}},{{o}_{l}}]$ на степенной диаграмме, дуален ребру $[{{v}_{i}},{{v}_{j}}]$ во взвешенной триангуляции Делоне.

Вдоль кривой $\gamma (t)$ степени вершин непрерывно меняются. Предположим, что когда $t < {{t}_{i}}$ и приближается к ${{t}_{i}}$, два степенных центра ${{o}_{k}}$ и ${{o}_{l}}$ становятся все ближе и ближе. В критической точке ${{t}_{i}}$ центр ${{o}_{k}}$ совпадает с ${{o}_{l}}$, и триангуляция меняется путем замены ребер $[{{v}_{i}},{{v}_{j}}]$ на $[{{v}_{k}},{{v}_{l}}]$. При дальнейшем увеличении $t$, где $t > {{t}_{i}}$, степенной центр $[{{v}_{k}},{{v}_{i}},{{v}_{l}}]$ и центр $[{{v}_{l}},{{v}_{j}},{{v}_{k}}]$ расходятся. Это показывает, что в критический момент времени ${{t}_{i}}$ край степенной диаграммы $[{{v}_{i}},{{v}_{j}}]$ сжимается до точки и растет до нового края $[{{v}_{k}},{{v}_{l}}]$. Таким образом, степенная диаграмма изменяется непрерывно. Следовательно, сингулярное множество также меняется непрерывно, а значит, уравнение (16) выполняется. Для пространств больших измерений обмен краями заменяется бистеллярным преобразованием (см. [19]), и доказательство остается точно таким же.

Комбинируя шаги 1 и 2, получаем для $0 \leqslant i < k$

следовательно, Теорема 8 доказана.

На фиг. 7 и 8 была показана связь гомотопии между сингулярными множествами оптимальных транспортных отображений для различных целевых мер. Мы видим, что мелкие ветви могут исчезнуть, но петли и крупные ветви хорошо сохраняются. На фиг. 10 показана деформация гомотопии между сингулярными множествами оптимальных транспортных отображений с единичного диска на область в форме морского конька с различными целевыми мерами. В начале мы вычисляем условную медиальную ось, а целевая мера на каждом ${{y}_{i}}$ равна площади соответствующей ячейки. Конечной целевой мерой является равномерное распределение.

Более сложный пример показан на фиг. 11. Вычисляются оптимальные транспортные отображения с плоской спиральной формы на единичный диск, и извлекаются соответствующие сингулярные множества. Видно, что сингулярные множества (степенные медиальные оси) гомотопически эквивалентны друг другу.

В приложениях глубокого обучения набор обучающих данных кодируется в латентное пространство (см. фиг. 3), распределение латентных данных является суммой или мерой Дирака $\nu = {{n}^{{ - 1}}}\sum\nolimits_{i = 1}^n \,\delta (y - \varphi ({{x}_{i}}))$, где $n$ – количество выборок, ${{x}_{i}}$ – обучающая выборка. Оптимальное транспортное отображение может быть вычислено с помощью предложенного алгоритма (см. фиг. 4). Сингулярность на опорном участке распределения белого шума и недифференцируемые точки на потенциале Бренье могут быть легко обнаружены. Полученные результаты можно увидеть на фиг. 2, схлопывание и смешение мод были устранены путем тщательной обработки сингулярностей оптимального транспортного отображения.

5.1. Нормальное расстояние Фреше

Предположим, человек выгуливает свою собаку, он проходит кривую ${{\gamma }_{1}}$, а собака проходит ${{\gamma }_{2}}$ (фиг. 12а). Ни один из них не может двигаться назад. Расстояние Фреше между этими двумя кривыми равно длине самого короткого поводка. Расстояние Фреше дает лучшее измерение близости двух кривых, чем расстояние Хаусдорфа. Возможно, что две кривые имеют малое расстояние Хаусдорфа, но большое расстояние Фреше.

Пусть $M$ – метрическое пространство; замкнутая кривая $\gamma $ в $M$ – непрерывное отображение из единичного круга в $M$, $\gamma :{{\mathbb{S}}^{1}} \to M$; репараметризация $\alpha $ из ${{\mathbb{S}}^{1}}$ – сохраняющий ориентацию гомеоморфизм $\alpha :{{\mathbb{S}}^{1}} \to {{\mathbb{S}}^{1}}$.

Определение 6 (расстояние Фреше). Пусть ${{\gamma }_{1}}$ и ${{\gamma }_{2}}$ – две заданные замкнутые кривые в $M$. Тогда расстояние Фреше ${{d}_{F}}({{\gamma }_{1}},{{\gamma }_{2}})$ между ${{\gamma }_{1}},\;{{\gamma }_{2}}$ определяется как инфимум по всем репараметризациям $\alpha $ и $\beta $ из ${{\mathbb{S}}^{1}}$ максимума по всем $t \in {{\mathbb{S}}^{1}}$ расстояния в $M$ между ${{\gamma }_{1}}(\alpha (t))$ и ${{\gamma }_{2}}(\beta (t))$, а именно,

где ${{d}_{M}}$ – геодезическое расстояние на $M$.

На фиг. 13 прямое произведение ${{\gamma }_{1}} \times {{\gamma }_{2}}$ представлено в виде тора ${{T}^{2}}: = {{\mathbb{S}}^{1}} \times {{\mathbb{S}}^{1}}$. На торе есть два канонических отображения широты и долготы:

Диагональ обозначается как $\Delta = \{ (p,p) \in {{\mathbb{S}}^{1}} \times {{\mathbb{S}}^{1}}\} $. Гомеоморфизм между ${{\gamma }_{1}}$ и ${{\gamma }_{2}}$ есть $\varphi :{{\mathbb{S}}^{1}} \to {{\mathbb{S}}^{1}}$, представленный в виде замкнутой кривой ${{\Gamma }_{\varphi }} \subset {{T}^{2}}$: которая гомотопна $\Delta $. Более того, ${{\Gamma }_{\varphi }}$ имеет одно и только одно пересечение с каждым из листьев в ${{\mathcal{F}}_{1}}$ или в ${{\mathcal{F}}_{2}}$. Все кривые такого вида представляют все гомеоморфизмы между ${{\gamma }_{1}}$ и ${{\gamma }_{2}}$.

Определение 7 (пространство отображения). Пространство отображения между ${{\gamma }_{1}}$ и ${{\gamma }_{2}}$, обозначаемое как $H({{\gamma }_{1}},{{\gamma }_{2}})$, есть множество всех замкнутых кривых $\Gamma \subset {{T}^{2}}$, которое

1) гомотопно диагонали $\Delta $,

2) пересекает каждый из листьев в ${{\mathcal{F}}_{1}}$ в одной точке,

3) пересекает каждый из листьев в ${{\mathcal{F}}_{2}}$ в одной точке.

Мы можем представить фундаментальную область тора в виде квадрата, тогда $\Gamma \in H({{\gamma }_{1}},{{\gamma }_{2}})$, если и только если кривая монотонна как в горизонтальной, так и в вертикальной координатах.

Определение 8 (свободное пространство Фреше). Учитывая замкнутые кривые ${{\gamma }_{1}},\;{{\gamma }_{2}}$ в метрическом пространстве $M$ и константу $\varepsilon > 0$, свободное пространство между ${{\gamma }_{1}}$ и ${{\gamma }_{2}}$ определяется как

Как показано на фиг. 12б, каждая  точка $(s,t)$ на  торе имеет  красный цвет, если расстояние  между  соответствующими  точками ${{\gamma }_{1}}(s)$ и ${{\gamma }_{2}}(t)$  больше $\varepsilon $, а белый иначе. Гомеоморфизм $\varphi :{{\gamma }_{1}} \to {{\gamma }_{2}}$ показан синей кривой в свободном пространстве, что подразумевает ${{d}_{M}}({{\gamma }_{1}}(s),{{\gamma }_{2}} \circ \varphi (s)) < \varepsilon $, для всех $s \in {{\mathbb{S}}^{1}}$. Следующее предложение 2 очевидно.

Предложение 2. Расстояние Фреше между ${{\gamma }_{1}}$ и ${{\gamma }_{2}}$ меньше $\varepsilon $, если и только если существует кривая $\Gamma $ в пространстве отображений $H({{\gamma }_{1}},{{\gamma }_{2}})$, и $\Gamma $ также находится в свободном пространстве Фреше ${{F}_{\varepsilon }}({{\gamma }_{1}},{{\gamma }_{2}})$.

5.2. Нормальное расстояние Фреше

Предположим, что $\gamma :{{\mathbb{S}}^{1}} \to {{\mathbb{R}}^{2}}$ – замкнутая плоская кривая, $\gamma $ – ${{C}^{1}}$, поэтому нормаль везде определена. Кривая параметризуется длиной дуги $\gamma (s)$, единичная внешняя нормаль на $\gamma (s)$ представлена как $n(s) = (\cos \theta (s),\sin \theta (s))$, $\theta \in [0,2\pi )$. Гауссово отображение $G:\gamma \to {{\mathbb{S}}^{1}}$ отображает каждую точку $\gamma (s)$ на нормаль $n(s)$.

Определение 9 (нормальное расстояние Фреше). Пусть ${{\gamma }_{1}},{{\gamma }_{2}}\,:$ ${{\mathbb{S}}^{1}} \to {{\mathbb{R}}^{2}}$ – замкнутые ${{C}^{1}}$-кривые на плоскости. Нормальное расстояние Фреше между ними определяется как расстояние Фреше между их образами отображения Гаусса на единичной окружности ${{\mathbb{S}}^{1}}$, а именно,

где ${{d}_{{{{\mathbb{S}}^{1}}}}}$ – расстояние ${{\mathbb{S}}^{1}}$, $\alpha ,\beta :{{\mathbb{S}}^{1}} \to {{\mathbb{S}}^{1}}$ – репараметризация ${{\mathbb{S}}^{1}}$.

Аналогично, мы можем определить нормальное свободное пространство между ${{\gamma }_{1}}$ и ${{\gamma }_{2}}$.

Определение 10 (нормальное свободное пространство). Пусть ${{\gamma }_{1}},{{\gamma }_{2}}:{{\mathbb{S}}^{1}} \to {{\mathbb{R}}^{2}}$ – замкнутые ${{C}^{1}}$-кривые на плоскости. При фиксированном $\varepsilon > 0$ нормальное свободное пространство между ${{\gamma }_{1}}$ и ${{\gamma }_{2}}$ определяется как

где $G:\gamma \to {{\mathbb{S}}^{1}}$ – отображение Гаусса.

Предложение 3. Пусть ${{\gamma }_{1}},{{\gamma }_{2}} \subset {{\mathbb{R}}^{2}}$ – две замкнутые ${{C}^{1}}$-кривые, где ${{\gamma }_{1}}$ параметризуется длиной дуги, а ${{\gamma }_{2}}$ – строго выпуклая, параметризуемая обратным отображением Гаусса. Нормальное расстояние Фреше между ${{\gamma }_{1}}$ и ${{\gamma }_{2}}$ меньше $\varepsilon $, если и только если существует кривая $\Gamma $ в пространстве отображений $H({{\gamma }_{1}},{{\gamma }_{2}})$, и $\Gamma $ также находится в нормальном свободном пространстве Фреше ${{F}_{{n,\varepsilon }}}({{\gamma }_{1}},{{\gamma }_{2}})$.

Дoказательство. В соответствии с определениями пространства отображения и нормального расстояния Фреше доказательство является простым.

Форма плоской ${{C}^{2}}$-кривой определяется исключительно ее кривизной, поэтому нормальное расстояние Фреше определяется кривизной обеих кривых ${{\gamma }_{1}}$ и ${{\gamma }_{2}}$. Для данной цели мы рассмотрим только простой случай, когда ${{\gamma }_{2}}$ является строго выпуклой кривой, такой как единичный круг ${{\mathbb{S}}^{1}}$, который параметризуется обратным значением его отображения Гаусса.

Лемма 1 (условие кривизны). При тех же гипотезах предложения $3$, если существует сегмент кривой $\gamma \subset {{\gamma }_{1}}$, начинающийся из $p$ и заканчивающийся в $q$, удовлетворяющий $s(q) > s(p)$ и

где $s$ – параметризация длины дуги ${{\gamma }_{1}}$, а $\theta $ – образ отображения Гаусса, т.е. угол единичной внешней нормали, тогда нормальное расстояние Фреше между ${{\gamma }_{1}}$ и ${{\gamma }_{2}}$ больше $\pi {\text{/}}2$, ${{d}_{{{{F}_{n}}}}}({{\gamma }_{1}},{{\gamma }_{2}}) > \pi {\text{/}}2$.

Более того, если $\gamma $ является ${{C}^{2}}$, то условие (18) можно заменить следующим условием кривизны:

где $\kappa $ – знаковая кривизна $\gamma $ относительно направленного внутрь единичного нормального вектора.

Доказательство. Предположим, что $\tau $ – произвольный отрезок ${{\gamma }_{2}}$, $\tau \subset {{\gamma }_{2}}$. Построим нормальное свободное пространство между $\gamma $ и $\tau $, как показано на фиг. 14. Заметим, что когда $\gamma $ является ${{C}^{2}}$, (19) подразумевает (18) как из (19),

поэтому достаточно рассмотреть (18).

Нормальное свободное пространство – это зеленая область в прямоугольнике, $p$ и $q$ соответствуют нижнему и верхнему краю. Из (20) имеем, что левый нижний угол и правый верхний угол зеленой области разделены вертикальной линией, следовательно, любая кривая, содержащаяся в зеленой области, не может быть монотонно возрастающей (заметим, что вертикальная линия исключается определением 7). Это показывает, что любой гомеоморфизм $\varphi :\gamma \to \tau $ и его граф ${{\Gamma }_{\varphi }}$ должны пересекать красную область. Поэтому нормальное расстояние Фреше между ${{\gamma }_{1}}$ и ${{\gamma }_{2}}$ должно быть больше, чем $\pi {\text{/}}2$. Лемма 1 доказана.

5.3. Скошенность

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

Лемма 2 (скошенность). Пусть $\Omega ,\Omega {\kern 1pt} * \subset {{\mathbb{R}}^{n}}$ – ограниченные области, $\Omega $ – выпуклая, $\partial \Omega {\kern 1pt} *$ – ${{C}^{1}}$. Функции плотности $f$ и $g$ удовлетворяют условию равновесия $\int_\Omega ^{} f = \int_{\Omega {\kern 1pt} *}^{} g $ и ограничены, $0 < {{c}_{0}} < f,$ $g < {{c}_{1}} < \infty $, потенциал Бренье $u:\Omega \to \mathbb{R}$, его дуал Лежандра $u{\kern 1pt} *:\Omega {\kern 1pt} * \to \mathbb{R}$. Предположим, что $x \in \partial \Omega $ и $y \in \partial \Omega {\kern 1pt} *$, $Du(x) = y$, тогда

Доказательство. Предположим обратное, как показано на фиг. 15, существует $x \in \partial \Omega {\kern 1pt} *$ и $y \in \partial \Omega $, $\langle n(x),n(y)\rangle < 0$, тогда $\langle - n(x),n(y)\rangle \geqslant 0$. Пусть $z = x - \varepsilon n(y)$, имеем $z \in \Omega {\kern 1pt} *$ для достаточно малого $\varepsilon > 0$. По предположению $\nabla u{\kern 1pt} *(z) \in \Omega $. Тогда в силу выпуклости $u{\kern 1pt} *$

Получаем противоречие тому, что $\nabla u{\kern 1pt} *{\kern 1pt} (z) \in \Omega $ является внутренней точкой. Лемма 2 доказана.

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

Лемма 3. Предположим, что $\Omega ,\Omega {\kern 1pt} * \subset {{\mathbb{R}}^{2}}$ – ограниченные открытые области, $\Omega $ – выпуклая, $\partial \Omega {\kern 1pt} *$ есть ${{C}^{1}}$-кривая, функции плотности

Если потенциал Бренье $u$ не имеет сингулярности на $\bar {\Omega }$, то $Du$, ограниченный на границе ${{\left. {Du} \right|}_{{\partial \Omega }}}:\partial \Omega \to \partial \Omega {\kern 1pt} *$, является гомеоморфным.

Доказательство. Пусть $v$ – дуал Лежандра от $u$, $v(y): = {{\sup }_{{x \in \Omega }}}\langle x,y\rangle - u(x)$,

тогда по двумерной теории регулярности, $\tilde {v} \in {{C}^{1}}(\overline {\Omega {\kern 1pt} *} )$, $Du \circ D\tilde {v} = {\text{id}}$. Это показывает, что $Du$ является гомеоморфизмом из $\bar {\Omega }$ в $\overline {\Omega {\kern 1pt} *} $.

Теперь мы можем привести доказательство следующей теоремы, которая показывает существование сингулярности оптимального транспортного отображения между плоскими областями. Эта теорема впервые была получена в [20], доказательство здесь намного проще.

Теорема 9 (существование сингулярности). Пусть $\Omega ,\Omega {\kern 1pt} * \subset {{\mathbb{R}}^{2}}$ – ограниченные области, $\Omega $ – выпуклая, $\partial \Omega {\kern 1pt} *$ есть ${{C}^{1}}$-кривая, и существует отрезок $\gamma \subset \partial \Omega {\kern 1pt} *$ такой, что

тогда для любых функций плотности $f$ и $g$, удовлетворяющих условию равновесия $\int_\Omega \,f = \int_{\Omega {\kern 1pt} *} \,g$ и ограниченных, $0 < {{c}_{0}} < f,$ $g < {{c}_{1}}$, оптимальное транспортное отображение должно иметь непустое сингулярное множество в $\bar {\Omega }$.

Доказательство. Предположим, что существуют функции плотности $f,\;g$, удовлетворяющие условию равновесия $\int \,f = \int \,g$ и условию ограниченности $0 < {{c}_{0}} < f,$ $g < {{c}_{1}}$, соответствующий потенциал Бренье равен $u$, такой, что оптимальное транспортное отображение $Du$ не имеет сингулярности на $\bar {\Omega }$.

По лемме 3 ограничение $Du$ на границу $\partial \Omega $ является гомеоморфизмом. По лемме 2 для любых $p \in \partial \Omega $, $Du(p) \in \partial \Omega {\kern 1pt} *$, $\langle n(p),Du(p)\rangle \geqslant 0$. Поэтому ${{F}_{n}}(\partial \Omega ,\partial \Omega {\kern 1pt} *) \leqslant \pi {\text{/}}2$.

По лемме 1 и условию кривизны (22) ${{F}_{n}}(\partial \Omega ,\partial \Omega {\kern 1pt} *) > \pi {\text{/}}2$ получаем противоречие. Следовательно, предположение неверно для любых функций плотности $f,\;g$, удовлетворяющих условию равновесия и условию ограниченности, оптимальное транспортное отображение $Du$ должно иметь сингулярности в $\bar {\Omega }$.