Стойкая гомология - Persistent homology

Видеть гомология для введения в обозначения.

Стойкая гомология представляет собой метод вычисления топологических характеристик пространства с различным пространственным разрешением. Более стойкие особенности обнаруживаются в широком диапазоне пространственных масштабов и, как считается, с большей вероятностью представляют истинные особенности нижележащего пространства, а не артефакты выборки, шума или конкретного выбора параметров.^[1]

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

Определение

Формально рассмотрим вещественную функцию на симплициальном комплексе ${\displaystyle f:K\rightarrow \mathbb {R} }$ который не убывает при увеличении последовательности граней, поэтому ${\displaystyle f(\sigma )\leq f(\tau )}$ в любое время ${\displaystyle \sigma }$ это лицо ${\displaystyle \tau }$ в ${\displaystyle K}$. Тогда для каждого ${\displaystyle a\in \mathbb {R} }$ то подуровневый набор ${\displaystyle K(a)=f^{-1}(-\infty ,a]}$ является подкомплексом K, а порядок значений ${\displaystyle f}$ на симплексах в ${\displaystyle K}$ (который на практике всегда конечен) индуцирует порядок на подуровневых комплексах, который определяет фильтрацию

${\displaystyle \emptyset =K_{0}\subseteq K_{1}\subseteq \cdots \subseteq K_{n}=K}$

Когда ${\displaystyle 0\leq i\leq j\leq n}$, включение ${\displaystyle K_{i}\hookrightarrow K_{j}}$ вызывает гомоморфизм ${\displaystyle f_{p}^{i,j}:H_{p}(K_{i})\rightarrow H_{p}(K_{j})}$ на симплициальные гомологии группы для каждого измерения ${\displaystyle p}$. В ${\displaystyle p^{\text{th}}}$ стойкие группы гомологии являются образами этих гомоморфизмов, а ${\displaystyle p^{\text{th}}}$ настойчивый Бетти числа ${\displaystyle \beta _{p}^{i,j}}$ являются разряды этих групп.^[2] Постоянные числа Бетти для ${\displaystyle p=0}$ совпадают с функция размера, предшественник стойкой гомологии.^[3]

Любой фильтруемый комплекс над полем ${\displaystyle F}$ линейным преобразованием, сохраняющим фильтрацию, можно привести к так называемому каноническая форма, канонически определенная прямая сумма фильтрованных комплексов двух типов: одномерные комплексы с тривиальным дифференциалом ${\displaystyle d(e_{t_{i}})=0}$ и двумерные комплексы с тривиальными гомологиями ${\displaystyle d(e_{s_{j}+r_{j}})=e_{r_{j}}}$.^[4]

А модуль постоянства через частично заказанный набор ${\displaystyle P}$ это набор векторных пространств ${\displaystyle U_{t}}$ проиндексировано ${\displaystyle P}$, с линейной картой ${\displaystyle u_{t}^{s}:U_{s}\to U_{t}}$ в любое время ${\displaystyle s\leq t}$, с ${\displaystyle u_{t}^{t}}$ равно тождеству и ${\displaystyle u_{t}^{s}\circ u_{s}^{r}=u_{t}^{r}}$ за ${\displaystyle r\leq s\leq t}$. Точно так же мы можем рассматривать его как функтор из ${\displaystyle P}$ рассматривается как категория к категории векторных пространств (или ${\displaystyle R}$-модули ). Существует классификация модулей сохранения над полем ${\displaystyle F}$ проиндексировано ${\displaystyle \mathbb {N} }$:

$${\displaystyle U\simeq \bigoplus _{i}x^{t_{i}}\cdot F[x]\oplus \left(\bigoplus _{j}x^{r_{j}}\cdot (F[x]/(x^{s_{j}}\cdot F[x]))\right).}$$

Умножение на ${\displaystyle x}$ соответствует переходу на один шаг вперед в модуле постоянства. Интуитивно понятно, что свободные части в правой части соответствуют генераторам гомологий, которые появляются на уровне фильтрации ${\displaystyle t_{i}}$ и никогда не исчезнут, а торсионные части соответствуют тем, которые появляются на уровне фильтрации ${\displaystyle r_{j}}$ и последний для ${\displaystyle s_{j}}$ ступени фильтрации (или, что то же самое, исчезают на уровне фильтрации ${\displaystyle s_{j}+r_{j}}$).^{[5] [4]}

Каждая из этих двух теорем позволяет однозначно представить стойкие гомологии фильтрованного симплициального комплекса с штрих-код или же диаграмма устойчивости. Штрих-код представляет каждый постоянный генератор с горизонтальной линией, начинающейся на первом уровне фильтрации, где он появляется, и заканчивающейся на уровне фильтрации, где он исчезает, в то время как диаграмма постоянства отображает точку для каждого генератора с его координатой x, временем рождения и его Координата по оси Y время смерти. Эквивалентно те же данные представлены уравнением Баранникова. каноническая форма^[4], где каждый генератор представлен отрезком, соединяющим значения рождения и смерти, нанесенные на отдельные линии для каждого ${\displaystyle p}$.

Стабильность

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

$${\displaystyle W_{\infty }(X,Y):=\inf _{\varphi :X\to Y}\sup _{x\in X}\Vert x-\varphi (x)\Vert _{\infty },}$$

