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

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

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

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

Определение [ править ]

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

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

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

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

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

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).

Умножение на соответствует перемещению вперед на один шаг в модуле постоянства. Интуитивно, свободные части в правой части соответствуют генераторам гомологий, которые появляются на уровне фильтрации и никогда не исчезают, в то время как торсионные части соответствуют тем, которые появляются на уровне фильтрации и сохраняются на этапах фильтрации (или, что то же самое, исчезают на уровне фильтрации. ). ^[5]^[4]

x

t_{i}

r_{j}

s_{j}

s_{j}+r_{j}

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

Стабильность [ править ]

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

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

называется « узкое место» . Небольшое возмущение входной фильтрации приводит к небольшому возмущению ее диаграммы устойчивости на расстоянии узкого места. Для конкретности рассмотрим фильтрацию на пространстве, гомеоморфном симплициальному комплексу, определяемому множествами подуровней непрерывной ручной функции . Отображение, переходящее в диаграмму персистентности ее й гомологии, является 1-липшицевым относительно -метрики на функциях и расстояния до узкого места на диаграммах персистентности. То есть . ^[6]

X

f:X\to \mathbb {R}

D

f

k

\sup

W_{\infty }(D(f),D(g))\leq \lVert f-g\rVert _{\infty }

Вычисление [ править ]

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

Пакет программного обеспечения	Создатель	Последний релиз	Дата выпуска	Лицензия на программное обеспечение ^[8]	Открытый источник	Язык программирования	Функции
OpenPH	Родриго Мендоза-Смит, Джаред Таннер	0.0.1	25 апреля 2019 г.	Apache 2.0	да	Матлаб , CUDA
javaPlex	Эндрю Тауш, Микаэль Вейдемо-Йоханссон, Генри Адамс	4.2.5	14 марта 2016 г.	Обычай	да	Java , 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	Ускорение графического процессора

См. Также [ править ]

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

Ссылки [ править ]

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

[1] Карлссон, Гуннар (2009). « Топология и данные ». Бюллетень AMS 46 (2) , 255–308.

[2] Edelsbrunner, Н и Харер, J (2010). Вычислительная топология: введение . Американское математическое общество.

[3] Verri, А, Урас, С, Фросини, Р и Ферри, М (1993). Об использовании функций размера для анализа формы , Биологическая кибернетика, 70 , 99–107.

[Barannikov_1994-4] а б в г Баранников, Сергей (1994). «Обрамленный комплекс Морса и его инварианты» . Успехи советской математики . 21 : 93–115.

[5] Зомородян, Афра; Карлссон, Гуннар (19 ноября 2004 г.). «Вычисление стойких гомологий» . Дискретная и вычислительная геометрия . 33 (2): 249–274. DOI : 10.1007 / s00454-004-1146-у . ISSN 0179-5376 .

[:17-6] Коэн-Штайнер, Дэвид; Эдельсбруннер, Герберт; Харер, Джон (12 декабря 2006 г.). «Диаграммы устойчивости» . Дискретная и вычислительная геометрия . 37 (1): 103–120. DOI : 10.1007 / s00454-006-1276-5 . ISSN 0179-5376 .

[Otter_Porter_Tillmann_Grindrod-7] Выдра, Нина; Портер, Мейсон А; Тилльманн, Ульрике; и другие. (2017-08-09). «Дорожная карта для вычисления устойчивой гомологии» . EPJ Data Science . Springer. 6 (1): 17. DOI : 10,1140 / epjds / s13688-017-0109-5 . ISSN 2193-1127 .

[license-8] Лицензии здесь являются кратким изложением и не считаются полными заявлениями о лицензиях. Некоторые пакеты могут использовать библиотеки под разными лицензиями.

[Bauer_Kerber_Reininghaus_Wagner-9] Бауэр, Ульрих; Кербер, Майкл; Райнингхаус, Ян; Вагнер, Хуберт (2014). «PHAT - Набор инструментов для устойчивых гомологических алгоритмов». Математическое программное обеспечение - ICMS 2014 . Springer Berlin Heidelberg. С. 137–143. DOI : 10.1007 / 978-3-662-44199-2_24 . ISBN 978-3-662-44198-5. ISSN 0302-9743 .

[Maria_Boissonnat_Glisse_Yvinec-10] Мария, Клеман; Буассонна, Жан-Даниэль; Глисс, Марк; и другие. (2014). "Библиотека Гудхи: симплициальные комплексы и постоянные гомологии". Математическое программное обеспечение - ICMS 2014 . Берлин, Гейдельберг: Springer. С. 167–174. DOI : 10.1007 / 978-3-662-44199-2_28 . ISBN 978-3-662-44198-5. ISSN 0302-9743 .

[1]