Стойкая гомология

Method for computing topological features of a space at different spatial resolutions

См. Гомологии для введения в обозначения.

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

Чтобы найти постоянную гомологию пространства, его сначала необходимо представить как симплициальный комплекс . Функция расстояния в базовом пространстве соответствует фильтрации симплициального комплекса, то есть вложенной последовательности возрастающих подмножеств. Один из распространенных методов сделать это — использовать подуровневую фильтрацию расстояния до облака точек или, что то же самое, фильтрацию смещения в облаке точек и использовать его нервы , чтобы получить симплициальную фильтрацию, известную как фильтрация Чеха . ^[2] Подобная конструкция использует вложенную последовательность комплексов Виеториса–Рипса, известную как фильтрация Виеториса–Рипса . ^[3]

Определение

Формально, рассмотрим вещественную функцию на симплициальном комплексе , которая не убывает при возрастающей последовательности граней, поэтому всякий раз, когда грань in . Тогда для любого множества подуровней является подкомплексом K и упорядочение значений на симплексах в (которое на практике всегда конечно) индуцирует упорядочение на комплексах подуровней, которое определяет фильтрацию ${\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])}$ ${\displaystyle f}$ ${\displaystyle K}$

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

Когда включение индуцирует гомоморфизм на симплициальных группах гомологий для каждого измерения . Постоянные группы гомологии — это образы этих гомоморфизмов, а постоянные числа Бетти — это ранги этих групп. ^[4] Персистентные числа Бетти для совпадают с функцией размера , предшественником персистентной гомологии. ^[5] ${\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}}$ ${\displaystyle p=0}$

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

Модуль персистентности над частично упорядоченным набором — это набор векторных пространств, индексированных , с линейным отображением всякий раз, когда , с равным единице и для . Эквивалентно, мы можем рассматривать его как функтор из рассматриваемой категории в категорию векторных пространств (или -модулей ). Существует классификация модулей персистентности по полю, индексируемому : Умножение на соответствует переходу на один шаг вперед в модуле персистентности. Интуитивно понятно, что свободные части в правой части соответствуют генераторам гомологии, которые появляются на уровне фильтрации и никогда не исчезают, а торсионные части соответствуют тем, которые появляются на уровне фильтрации и сохраняются на протяжении шагов фильтрации (или, что то же самое, исчезают на уровне фильтрации). ). ^{[7] [6]} ${\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}}$

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

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

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

Вычисление

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

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

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

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

1. Карлссон, Гуннар (2009). «Топология и данные». Бюллетень AMS 46(2) , 255–308.
2. Кербер, Майкл; Шараткумар, Р. (2013). «Приблизительный комплекс Чеха в низких и высоких измерениях». В Цай, Лэйчжэнь; Ченг, Сиу-Винг; Лам, Так-Ва (ред.). Алгоритмы и вычисления . Конспекты лекций по информатике. Том. 8283. Берлин, Гейдельберг: Springer. стр. 666–676. дои : 10.1007/978-3-642-45030-3_62. ISBN 978-3-642-45030-3. S2CID  5770506.
3. Дей, Тамал К.; Ши, Даю; Ван, Юсу (30 января 2019 г.). «SimBa: эффективный инструмент для аппроксимации устойчивости разрывной фильтрации с помощью простого пакетного коллапса». Журнал экспериментальной алгоритмики ACM . 24 : 1,5:1–1,5:16. дои : 10.1145/3284360 . ISSN  1084-6654. S2CID  216028146.
4. Эдельсбруннер, Х. и Харер, Дж. (2010). Вычислительная топология: Введение . Американское математическое общество.
5. Верри, А.; Урас, К.; Фросини, П.; Ферри, М. (1993). «Об использовании функций размера для анализа формы». Биологическая кибернетика . 70 (2): 99–107. дои : 10.1007/BF00200823. S2CID  39065932.
6. Баранников, Сергей (1994). «Оформленный комплекс Морса и его инварианты». Успехи советской математики . 21 : 93–115.
7. Зомородиан, Афра; Карлссон, Гуннар (19 ноября 2004 г.). «Вычисление стойкой гомологии». Дискретная и вычислительная геометрия . 33 (2): 249–274. дои : 10.1007/s00454-004-1146-y . ISSN  0179-5376.
8. Коэн-Штайнер, Дэвид; Эдельсбруннер, Герберт; Харер, Джон (12 декабря 2006 г.). «Устойчивость диаграмм постоянства». Дискретная и вычислительная геометрия . 37 (1): 103–120. дои : 10.1007/s00454-006-1276-5 . ISSN  0179-5376.
9. Выдра, Нина; Портер, Мейсон А; Тильманн, Ульрике; и другие. (09.08.2017). «Дорожная карта для расчета стойкой гомологии». EPJ Наука о данных . 6 (1). Спрингер: 17. doi : 10.1140/epjds/s13688-017-0109-5 . ISSN  2193-1127. ПМК 6979512 . ПМИД  32025466. 
10. Лицензии здесь представляют собой краткое изложение и не считаются полным описанием лицензий. Некоторые пакеты могут использовать библиотеки под разными лицензиями.
11. Бауэр, Ульрих; Кербер, Майкл; Рейнингхаус, Ян; Вагнер, Хуберт (2014). «PHAT - Набор инструментов для алгоритмов постоянной гомологии». Математическое программное обеспечение – ICMS 2014 . Шпрингер Берлин Гейдельберг. стр. 137–143. дои : 10.1007/978-3-662-44199-2_24. ISBN 978-3-662-44198-5. ISSN  0302-9743.
12. Мария, Клеман; Буассонна, Жан-Даниэль; Глисс, Марк; и другие. (2014). «Библиотека Гудхи: симплициальные комплексы и стойкая гомология». Математическое программное обеспечение – ICMS 2014 (PDF) . Берлин, Гейдельберг: Springer. стр. 167–174. дои : 10.1007/978-3-662-44199-2_28. ISBN 978-3-662-44198-5. ISSN  0302-9743. S2CID  17810678.