Тензорные методы аппроксимации негладких функций многих переменных для задач численного моделирования тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Бойко Алексей Игоревич

• Бойко Алексей Игоревич
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Бойко Алексей Игоревич

Введение

Глава 1. Малоранговые тензорные разложения

1.1 Общие обозначения

1.2 Малоранговое разложение матриц

1.3 Тензорный Поезд (Tensor Train, TT)

1.3.1 Определения и вычислительная сложность

1.3.2 ТТ-матрица (Tensor Train Matrix)

1.4 QTT-разложение

1.5 Разложение Таккера

1.6 TT-SVD

1.7 TT-Cross

1.8 AMEn

1.9 Выводы по главе

Глава 2. Задача рассеяния волн в частотной области

2.1 Введение

2.2 Малоранговые методы в вычислительной электродинамике

2.3 Уравнение Липпмана-Швингера

2.3.1 Математическая постановка задачи рассеяния

2.3.2 Дискретизация уравнения

2.4 Тензорное сжатие уравнения

2.4.1 Сжатие функции Грина

2.4.2 Сжатие остальных частей уравнения

2.5 Численные эксперименты

2.5.1 Время решения

2.5.2 Погрешность численного решения

2.5.3 Масштабирование от частоты

2.6 Заключение по главе

Глава 3. Задача стохастического оптимального управления и

уравнение Беллмана

3.1 Введение

3.2 Задача стохастического оптимального управления

3.3 Аппроксимация марковским процессом принятия решений

3.4 Уравнение Беллмана

3.4.1 Итерация функции ценности в формате тензорного поезда

3.4.2 Q-итерация в формате тензорного поезда

3.5 Численные эксперименты

3.5.1 Система 1: непериодический обратный маятник

3.5.2 Система 2: машина Дубинса

3.6 Сравнение производительности

3.7 Заключение

Глава 4. Знаковая функция расстояния и неявное

представление трёхмерной геометрии

4.1 Введение

4.2 Взаимосвязь SDF и уравнения Эйконала

4.3 Исторический очерк

4.4 О сжатии SDF и TSDF

4.5 TSDF Fusion и его имплементация с компрессией

4.6 Численные эксперименты

4.6.1 Тест на синтетических данных

4.6.2 Метрика Intersection over Union (IoU)

4.6.3 Метрика расстояние Хаусдорфа

4.6.4 Метрика расстояние Чамфера

4.6.5 Тест на реальных данных

4.7 Патент и расширение алгоритма

4.8 Заключение по главе

Заключение

Список литературы

Список литературы

Список рисунков

Список таблиц

Приложение А. Свидетельство о выдаче патента

Введение

Введение диссертации (часть автореферата) на тему «Тензорные методы аппроксимации негладких функций многих переменных для задач численного моделирования»

Актуальность темы

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

В современных областях предсказательного моделирования, таких как глубокое машинное обучение (deep learning) приближение решений многомерных (в т.ч. нелинейных) уравнений в частных производных также встречаются довольно часто (хоть обычно и не указывается в явном виде). Примером служит область глубокого обучения с подкреплением [55; 57; 72], где искомая с помощью предиктивных подходов Функция Ценности есть ничто иное, как решение уравнений Гамильтона-Якоби-Беллмана (в случае систем с непрерывными степенями свободы). Ещё одним примером служат задачи трёхмерной графики и современного трёхмерное компьютерного зрения, где форма объектов ищется в виде своей знаковой функции расстояния [17; 48], которая является решением определенной краевой задачи уравнения эйконала.

Классические методы аппроксимации функций многих переменных (с помощью линейной комбинации базисных функций) позволяют находить решения уравнений в частных производных с очень высокой, а главное, контролируемой точностью. Однако, они подвержены так называемому «проклятию размерности». Это связано с тем обстоятельством, что решение, как правило, ищется на области вида Q С Rd, что при дискретизации масштабируется как 0(Nd) и по вычислительной сложности, и по памяти. Такая сложность полиномиально зависит от мелкости разбиения N и экспоненциально - от размерности задачи d. Это известная проблема в численных методах, существенно ограничивающая возможность вычислять решения для задач высокой размерности, либо для задач на сверх-мелких сетках.

Вторым большим классом аппроксиматоров, который получает все большее распространение, являются нейронные сети, начиная с простых многослойных перцептронов и заканчивая более современными специализированными архитектурами для физических задач, такие как Physics-Informed Neural Networks [45; 58] или архитектуры с фурье-признаками, как Positional Encoding [3; 25] и SIREN [37]. Такие функциональные приближения можно «обучать» удовлетворять определенному уравнению, и они действительно могут приближать искомую функцию с достаточно высокой точностью (в статистическом смысле, то есть на конечной случайной выборке точек). При этом нейронные сети требуют гораздо меньше памяти, а также не страдают от «проклятия размерности», в отличие от «честных» способов приближения, основанных на разложении по сеточному либо конечно-элементному базису. У нейронных сетей, однако, существует проблема отсутствия гарантии сходимости к истинному решению, а также отсутствия гарантированных оценок на точность приближения решения.

В данной диссертации рассматривается класс функциональных аппроксиматоров, который сочетает черты конечно-разностых и нейросетевых методов - малоранговые тензорные разложения (тензорные сети) [29; 43]. В отличие от нейронных сетей, малоранговые тензорные разложения зачастую имеют доказанные верхние оценки ошибки аппроксимации, а также для них доступна большая часть классического инструментария вычислительных методов (алгебраические операции над сжатыми тензорами, вычисление матрично-векторных произведений). В дополнение к этому, тензорные представления могут быть «обучены» теми же стандартными методами обратного распространения ошибки как и обычные нейронные сети [69]. К сожалению, в отличие от нейронных сетей [16; 35], для малоранговых тензорных разложений не существует универсальной теоремы аппроксимации, т.е. нет гарантий, что любая функция (на сетке), являющаяся решением физического уравнения может быть достаточно близко приближена малоранговым разложением.

