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

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

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

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

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

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

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

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

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

Модуль персистентности над частично упорядоченным набором $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).

Умножение на

x

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

t_{i}

и никогда не исчезают, а торсионные части соответствуют тем, которые появляются на уровне фильтрации.

r_{j}

и продлится

s_{j}

ступени фильтрации (или, что то же самое, исчезают на уровне фильтрации

s_{j}+r_{j}

). ^[7] ^[6]

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

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

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

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

где

\varphi

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

X

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

f:X\to \mathbb {R}

. Карта

D

принимая

f

к диаграмме персистентности его

k

гомология 1-липшицева относительно

\sup

-метрика функций и расстояние до узкого места на диаграммах устойчивости.То есть,

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

. ^[8]

Расчет [ править ]

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

Пакет программного обеспечения	Создатель	Последний выпуск	Дата выпуска	Лицензия на программное обеспечение ^[10]	Открытый исходный код	Язык программирования	Функции
OpenPH	Родриго Мендоса-Смит, Джаред Таннер	0.0.1	25 апреля 2019 г.	Апач 2.0	Да	Матлаб , CUDA	ускорение графического процессора
JavaPlex	Эндрю Тауш, Микаэль Вейдемо-Йоханссон, Генри Адамс	4.2.5	14 марта 2016 г.	Обычай	Да	Ява , Матлаб
Дионис	Dmitriy Morozov	2.0.8	24 ноября 2020 г.	Модифицированный BSD	Да	C++ , Python привязки
Персей	Vidit Nanda	4.0 бета		лицензия GPL	Да	С++
ПХАТ ^[11]	Ульрих Бауэр, Михаэль Кербер, Ян Рейнингхаус	1.4.1			Да	С++
ДИФА	Ян Рейнингхаус				Да	С++
Гудхи ^[12]	ИНРИА	3.4.0	15 декабря 2020 г.	С / GPLv3	Да	C++ , Python привязки
CTL	Райан Льюис	0.2		БСД	Да	С++
пистолет	Эндрю Тауш				Да	Р
ТДА	Бриттани Т. Фэйси, Джису Ким, Фабрицио Леччи, Клемент Мария, Винсент Рувро	1.5	16 июня 2016 г.		Да	Р	Предоставляет интерфейс R для GUDHI, Dionysus и PHAT.
Эйрен	Грегори Хенсельман	1.0.1	9 марта 2019 г.	лицензия GPLv3	Да	Юлия
потрошитель	Ульрих Бауэр	1.0.1	15 сентября 2016 г.	С	Да	С++
Набор инструментов топологии	Жюльен Тьерни, Гийом Фавелье, Джошуа Левин, Шарль Гене, Мишель Мишо	0.9.8	29 июля 2019 г.	БСД	Да	C++ , VTK и Python Привязки
библиотека	Стефан Хубер	0.2	27 ноября 2014 г.	С	Да	С++
Рипсер++	Саймон Чжан, Мэнбай Сяо и Хао Ван	1.0	март 2020 г.	С	Да	CUDA , C++ , Python привязки	ускорение графического процессора

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

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

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

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

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

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

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

[Otter_Porter_Tillmann_Grindrod-9] Выдра, Нина; Портер, Мейсон А; Тильманн, Ульрике; и др. (09.08.2017). «Дорожная карта для расчета стойкой гомологии» . EPJ Наука о данных . 6 (1). Спрингер: 17. doi : 10.1140/epjds/s13688-017-0109-5 . ISSN 2193-1127 . ПМК 6979512 . ПМИД 32025466 .

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

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

[Maria_Boissonnat_Glisse_Yvinec-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 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]