Бифильтрация Degree-Rips

Бифильтрация градусов -RIPS — это симплициальная фильтрация, используемая при анализе топологических данных для анализа формы данных облака точек . Это многопараметрическое расширение фильтрации Виеториса-Рипса , которое обладает большей устойчивостью к выбросам данных , чем однопараметрическая фильтрация, и которое более пригодно для практических вычислений, чем другие многопараметрические конструкции. Бифильтрация степени Rips, представленная в 2015 году Лесником и Райтом, представляет собой не имеющий параметров и чувствительный к плотности инструмент для выполнения вычислений постоянной гомологии на данных облака точек. ^[1]

Определение

Стандартной практикой в анализе топологических данных (TDA) является связывание последовательности вложенных симплициальных комплексов с конечным набором данных, чтобы обнаружить постоянство топологических особенностей в диапазоне параметров масштаба. Один из способов сделать это — рассмотреть последовательность комплексов Виеториса–Рипса конечного множества в метрическом пространстве, индексированную по всем масштабным параметрам.

Если $X$ является конечным множеством в метрическом пространстве, то эта конструкция известна как фильтрация Вьеториса–Рипса (или просто «Рипса») на $X$ , обычно обозначаемый ${\text{Rips}}(X)$ или ${\mathcal {R}}(X)$ . ^[2]^[3]^[4] Фильтрация Rips может быть выражена в виде функтора ${\text{Rips}}(X):\mathbb {R} \to \mathbf {Simp}$ от действительных чисел (рассматриваемых как частично упорядоченных множеств категория ) к категории симплициальных комплексов и симплициальных отображений , подкатегории категории $\mathbf {Top}$ топологических пространств и непрерывных отображений через функтор геометрической реализации . ^[5]

Фильтрация Rips индексируется по одному параметру, но мы можем получить больше информации (например, плотности) о базовом наборе данных, рассматривая многопараметрическую фильтрацию. Фильтрация, индексированная произведением двух полностью упорядоченных множеств, известна как бифильтрация, впервые введенная Гуннаром Карлссоном и Афрой Зомородян в 2009 году. ^[6]

Бифильтрация степени Rips фильтрует каждый симплициальный комплекс в фильтрации Rips по степени каждой вершины в графе, изоморфном в 1-скелету каждом индексе. Более формально, пусть $(a,b)$ быть элементом $\mathbb {R} ^{2}$ и определить $G_{a,b}$ быть подграфом 1-скелета ${\text{Rips}}(X)_{b}$ содержащий все вершины, степень которых не меньше $a$ . Построив впоследствии максимально возможный симплициальный комплекс на этом 1-остове, получим комплекс ${\text{D-Rips}}(X)_{a,b}$ . Делая это для всех возможных степеней вершин и всех параметров масштаба в фильтрации Rips, мы расширяем конструкцию Rips до бифильтрации. $\{{\text{D-Rips}}(X)_{a,b}\}_{(a,b)\in \mathbb {R} ^{2}}$ . ^[1]

Обратите внимание, что, поскольку размер каждого комплекса будет уменьшаться по мере $a$ увеличивается, мы должны определить набор индексов $\mathbb {R} ^{2}$ с $\mathbb {R} ^{\text{op}}\times \mathbb {R}$ , где $\mathbb {R} ^{\text{op}}$ является противоположной частичной категорией $\mathbb {R}$ . Поэтому бифильтрацию степени-Rips можно рассматривать как функтор ${\text{D-Rips}}(X):\mathbb {R} ^{\operatorname {op} }\times \mathbb {R} \to \mathbf {Simp}$ . ^[7]

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

Приложения для анализа данных

Бифильтрация степеней разрывов обладает несколькими свойствами, которые делают ее полезным инструментом при анализе данных. Например, каждый его скелет имеет полиномиальный размер ; k-мерный скелет ${\text{D-Rips}}(X)$ имеет $O(|X|^{k+2})$ просто, где $O$ обозначает асимптотическую верхнюю границу . ^[7] Более того, было показано, что бифильтрация степени Rips обладает достаточно сильными свойствами устойчивости по отношению к возмущениям основного набора данных. ^[7] Дальнейшая работа также была проведена по изучению стабильных компонентов и гомотопических типов комплексов степени-Rips. ^[9]^[10]^[11]

Программное обеспечение RIVET было создано для визуализации нескольких многопараметрических инвариантов (т. е. структур данных, которые пытаются уловить основную геометрическую информацию данных) двухпараметрических модулей персистентности, включая модули постоянной гомологии бифильтрации степени-RIPS. Эти инварианты включают функцию Гильберта , инвариант ранга и расслоенный штрих-код. ^[1]