Цели и задачи

Целью данной работы является расширение ряда малоранговых методов решения численных задач, подверженных ограничениям «проклятия размерности». В частности, решаются следующие задачи:

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

2. разработать более быстрый, чем имеющийся в литературе, метод решения задачи оптимального управления достаточно общего вида (нелинейные не аффинные системы, произвольная функция награды, наличие внешнего шума в системе). Метод должен работать на бортовых вычислителях малой мощности. Исследовать поведение малоранговой тензорной аппроксимации в случае многомерных задач.

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

Теоретическая значимость

— В первой статье [9] показано, что постановка уравнения Липпмана-Швингера в формате QTT может достигать рекордно низкой (полилогарифмической) сложности 0(logp N) от размера дискретизации

— Во второй статье [8] предложена новая версия алгоритма итерации функции ценности (Value Iteration) в малоранговом тензорном формате. Доказано, что (при выполнении некоторых условий) наш алгоритм имеет меньшую вычислительную сложность от ТТ-рангов функции ценности, чем алгоритм, известный из литературы.

Практическая значимость

— Первая статья [9] представляет практический метод решения задачи рассеяния (уравнения Липпмана-Швингера) полностью в QTT такой, что общая сложность составляет О (logp N) вместо О (N log N). В случае, если функция распределения диэлектрической проницаемости имеет малые QTT-ранги, данный алгоритм (и соответствующий код) позволяет решать многомасштабные задачи на очень мелких сетках даже на обычном ноутбуке. Данная формулировка была в дальнейшем использована другими авторами и усовершенствована

на более общие распределения диэлектрической проницаемости в публикации в ведущем издании области IEEE Transactions on Microwave Theory and Techniques [64].

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

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

Основные положения, выносимые на защиту:

1. Предложен метод решения задач рассеяния волн на неоднородных мультимасштабных объектах за полилогарифмическое время от размера разбиения сетки

2. Предложен алгоритм TT-QI численного решения задачи стохастического оптимального управления для стохастических динамических управляемых систем (случайных процессов) в тензорном формате. Доказана более низкая сложность на итерацию.

3. Предложен алгоритм TT-TSDF для компактного представления разрывных трёхмерных функций сложной формы (в частности, функций-индикаторов) на трёхмерной сетке, и анализ его производительности для сжатия синтетических трёхмерных моделей, неполных трёхмерных карт (сканов) местности из робототехники, а также представления разрывных трёхмерных данных компьютерной томографии из задач нефтегазовой геологии.

Обоснование специальности

Данная диссертация по своей тематике и направленности полученных результатов соответствует следующим пунктам паспорта специальности 1.2.2 «Математическое моделирование, численные методы и комплексы программ»:

— (1) Разработка новых математических методов моделирования объектов и явлений.

— (3) Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий.

— (4) Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента.

— (5) Комплексные исследования научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента.

Апробация работы

Основные результаты докладывались и обсуждались на следующих конференциях и научных школах:

1. Римско-Московская Школа по матричным методам и прикладной линейной алгебре, 2016, Университет Тор Вергата, Рим, Италия и МГУ, Москва, Россия

2. Научно-практическая конференция компании Cadence, 2017, Москва

3. Летняя Школа "Нанофотоника и Метаматериалы 2017, ИТМО, Санкт-Петербург

4. Progress In Electromagnetics Research Symposium - Spring 2017, Санкт-Петербург

5. Skoltech-MIT Conference: "Shaping the Future: Big Data, Biomedicine and Frontier Technologies", 2017, Москва

6. Gen-Y conference of Skoltech - 2019, г.Сочи

7. The 5th International Conference on Matrix Methods in Mathematics -2019, Москва

8. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2020, virtual

Содержание работы

Первая глава является вводной и посвящена описанию математического аппарата малоранговых тензорных разложений. Вторая глава посвящена применению QTT-разложения для решения интегральной формы задачи рассеяния волн на сверх-мелких сетках, необходимых, в частности, для решения многомасштабных задач фотоники. Третья глава посвящена применению ТТ-разложения к решению уравнения Беллмана, возникающего при дискретизации задач стохастического оптимального управления робота с несколькими степенями свободы с помощью марковского процесса принятия решений. В четвертой главе приведено описание метода ТТ-аппроксимации на сетке разрывных функций-индикаторов сложной формы в трёхмерном пространстве, а также его применение для компактного представления трёхмерных объектов и сцен в контексте задач компьютерного зрения и робототехники.

Личный вклад автора. Все материалы и результаты главы 2 были полностью получены автором при научном руководстве д.ф-м.н. И.В. Оселедца и д.ф-м.н. Н.А.Гиппиуса. Все материалы и результаты главы 3 были полностью получены автором при научном руководстве д.ф-м.н. И.В. Оселедца и Ph.D. Г.Феррера. Основной результат главы 4 был получен автором при научном руководстве д.ф-м.н. И.В. Оселедца и Ph.D. Г.Феррера, часть кода для численных экспериментов и часть текста публикации были написаны совместно с М.П.Матросовым.

Объем и структура работы Диссертация состоит из введения, 4 глав, заключения и 1 приложения. Полный объём диссертации составляет 95 страниц, включая 30 рисунков и 6 таблиц. Список литературы содержит 76 наименований.

