Эффективный алгоритм Синкхорна с использованием матриц Теплица и применения

Задача оптимального транспорта нахождения расстояния между двумя вероятностными мерами является важной темой в современной математике, которая дает основу для различных приложений в машинном обучении и статистике, включая глубокие генеративные модели. Основным предметом данной диссертации является эффективная модификация численного алгоритма решения регуляризационной задачи оптимального транспорта для дискретных мер, ее анализ и применение к задаче генерации расчетных сеток. Ключевой модификацией является использование блочных матриц Теплица, которые возникают в случае дискретизации произвольной меры на фиксированной регулярной сетке. Это приводит к значительному ускорению произведения матрицы на вектор в итерации алгоритма Синкхорна, к меньшему потреблению памяти и позволяет найти отображение для достаточно мелких сеток, например, размером $2^{24}$, за допустимое время. Проведенные численные эксперименты иллюстрируют эффективность метода по сравнению с классическим алгоритмом Синкхорна.