В продолжение введения степени разрыва в своей оригинальной статье 2015 года Лесник и Райт в 2022 году показали, что основной компонент вычислений постоянной гомологии (а именно, вычисление минимальных представлений и биградуированных чисел Бетти ) может быть эффективно достигнут это превосходит другие программы для обеспечения постоянной гомологии. ^[12] Также были исследованы методы повышения алгоритмической эффективности многопараметрической постоянной гомологии, которые предполагают возможность существенного увеличения скорости таких инструментов анализа данных, как RIVET. ^[13]

Бифильтрация градусов-RIPS использовалась для анализа данных в случайных облаках точек. ^[14] а также для анализа кластеров данных с точки зрения изменений плотности. ^[15]^[16]^[17] Был проведен некоторый предварительный экспериментальный анализ эффективности степени разрыва, в частности, в отношении выбросов, но по состоянию на февраль 2023 года это продолжающаяся область исследований. ^[18]

Ссылки

^ Перейти обратно: ^а ^б ^с Лесник, Майкл; Райт, Мэтью (01 декабря 2015 г.). «Интерактивная визуализация двумерных модулей персистентности». arXiv : 1512.00180 [ math.AT ].
^ Рабадан, Рауль; Блумберг, Эндрю Дж. (2019). Топологический анализ данных для геномики и эволюции: топология в биологии . Кембридж: Издательство Кембриджского университета. стр. 135–139. дои : 10.1017/9781316671665 . ISBN 978-1-107-15954-9 . S2CID 242498045 .
^ Удо, Стив Ю. (2015). Теория персистентности: от колчанных представлений к анализу данных . Провиденс, Род-Айленд. п. 104. ИСБН 978-1-4704-2545-6 . OCLC 918149730 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Структура и стабильность модулей персистентности . Фредерик Шазаль, Вин Де Сильва, Марк Глисс, Стив Ю. Удо. Швейцария. 2016. с. 66. ИСБН 978-3-319-42545-0 . OCLC 960458101 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) CS1 maint: другие ( ссылка )
^ Ботнан, Магнус Бакке; Лесник, Майкл (27 марта 2022 г.). «Введение в многопараметрическую устойчивость». п. 8. arXiv : 2203.14289 [ math.AT ].
^ Карлссон, Гуннар; Зомородян, Афра (01.07.2009). «Теория многомерного постоянства» . Дискретная и вычислительная геометрия . 42 (1): 71–93. дои : 10.1007/s00454-009-9176-0 . ISSN 1432-0444 .
^ Перейти обратно: ^а ^б ^с Блумберг, Эндрю Дж.; Лесник, Майкл (17 октября 2022 г.). «Стабильность двухпараметрической постоянной гомологии» . Основы вычислительной математики : 3, 8. arXiv : 2010.09628 . дои : 10.1007/s10208-022-09576-6 . ISSN 1615-3375 . S2CID 224705357 .
^ Шенк, Хэл (2022). Алгебраические основы прикладной топологии и анализа данных . Чам. п. 183. ИСБН 978-3-031-06664-1 . OCLC 1351750760 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Жардин, Дж. Ф. (сентябрь 2020 г.). «Стабильные компоненты и слои» . Канадский математический бюллетень . 63 (3): 562–576. arXiv : 1905.05788 . дои : 10.4153/S000843951900064X . ISSN 0008-4395 . S2CID 155092981 .
^ Джардин, Дж. Ф. (2019). «Данные и гомотопические типы». arXiv : 1908.06323 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Жардин, Дж. Ф. (26 октября 2020 г.). «Постоянная гомотопическая теория». arXiv : 2002.10013 [ math.AT ].
^ Лесник, Майкл; Райт, Мэтью (2022). «Вычисление минимальных представлений и биградуированных чисел Бетти двухпараметрической постоянной гомологии» . SIAM Journal по прикладной алгебре и геометрии . 6 (2): 267–298. arXiv : 1902.05708 . дои : 10.1137/20M1388425 . S2CID 85499980 .
^ Алонсо; Кербер; Притам (2023). «Фильтрация-доминирование в бифильтрованных графах» . 2023 Материалы симпозиума по алгоритмической разработке и экспериментам (ALENEX) : 27–38. arXiv : 2211.05574 . дои : 10.1137/1.9781611977561.ch3 . ISBN 978-1-61197-756-1 . S2CID 253447256 .
^ Прабеш Паудел; Ван, Кен; Юлдашева, Юлия (2021). «Характеристики бифильтрации градусных разрывов из случайных геометрических облаков точек» . дои : 10.13140/RG.2.2.34156.28809 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Ролле, Александр; Скоккола, Луис (16 июля 2021 г.). «Стабильная и последовательная кластеризация на основе плотности». arXiv : 2005.09048 [ math.ST ].
^ Ролле, Александр (2020). «Многопараметрическая иерархическая кластеризация и не только» . Семинар «Топологический анализ данных и не только» на 34-й конференции по нейронным системам обработки информации .
^ Адамик, Кэтрин Л.М. (2021). «Стабильность точек слоя». arXiv : 2109.01701 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Ролле, Александр (16 марта 2022 г.). «Комплексы степеней разрывов кольца с выбросами». arXiv : 2203.08767 [ math.AT ].