Глава 1. Малоранговые тензорные разложения

1.1 Общие обозначения

В данной работе термином тензор мы будем обозначать D-мерный массив действительных или комплексных чисел A(ii,..,ij)).

Мультииндекс J = ji..,k = ji,... ,jk определяется, как

J = ji,..., jk = Л + (32 - 1)Ni + • • • + Ok - l)Ni • ... • nk-i. (1.1)

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

J=k = 31,...,3к-1,3к+1,...,3ь (1.2)

J>k = jk+i,...,jd. (1.3) Математические операции:

1. с = a • b - внутреннее произведение по последнему индексу а и первому индексу Ь. В соглашении Эйнштейна обозначается cjj = bkj

2. с = а 0 b - произведение Кронекера. В соглашении Эйнштейна обозначается ciJ = ajbJ

3. с = а © b - адамарово (поэлементное) произведение. В соглашении

¡1,К = I = J

Эйнштейна обозначается ск = bxJJaJbJ, где &kjj = \

[0, ELSE

1.2 Малоранговое разложение матриц

Перед тем, как перейти к малоранговыми разложениям тензоров, рассмотрим для начала малоранговые разложения матриц. Пусть дана функция на квадратной сетке N х N, сохраненная в двухмерном массиве (матрице А). Наша цель - найти такую матрицу А с неполным рангом Я < N, что её отклонение £ относительно матрицы А (в смысле нормы Фробениуса)

минимально:

£ = ||А - Ä||F = - äij)2 — min. (1.4)

у i,j

Согласно теореме Эккарта- Янга, матрица А может быть найдена

усеченным сингулярным разложением матрицы А: А = USV* А = USV*.

В дополнение к этому, квадрат ошибки по норме Фробениуса такого

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

N

отброженных сингулярных чисел £ = ^ а2. Фробениусова норма же, с

i=д+1

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

1.3 Тензорный Поезд (Tensor Train, TT)

1.3.1 Определения и вычислительная сложность

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

Данный метод может быть применен и в случае, когда число переменных у функции более чем 2. Рассмотрим функцию на многомерной сетке размером N1,... ,Nd точек, заданную в виде ^-мерного массива F(i1,... ,id).

Тогда разложением в тензорный поезд (Tensor Train, ТТ-разложением или ТТ-вектором) называется следующее выражение:

П,Г2,...,Гл-!