называется расстояние до узкого места. Небольшое возмущение входной фильтрации приводит к небольшому возмущению ее диаграммы устойчивости на расстоянии узкого места. Для конкретности рассмотрим фильтрацию на пространстве ${\displaystyle X}$ гомеоморфен симплициальному комплексу, определяемому множествами подуровней непрерывной ручной функции ${\displaystyle f:X\to \mathbb {R} }$. Карта ${\displaystyle D}$ принимая ${\displaystyle f}$ к диаграмме стойкости его ${\displaystyle k}$-я гомологии 1-липшицевы относительно ${\displaystyle \sup }$-метрика функций и расстояние до узких мест на диаграммах устойчивости. ${\displaystyle W_{\infty }(D(f),D(g))\leq \lVert f-g\rVert _{\infty }}$. ^[6]

Вычисление

Существуют различные программные пакеты для вычисления интервалов сохранения конечной фильтрации. ^[7] . Основной алгоритм основан на доведении отфильтрованного комплекса до его состояния. каноническая форма верхнетреугольными матрицами^[4].

Пакет программного обеспечения	Создатель	Последний релиз	Дата выхода	Лицензия на программное обеспечение[8]	Открытый исходный код	Язык программирования	Функции
OpenPH	Родриго Мендоса-Смит, Джаред Таннер	0.0.1	25 апреля 2019 г.	Apache 2.0	да	Matlab, CUDA
javaPlex	Эндрю Тауш, Микаэль Вейдемо-Йоханссон, Генри Адамс	4.2.5	14 марта 2016 г.	Обычай	да	Ява, Matlab
Дионис	Дмитрий Морозов	2.0.8	24 ноября 2020 г.	Модифицированный BSD	да	C ++, Python привязки
Персей	Видит Нанда	4.0 бета		GPL	да	C ++
PHAT [9]	Ульрих Бауэр, Майкл Кербер, Ян Рейнингхаус	1.4.1			да	C ++
ДИФА	Ян Рейнингхаус				да	C ++
Гудхи [10]	INRIA	3.0.0	23 сентября 2019 г.	GPLv3	да	C ++, Python привязки
CTL	Райан Льюис	0.2		BSD	да	C ++
Phom	Эндрю Тауш				да	р
TDA	Бриттани Т. Фаси, Джису Ким, Фабрицио Леччи, Клемент Мария, Винсент Рувро	1.5	16 июня 2016 г.		да	р
Эйрен	Грегори Хенсельман	1.0.1	9 марта 2019 г.	GPLv3	да	Юля
Ripser	Ульрих Бауэр	1.0.1	15 сентября 2016 г.	Массачусетский технологический институт	да	C ++
набор инструментов топологии	Жюльен Тьерни, Гийом Фавелье, Джошуа Левин, Шарль Гёне, Мишель Мишо	0.9.8	29 июля 2019 г.	BSD	да	C ++, VTK и Python привязки
libstick	Стефан Хубер	0.2	27 ноября 2014 г.	Массачусетский технологический институт	да	C ++
Рипсер ++	Саймон Чжан, Мэнбай Сяо и Хао Ван	1.0	Март 2020 г.	Массачусетский технологический институт	да	CUDA, C ++, Python привязки	GPU ускорение

Смотрите также

• Топологический анализ данных
• Вычислительная топология

Рекомендации

1. Карлссон, Гуннар (2009). "Топология и данные ". Бюллетень AMS 46(2), 255–308.
2. Эдельсбруннер, Х. и Харер, Дж. (2010). Вычислительная топология: введение. Американское математическое общество.
3. Верри, А., Урас, К., Фрозини, П. и Ферри, М. (1993). Об использовании функций размера для анализа формы, Биологическая кибернетика, 70, 99–107.
4. Баранников, Сергей (1994). «Обрамленный комплекс Морса и его инварианты». Успехи советской математики. 21: 93–115.
5. Зомородян, Афра; Карлссон, Гуннар (19 ноября 2004 г.). «Вычисление стойких гомологий». Дискретная и вычислительная геометрия. 33 (2): 249–274. Дои:10.1007 / s00454-004-1146-у. ISSN  0179-5376.
6. Коэн-Штайнер, Дэвид; Эдельсбруннер, Герберт; Харер, Джон (12 декабря 2006 г.). «Диаграммы устойчивости». Дискретная и вычислительная геометрия. 37 (1): 103–120. Дои:10.1007 / s00454-006-1276-5. ISSN  0179-5376.
7. Выдра, Нина; Портер, Мейсон А; Тилльманн, Ульрике; и другие. (2017-08-09). «Дорожная карта для вычисления устойчивой гомологии». EPJ Data Science. Springer. 6 (1): 17. Дои:10.1140 / epjds / s13688-017-0109-5. ISSN  2193-1127.
8. Лицензии здесь представляют собой краткое изложение и не считаются полными заявлениями о лицензиях. Некоторые пакеты могут использовать библиотеки под разными лицензиями.
9. Бауэр, Ульрих; Кербер, Майкл; Райнингхаус, Ян; Вагнер, Хуберт (2014). «PHAT - Набор инструментов для устойчивых гомологических алгоритмов». Математическое программное обеспечение - ICMS 2014. Springer Berlin Heidelberg. С. 137–143. Дои:10.1007/978-3-662-44199-2_24. ISBN  978-3-662-44198-5. ISSN  0302-9743.
10. Мария, Клеман; Буассонна, Жан-Даниэль; Глисс, Марк; и другие. (2014). "Библиотека Гудхи: симплициальные комплексы и постоянные гомологии". Математическое программное обеспечение - ICMS 2014. Берлин, Гейдельберг: Springer. С. 167–174. Дои:10.1007/978-3-662-44199-2_28. ISBN  978-3-662-44198-5. ISSN  0302-9743.