[:0-1] Перейти обратно: ^а ^б ^с Лесник, Майкл; Райт, Мэтью (01 декабря 2015 г.). «Интерактивная визуализация двумерных модулей персистентности». arXiv : 1512.00180 [ math.AT ].

[2] Рабадан, Рауль; Блумберг, Эндрю Дж. (2019). Топологический анализ данных для геномики и эволюции: топология в биологии . Кембридж: Издательство Кембриджского университета. стр. 135–139. дои : 10.1017/9781316671665 . ISBN 978-1-107-15954-9 . S2CID 242498045 .

[3] Удо, Стив Ю. (2015). Теория персистентности: от колчанных представлений к анализу данных . Провиденс, Род-Айленд. п. 104. ИСБН 978-1-4704-2545-6 . OCLC 918149730 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[4] Структура и стабильность модулей персистентности . Фредерик Шазаль, Вин Де Сильва, Марк Глисс, Стив Ю. Удо. Швейцария. 2016. с. 66. ИСБН 978-3-319-42545-0 . OCLC 960458101 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) CS1 maint: другие ( ссылка )

[5] Ботнан, Магнус Бакке; Лесник, Майкл (27 марта 2022 г.). «Введение в многопараметрическую устойчивость». п. 8. arXiv : 2203.14289 [ math.AT ].

[6] Карлссон, Гуннар; Зомородян, Афра (01.07.2009). «Теория многомерного постоянства» . Дискретная и вычислительная геометрия . 42 (1): 71–93. дои : 10.1007/s00454-009-9176-0 . ISSN 1432-0444 .

[:1-7] Перейти обратно: ^а ^б ^с Блумберг, Эндрю Дж.; Лесник, Майкл (17 октября 2022 г.). «Стабильность двухпараметрической постоянной гомологии» . Основы вычислительной математики : 3, 8. arXiv : 2010.09628 . дои : 10.1007/s10208-022-09576-6 . ISSN 1615-3375 . S2CID 224705357 .

[8] Шенк, Хэл (2022). Алгебраические основы прикладной топологии и анализа данных . Чам. п. 183. ИСБН 978-3-031-06664-1 . OCLC 1351750760 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[9] Жардин, Дж. Ф. (сентябрь 2020 г.). «Стабильные компоненты и слои» . Канадский математический бюллетень . 63 (3): 562–576. arXiv : 1905.05788 . дои : 10.4153/S000843951900064X . ISSN 0008-4395 . S2CID 155092981 .

[10] Джардин, Дж. Ф. (2019). «Данные и гомотопические типы». arXiv : 1908.06323 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[11] Жардин, Дж. Ф. (26 октября 2020 г.). «Постоянная гомотопическая теория». arXiv : 2002.10013 [ math.AT ].

[12] Лесник, Майкл; Райт, Мэтью (2022). «Вычисление минимальных представлений и биградуированных чисел Бетти двухпараметрической постоянной гомологии» . SIAM Journal по прикладной алгебре и геометрии . 6 (2): 267–298. arXiv : 1902.05708 . дои : 10.1137/20M1388425 . S2CID 85499980 .

[13] Алонсо; Кербер; Притам (2023). «Фильтрация-доминирование в бифильтрованных графах» . 2023 Материалы симпозиума по алгоритмической разработке и экспериментам (ALENEX) : 27–38. arXiv : 2211.05574 . дои : 10.1137/1.9781611977561.ch3 . ISBN 978-1-61197-756-1 . S2CID 253447256 .

[14] Прабеш Паудел; Ван, Кен; Юлдашева, Юлия (2021). «Характеристики бифильтрации градусных разрывов из случайных геометрических облаков точек» . дои : 10.13140/RG.2.2.34156.28809 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[15] Ролле, Александр; Скоккола, Луис (16 июля 2021 г.). «Стабильная и последовательная кластеризация на основе плотности». arXiv : 2005.09048 [ math.ST ].

[16] Ролле, Александр (2020). «Многопараметрическая иерархическая кластеризация и не только» . Семинар «Топологический анализ данных и не только» на 34-й конференции по нейронным системам обработки информации .

[17] Адамик, Кэтрин Л.М. (2021). «Стабильность точек слоя». arXiv : 2109.01701 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[18] Ролле, Александр (16 марта 2022 г.). «Комплексы степеней разрывов кольца с выбросами». arXiv : 2203.08767 [ math.AT ].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]