F (M2,...¿d)= ^ G(1)(n,mi>

(1.5)

•G(2'(mi,¿2,m2) •... • Gw(md-i,id),

где массивы G(k) называются TT-ядрами, а числа Гк называются TT-рангами.

Как было показано в оригинальной статье [54], ТТ-разложение с минимальными возможными компрессионными рангами всегда существует и ядра такого разложения могут быть найдены алгоритмом ТТ-БУЭ

[52]. Ключевой идеей данного алгоритма является последовательное преоборазование многомерного тензора Г в прямоугольным матрицы, с последующим применением к ним усеченного сингулярного разложения. Данный алгоритм будет рассматриваться более подробно в Главе 1.6

NxNxN NxR RxNxR RxN

Рисунок 1.1 — TT-разложение тензора размера N х N х N с рангами Ri =

R2 = R.

В контексте тематики данной диссертации мы рассматриваем малоранговые тензорные разложения прежде всего как малопараметрические (и потому эффективные для больших вычислительных задач) аппроксиматоры функций многих переменных. Важно отметить, что для ТТ-разложения известны методы вычисления алгебраических операций +, — ,*, ©, 0, •, а также свертка и усреднение по любому из индексов, непосредственно в сжатом малоранговом формате. Кроме того, в малоранговом формате также определены действия линейных операторов, заданных в формате ТТ-матриц (см. секцию 1.3.2), а также применение взятие нелинейных функций от ТТ-вектора с помощью алгоритмов из семейства TT-CROSS (см. главу 1.7), или же алгоритмов, построенных на оптимизации (DMRG/ALS/AMEn [21; 51]). Также существует возможность «обучать» тензоры малого ранга подобно нейронным сетям с помощью метода обратного распространения ошибки и градиентных оптимизаторов [69]. Такой список возможностей позволил использовать ТТ-разложение в достаточно широком спектре различных вычислительных задач. Наконец, существует довольно развитая база открытого исходного кода (TT-Toolbox, ttpy, tntorch, t3f, tensorly libraries).

Также следует отметить, что для алгебраических операций в ТТ-формате известны оценки на TT-ранги г результирующего тензорного поезда (см. (1.6)).

r(tti + tt2) < r(tti)+ r(tt2) r(tti © tt2) < r(ííi)r(íí2) r(íí1 © íí2) = max(r(tti),r(tt2)) r(ttM • tt) < r(ttM) • r(tt)

1.3.2 ТТ-матрица (Tensor Train Matrix)

Подобно обычному тензорному поезду (ТТ-вектору) мы можем определить ТТ-матрицу.

П,..., гЛ-1

М (¿1,.. .,гл,]1,.. .,]<!) = С{1)('Ь1,'т1Л1)С{2)('12,т1,т2Л2) • ...

т1,...,тЛ-1 (1.7)

,тл-1,тл, (га,тл,3а).

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

1.4 QTT-разложение

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

Способ применять ТТ-разложение к маломерным задачам был предложен в статье [40], когда маломерный массив с очень «длинными» индексами было предложено превращать в многомерный массив с более «короткими» индексами.

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

Для начала рассмотрим применение данной идеи к одномерному массиву. Пусть задан вектор чисел V(i) экспоненциально большого размера N = 2d. Далее мы факторизуем «длинный» индекс i по d его двоичным регистрам {гт} и находим следующее разложение:

Г1,..., rd

V (0 = V £ Gf0)ni , (1.8)

mi,...,md

Такое разложение вектора V(i) называется QTT-вектором. Верхние пределы суммирования {rm} называются QTT-рангами. Обозначим за г максимальный QTT-ранг: г = max,; ri, тогда требования по памяти к такому разложению составят 0(г2 log N), а требования по сложности для основных алгебраических операций составят 0(г3 log N).

Важно отметить, что многие элементарные функции на сетке имеют малые QTT ранги [30; 40; 53]. В частности,

1. ехр(ж) имеет QTT-ранги: 1,

2. const имеет QTT-ранги: 1,

3. sin(^) и cos(x) имеют QTT-ранги: 2,

4. полиномы Р(d\x) имеет QTT-ранги: d + 1.

Синусы, косинусы и экспоненты часто возникают в решениях уравнений в частных производных эллиптического типа таких как уравнения Лапласа и Гельмгольца (или их эквивалентных интегральных форм), следовательно представляет научных интерес поискать решения сложных случаев данных уравнений в малоранговом QTT формате.

Результаты такого подхода к многомасштабной задаче рассеяния в двух измерениях на объектах, геометрия которых описывается малоранговой функцией на сетке, показаны в Главе 2 и в соответствующей публикации [9]. Подобный подход был развит для более сложных упорядоченных областей

в работе [49] и для рассеивателей более общего вида в т [64]. Недостатком данной работы является то, что если хотя бы на каком-то этапе вычисления возникает QTT-вектор или матрица со слишком большими QTT-рангами, вычисления быстро упираются в переполнение памяти, т.к. сложность по памяти и быстродействию зависит от максимального ранга полиномиально.

Подобное QTT-разложение может быть проведено и с матрицей экспоненциально большого размера 23, х 2^:

П,..., гл

М (1,3 ) = М (гц2 ...гп,зи2 ...эп)= ^ С{0,)1,т1 © ..

т1,...,та

(1.9)

ба (Я n(d)

^n-i,bn,jn,mn ^ " ^ ,гd,jd'

Данная конструкция называется QTT-матрицей [53].

Многие векторы и матрицы, строго говоря, не имеют точного QTT разложения с малыми QTT-рангами г. Однако, зачастую можно найти приближение Vt0i(i) такое, что оно будет близко к изначальному V(г), в смысле относительной ошибке по второй векторной норме:

||К, () - V W||2 <fnl (i)||2

Эта относительная ошибка в ТТ-сжатии называется допустимой точностью или ошибкой тензоризации (tolerance). Если ошибка тензоризации не превышает ошибку дискретизации и численной схемы, мы будем считать, что ТТ-версия нашей численной схемы эквивалентна полной версии (построенной на обычных массивах чисел, без сжатия). Для более подробной теории малоранговых приближений см. [52].

1.5 Разложение Таккера

Другое разложение, упоминаемое в данной диссертации, это разложение Таккера [34; 71]. Пусть дан трехмерный тензор А с размерами N х N х N. Найдем разложение следующего вида:

R,R,R

A(i,j,k) « G(p,l,m)U(1)(i,p)U(2)(j,l)U(3)(k,m) (1.10)

p,l,m=l

В трехмерном случае разложение Таккера более выгодно по памяти (при том же ранге), чем разложение в тензорный поезд (также называемое в трехмерном случае ТИСКЕК2). Сложность по памяти составляет Я? + 3МЯ вместо МЯ? + 2ЫЯ, однако цена доступа к функции в конкретной функции более высока: 0(Я??) у Таккера вместо 0(Я2) у ТТ. Поэтому выбор разложения зависит от приоритета данной задачи - обеспечить максимальное сжатие по памяти или более быстрый случайный доступ к функции в произвольных точках.

Для получения квази-оптимального разложения Таккера по полному тензору будет использоваться алгоритм ЫОБУВ [43].

1.6 TT-SVD

Основной алгоритм для нахождения ТТ-разложений по известному полному тензору был предложен И.В. Оселедцем в оригинальной работе [52]. Пусть задан тензор А = А{г\,... ,г^). Определим матрицы развертки как

(1.11)

Ak = A(ii,.. .,ik,ik+i,... ,id),

где a,..., ш обозначает формирование мультииндекса (одного «длинного» индекса) из заданных индексов.

Теорема 1. [54] Для любого тензора A = A(i\,...,id) существует TT-разложение с компрессионными рангами

rk = rank Ak

Теорема 2. [51] Для любого тензора A = A(i\,...,id) существует ТТ-разложение с компрессионными рангами rk, т.ч.

IA -T

If

<

\

d-i

Е

к=1

где £к минимальная ошибка аппроксимации (в норме Фробениуса) к-ой развертки:

£к = min ЦАк - В| |f.

rank В^ г к

2

£

к

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

Алгоритм 1: TT-SVD [52]

Data: тензор A размера п\ х ... х nd и целевая погрешность £ Result: ТТ -ядра Gk

1 вычислить nrm := ||A||_p,

d

2 размеры матрицы развёртки: Nl = п, Nr = П nk,

k=2

3 временный тензор: B := A,

4 первая развёртка: М := reshape (B, [Nl,Nr]),

5 вычисление SVD-разложения для М ~ UKV, с отсечкой £:

¡min(NL,NR)

6 положим G\:=U, M := AVT,r\ = r

7 for к = 2 to d — 1 do

._ Nr

8 9 10

11

12

переопределим размеры: Nl := nk,Nr := —

nk

построим следующую развёртку: M := reshape(M, [rNL, Nr})

вычислим SVD-разложения для M ~ UKV с отсечкой £:

Imin(NL,NR)

V"^ 2 £-nrm

J+ < ^

подействуем операцией reshape на матрицу U, превратив её в

тензор: Gk := reshape^, [rk—\,n,rk]) пересчитаем М := AV

13 end

14 Gd = М

1.7 ТТ-Сгозэ

Алгоритм TT-SVD находит квази-оптимальную малоранговую аппроксимацию, но при этом является весьма вычислительно дорогим. Менее оптимальным и менее универсальным, но также и менее вычислительно сложным является применение метода (квази)скелетного разложения или крестовой аппроксимации.

Рассмотрим для начала простой матричный случай. Пусть у нас есть вырожденная матрица А размера N х N, где гапк(А) = г < N. Очевидно, что в таком случае для матрица А точно представляется через г уже имеющихся строк и столбцов без вычисления левого и правого сингулярного базиса. Такой подход называется скелетным разложением и задаётся формулой:

А = С А-1Я, (1.12)

где С = А(:, J) выбранные г столбцов матрицы А, Я = А(Г,:) выбранные г строк матрицы А и

А = А(Х, а)

В более общем случае, когда матрица А не вырожденная, после выбора г строк Я и столбцов С равенство (1.12) будет выполняться с некоторой погрешностью (в смысле среднеквадратичного отклонения), однако, для многих вычислительных задач этого достаточно. Более подробно алгоритмы для таких случаев изложены в теории псевдоскелетных разложений [26].

В тензорном случае, как и в матричном, аналогичный подход также может быть применён. Алгоритм нахождения малорангового приближения путем выбора г строк, столбцов (в общем многомерном случае - распорок) для тензоров общего вида был изложен в статьях [19; 51].

Ниже приведел листинг алгоритма TT-Cгoss, находящий приближённое ТТ-разложение по заданному полному тензору (Алгоритм 2).

Алгоритм TT-CROSS будет иметь первостепенное значение в данной диссертации при работе с малоранговыми но высокоразмерными тензорами данных, например для инициализации функции Грина в главе 2, а также для порождения динамической системы и ТТ-итерации функции ценности в главе 3

Алгоритм 2: TT-CROSS [19; 51]

Data: Начальные значения TT-ядер v(k), к = 0,... ,d; функция

v(j0,... ,jd) целевая погрешность е. Result: уточнённые TT-ядра v(k).

1 Инициализируем Х<0 = J>d = 0 and iter = 0.

2 while iter < Imax or ||v — v^H > e||v|| do

3

4

5

6

7

8 9

10

11

12

13

14

Приравняем iter 4— iter +1 and vprev 4— v for к = 0 to d do

if J>k существует, т.е. iter > 1 then

Вычислим v(k) = v(l<k U [jk} U J>k) G Wfc-iXnfcXrk end

if к < d then

Вычислим QR разложение: V= QR, Q G Wk-inkXГк. Определим множество поправочных индексов: Ck = maxvol(Q) Обновим TT-ядра: Vlk> QQ(Ck,:)—1 и V<k+1> 4— Q(Ck, :)RV(k+1' Отобразим Ck в глобальное множество индексов X<k+1

end

end

15 end

16 Gd = M

1.8 AMEn

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

Ах = b (1.13)

Существующие в литературе алгоритмы включают в себя ALS [31], TT-GMRES [20] и AMEn [21]. В данной диссертации будет использоваться последний в силу его более высокой производительности. Листинг AMEn указан с меткой Алгоритм 3.

Алгоритм 3: AMEn [21], реккурентная версия Data: TT-матрица системы А, ТТ-вектор начального приближения

Т = T(tk), точность £ или ранги р1,..., рd-i Result: новое приближение х = т(хк) с рангами г'к ^ + Рк

1 А1 = Т= 1АТ=1, bi = Т= 1Ь, затем решить А1и1 = Ь1 для и1

2 и = т(и1 ,t2,... ,td) и z = b — Au

3 Вычислить приближение z ~ z = T(zk), ..||z — z|| ^ £||z|| или (z) < рк

4 Конкатенировать TT-ядра текущего приближения решения и невязки:

Список литературы диссертационного исследования кандидат наук Бойко Алексей Игоревич, 2025 год

Список литературы

1. 3D ShapeNets: A deep representation for volumetric shapes / Zhirong Wu [и др.] // 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). — 06.2015. — С. 1912—1920.

2. 3DMatch: Learning Local Geometric Descriptors from RGB-D Reconstructions / A. Zeng [и др.] // CVPR. — 2017.

3. Attention is All you Need / A. Vaswani [и др.] // NeurIPS Proceedings. — 2017.

4. Bellman R. E. Dynamic programming. — Princeton University Press, 1957.

5. Bertsekas D. P., Tsitsiklis J. N. Neuro-Dynamic Programming. — Belmont, Massachusetts : Athena Scientific, 1996.

6. Bitmead R. R., Anderson B. D. Asymptotically fast solution of toeplitz and related systems of linear equations // Linear Algebra and its Applications. — 1980. — Т. 34. — С. 103—116.

7. Bleszynski E., Bleszynski M., Jaroszewicz T. A fast integral-equation solver for electromagnetic scattering problems // Proceedings of IEEE Antennas and Propagation Society International Symposium and URSI National Radio Science Meeting. Т. 1. — 1994. — 416—419 vol.1.

8. Boyko A. I., Oseledets I. V., Ferrer G. TT-QI: Faster Value Iteration in Tensor Train Format for Stochastic Optimal Control // Computational Mathematics and Mathematical Physics. — 2021. — Т. 61. — С. 836—846.

9. Boyko A. I., Oseledets I. V., Gippius N. A. Towards solving Lippmann-Schwinger integral equation in 2D with polylogarithmic complexity with Quantized Tensor Train decomposition // Progress In Electromagnetics Research Symposium - Spring (PIERS). — 2017. — С. 2329—2333.

10. BundleFusion: Real-Time Globally Consistent 3D Reconstruction Using On-the-Fly Surface Reintegration / A. Dai [и др.] // ACM Trans. Graph. — New York, NY, USA, 2017. — Май. — Т. 36, № 3.

11. Cangellaris A., Lin C, Mei K. Point-matched time-domain finite element methods for electromagnetic radiation and scattering // IEEE Trans. Antennas Propagat. — 1987. — Окт. — Т. 35, вып. 10. — С. 1160—1173.

12. Chen Z, Zhang H. Learning implicit fields for generative shape modeling // Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. — 2019. — С. 5932—5941. — arXiv: 1812.02822.

13. Christ A., Hartnagel H. L. Three-Dimensional Finite-Difference Method for the Analysis of Microwave-Device Embedding // IEEE Transactions on Microwave Theory and Techniques. — 1987.

14. Continious Control with Deep Reinforcement Learning / T. P. Lillicrap [и др.] // ICLR. — 2016.

15. Curless B., Levoy M. A volumetric method for building complex models from range images // SIGGRAPH. — 1996. — С. 303—312.

16. Cybenko G. Approximation by superpositions of a sigmoidal function // Mathematics of Control, Signals and Systems. — 1989. — Дек. — Т. 2, № 4. — С. 303—314.

17. DeepSDF: Learning Continuous Signed Distance Functions for Shape Representation / J. J. Park [и др.] // CVPR. — 2019.

18. DeVoe H. Optical Properties of Molecular Aggregates. I. Classical Model of Electronic Absorption and Refraction // The Journal of Chemical Physics. — 1964. — Июль.

19. Dolgov S. V., Scheichl R. A hybrid Alternating Least Squares - TT Cross algorithm for parametric PDEs // SIAM/ASA Journal on Uncertainty Quantification. — 2017. — Июль. — Т. 7, вып. 1.

20. Dolgov S. V. TT-GMRES: solution to a linear system in the structured tensor format: // Russian Journal of Numerical Analysis and Mathematical Modelling. — 2013. — Т. 28, № 2. — С. 149—172.

21. Dolgov S. V., Savostyanov D. V. Alternating Minimal Energy Methods for Linear Systems in Higher Dimensions // SIAM Journal on Scientific Computing. — 2014. — Т. 36, № 5. — A2248—A2271. — eprint: https : // doi.org/10.1137/140953289.

22. Draco: a library for compressing and decompressing 3D geometric meshes and point clouds. — Google. — https://github.com/google/draco.

23. ElasticFusion: Dense SLAM without a pose graph / T. Whelan [h gp.] // Robotics: Science and Systems. — 2015. — T. 11. — eprint: 1604.01093.

24. Fleming W. H, Soner H. M. Controlled Markov Processes and Viscosity Solutions. — Springer, 2006.

25. Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domains / M. Tancik [h gp.] // NeurlPS Proceedings. — 2020.

26. Goreinov S. A., Tyrtyshnikov E. E., Zamarashkin N. A Theory of Pseudoskeleton Approximations // Linear Algebra and its Applications. — 1997. — T. 261. — C. 1—21.

27. Gorodetsky A. A., Karaman S., Marzouk Y. M. Efficient High-Dimensional Stochastic Optimal Motion Control using Tensor-Train Decomposition // Robotics: Science and Systems. — 2015.

28. Gorodetsky A. A., Karaman S., Marzouk Y. M. High-dimensional stochastic optimal control using continuous tensor decompositions // The International Journal of Robotics Research. — 2018.

29. Gorodetsky A. A., Karaman S., Marzouk Y. M. A continuous analogue of the tensor-train decomposition // Computer Methods in Applied Mechanics and Engineering. — 2019.

30. Grasedyck L. Polynomial Approximation in Hierarchical Tucker Format by Vector - Tensorization //. — 2010.

31. Grasedyck L, Kluge M, Kramer S. Variants of Alternating Least Squares Tensor Completion in the Tensor Train Format // SIAM Journal on Scientific Computing. — 2015. — T. 37, № 5. — A2424—A2450.

32. Greengard L, Rokhlin V. A fast algorithm for particle simulations // Journal of Computational Physics. — 1987. — T. 73, № 2. — C. 325—348.

33. Hane C, Tulsiani S., Malik J. Hierarchical surface prediction for 3D object reconstruction // 3DV. — 2017. — C. 412—420.

34. Hitchcock F. L. The expression of a tensor or a polyadic as a sum of products // Journal of Mathematics and Physics. — 1927. — T. 6. — C. 164—189.

35. Hornik K., Stinchcombe M. B., White H. L. Multilayer feedforward networks are universal approximators // Neural Networks. — 1989. — T. 2. — C. 359—366.

36. Horowitz M., Damle A., Burdick J. W. Linear Hamilton Jacobi Bellman Equations in high dimensions // IEEE Conference on Decision and Control. — 2014.

37. Implicit neural representations with periodic activation functions / V. Sitzmann [h gp.] // NeurlPS Proceedings. — 2020.

38. Jones M. W. Distance Field Compression // Journal of WSCG. — 2004. — 3 ^eBp. — T. 12, № 2. — C. 199—204.

39. Kazeev V., Khoromskij B., Tyrtyshnikov E. Multilevel Toeplitz Matrices Generated by Tensor-Structured Vectors and Convolution with Logarithmic Complexity // SIAM J. Sci. Comput. — 2013. — T. 35.

40. Khoromskij B. O(d log N)-Quantics Approximation of N-d Tensors in High-Dimensional Numerical Modeling // Constructive Approximation. — 2011. — T. 34. — C. 257—280.

41. Kidzinski et al L. Learning to Run challenge solutions: Adapting reinforcement learning methods for neuromusculoskeletal environments // Proceedings of NIPS. — 2017.

42. KinectFusion: Real-Time Dense Surface Mapping and Tracking / R. Newcombe [h gp.] // IEEE International Symposium on Mixed and Augmented Reality. — 2011. — C. 127—136.

43. Kolda T. G., Bader B. W. Tensor Decompositions and Applications // SIAM Review. — 2009. — T. 51, № 3. — C. 455—500.

44. Kushner H, Dupuis P. G. Numerical methods for stochastic control problems in continuous time. T. 24. — Springer, 2013.

45. Lagaris I. E, Likas A. C., Fotiadis D. I. Artificial neural networks for solving ordinary and partial differential equations // IEEE transactions on neural networks. — 1998. — T. 9 5. — C. 987—1000.

46. Lorensen W. E., Cline H. E. Marching Cubes: A High Resolution 3D Surface Construction Algorithm // SIGGRAPH Comput. Graph. — New York, NY, USA, 1987. — ABr. — T. 21, № 4. — C. 163—169.

47. Lu C., Chew W. A coupled surface-volume integral equation approach for the calculation of electromagnetic scattering from composite metallic and material targets // IEEE Transactions on Antennas and Propagation. — 2000. — T. 48, № 12. — C. 1866—1868.

48. Malladi R., Sethian J., Vemuri B. Shape modeling with front propagation: a level set approach // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 1995. — T. 17, Bbm. 2. — C. 158—175.

49. Markeeva L, Tsybulin I., Oseledets I. QTT-isogeometric solver in two dimensions // J. Comput. Phys. — 2021. — T. 424. — C. 109835.

50. Octree-based fusion for realtime 3D reconstruction / M. Zeng [h gp.] // Graphical Models. — 2013. — T. 75, № 3. — C. 126—136.

51. Oseledets I., Tyrtyshnikov E. TT-cross approximation for multidimensional arrays // Linear Algebra and its Applications. — 2010. — T. 432. — C. 70—88.

52. Oseledets I. V. Tensor-Train Decomposition // SIAM Journal on Scientific Computing. — 2011. — T. 33, № 5. — C. 2295—2317. — eprint: https://doi. org/10.1137/090752286.

53. Oseledets I. Constructive Representation of Functions in Low-Rank Tensor Formats // Constr Approx. — 2013. — T. 37. — C. 257—280.

54. Oseledets I. V. Compact matrix form of the d-dimensional tensor decomposition //. — 2009.

55. Playing Atari with Deep Reinforcement Learning / V. Mnih [h gp.] // NIPS Workshop. — 2013.

56. Polimeridis A. G., White J. K. On the compression of system tensors arising in FFT-VIE solvers // 2014 IEEE Antennas and Propagation Society International Symposium (APSURSI). — 2014. — C. 2144—2145.

57. Q-Learning Algorithms: A Comprehensive Classification and Applications / B. Jang [h gp.] // IEEE Access. — 2019. — T. 7. — C. 133653—133667.

58. Raissi M, Perdikaris P., Karniadakis G. Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations // Journal of Computational Physics. — 2019. — T. 378. — C. 686—707.

59. Real-time 3D reconstruction at scale using voxel hashing / M. Niesner [h gp.] // ACM Transactions on Graphics. — 2013. — T. 32, № 6.

60. Rossignac J. 3D compression made simple: Edgebreaker with ZipandWrap on a corner-table // International Conference on Shape Modeling and Applications. — 06.2001. — C. 278—283.

61. Rossler A. Runge-Kutta Methods for the Strong Approximation of Solutions of Stochastic Differential Equations // SIAM J. Numer. Anal. — 2010. — T. 3, № 48. — C. 922—952.

62. Schaubert D., Wilton D., Glisson A. A tetrahedral modeling method for electromagnetic scattering by arbitrarily shaped inhomogeneous dielectric bodies // IEEE Transactions on Antennas and Propagation. — 1984. — T. 32, № 1. — C. 77—85.

63. ShapeNet: An Information-Rich 3D Model Repository / A. X. Chang [h gp.]. — 2015. — http://arxiv.org/abs/1512.03012.

64. Sparsity-Aware Precorrected Tensor Train Algorithm for Fast Solution of 2-D Scattering Problems and Current Flow Modeling on Unstructured Meshes / Z. Chen [h gp.] //. T. 67. — 2019. — C. 4833—4847.

65. Splietker M, Behnke S. Directional TSDF: Modeling Surface Orientation for Coherent Meshes //. — 11.2019.

66. Taflove A. Application of the finite-difference time-domain method to sinusoidal steady state electromagnetic penetration problems // IEEE Trans. Electromagn. Compat. — 1980. — T. 3, Bbm. 22. — C. 191—202.

67. Tal E., Gorodetsky A., Karaman S. Continuous Tensor Train-Based Dynamic Programming for High-Dimensional Zero-Sum Differential Games // American Control Conference. — 2018.

68. Telea A. An Image Inpainting Technique Based on the Fast Marching Method //J. Graphics, GPU, Game Tools. — 2004. — T. 9. — C. 23—34.

69. Tensorizing Neural Networks / A. Novikov [h gp.] // Advances in Neural Information Processing Systems. T. 28 / nog peg. C. Cortes [h gp.]. — Curran Associates, Inc., 2015.

70. TT-TSDF: Memory-Efficient TSDF with Low-Rank Tensor Train Decomposition / A. I. Boyko [и др.] // 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). — 2020. — С. 10116—10121.

71. Tucker L. R. Some mathematical notes on three-mode factor analysis // Psychometrika. — 1966. — Сент. — Т. 31, вып. 3. — С. 279—311.

72. Watkins C. J. C. H, Dayan P. Q-learning // Machine Learning. — 1992. — Май. — Т. 8, № 3. — С. 279—292.

73. Webb J. P. Application of the finite-element method to electromagnetic and electrical topics // Reports on Progress in Physics. — 1995. — Дек. — Т. 58, № 12. — С. 1673—1712.

74. Whelan T, Kaess M, Fallon M. Kintinuous: Spatially extended kinectfusion // RSS Workshop on RGB-D: Advanced Reasoning with Depth Cameras. — 2012. — С. 7.

75. Yee K. Numerical solution of initial boundary value problems involving Maxwell's equations in isotropic media // IEEE Transactions on Antennas and Propagation. — 1966. — Май. — Т. 14, вып. 3. — С. 302—307.

76. Способ сжатия и хранения трехмерных данных (варианты) / А. И. Бойко [и др.] // Патент РФ на изобретение RU2753591 C1. — 2021. — Т. 23.

Список рисунков

1.1 ТТ-разложение тензора размера N х N х N с рангами Я\ = Я2 = Я. 13

2.1 Сжимаемость (максимальный QTT-ранг при ошибке 6 = 10-6) матрицы Грина С у в зависимости от количества элементов сетки

N и частоты................................................................31

2.2 Амплитуда полного поля |"ф(г)| ..........................................33

2.3 Время решения солвером ТТ-АМЕп, секунды (полулогарифмическая шкала)..............................................34

2.4 Время решения солвером РРТ-СМКЕБ, секунды (дважды логарифмическая шкала)....................................................34

2.5 Относительная погрешность решения QTT-солвера на сверх-мелких сетках (вплоть до « 106 х 106)............................................35

2.6 Распределение е(г)..........................................................37

2.7 Амплитуда полного поля |"ф(г)|. Длина падающей волны Л = Ь/20 . 37

2.8 Зависимость времени расчёта решения от длины падающей волны . 38

3.1 Решение для задачи оптимального быстродействия непериодическим маятником: (а) - оптимальная функция ценности

V(в), (б) - оптимальный регулятор п*(й)................. 53

3.2 Фазовые портреты динамической системы непериодического маятника: (а) - без управления (а = 0), (б) - под управлением оптимального регулятора (а = п*(в))................... 54

3.3 Симулированные траектории (х, у) машины Дубинса с инерцией. . . 57

3.4 Сжимаемость функции ценности в разных задачах........... 57

3.5 График относительной ошибки решения уравнения Беллмана для алгоритмов ТТ-У1 и ТТ^Р 3-маятник (квадратичная награда). ... 59

3.6 График относительной ошибки решения уравнения Беллмана для алгоритмов ТТ-У1 и ТТ^Р 3-маятник (задача оптимального быстродействия)............................... 60

3.7 График относительной ошибки решения уравнения Беллмана для алгоритмов ТТ-У1 и ТТ^Р простая машина Дубинса (квадратичная награда).......................... 61

3.8 График относительной ошибки решения уравнения Беллмана для алгоритмов TT-VI и TT-QI: машина Дубинса с инерцией (квадратичная награда).......................... 62

4.1 Визуализация TSDF размера 5123. Несжатый TSDF и различные степени TT-сжатия ............................ 66

4.2 ModelNet piane-0629 (watertight version)................. 70

4.3 Сечение SDF (без сжатия). Пунктирная линия соответствует

сечению поверхности модели (нулевой изоповерхности)........ 70

4.4 Сечение TT-SDF (R = 7). Можно видеть, что нулевая изоповерхность полностью разрушена.................. 70

4.5 Сечение TSDF (без сжатия). Пунктирная линия соответствует сечению поверхности модели ....................... 71

4.6 Сечение TT-TSDF (R = 7). Связность внутренней области 3D модели, как и форма форма поверхности сохранена. Пунктирная линия соответствует сечению поверхности модели ........... 71

4.7 Слева направо: несжатый TSDF, малоранговые TT-TSDFs с ТТ-рангами R = 40 (0.64% памяти), R = 20 (0.17% памяти),

R = 10 (0.046% памяти)....................................................77

4.8 Зависимость метрик и внешнего вида для 5123 TSDF Stanford Armadillo от ТТ-ранга R....................................................78

4.9 Стандартный KinectFusion................................................79

4.10 TSDF-Fusion с TT-сжатием с максимальным ТТ-рангом R = 40 ... 80

4.11 Пористая среда, описываемая разрывной функцией-индикатором

(без сжатия) ................................ 82

4.12 Пористая среда, сжатие с помощью разложения Таккера (с рангами

R = 80)................................... 82

А.1 Официальное подтверждение выдачи патента............. 95

Список таблиц

1 Сравнение производительности TT-VI и TT-QI ........................59

2 IoU (чем больше, тем лучше)..............................................76

4 Относительное расстояние Хаусдорфа х103 (чем меньше, тем лучше) 78

6 Метрики сжатого TSDF Fusion ............................................80

Приложение А Свидетельство о выдаче патента

Рисунок А.1 — Официальное подтверждение выдачи патента