Фильтрация Виеториса–Рипса
Набор из трех вложенных подкомплексов в рамках фильтрации Виеториса–Рипса на наборе точек в евклидовой плоскости.

В топологическом анализе данных фильтрация Виеториса–Рипса (иногда сокращается до « фильтрация Рипса ») представляет собой набор вложенных комплексов Виеториса–Рипса в метрическом пространстве , созданном путем взятия последовательности комплексов Виеториса–Рипса по увеличивающемуся параметру масштаба. Часто фильтрация Виеториса–Рипса используется для создания дискретной симплициальной модели на данных облака точек, встроенных в окружающее метрическое пространство. [1] Фильтрация Виеториса–Рипса представляет собой многомасштабное расширение комплекса Виеториса–Рипса, которое позволяет исследователям обнаруживать и отслеживать постоянство топологических особенностей в диапазоне параметров путем вычисления постоянной гомологии всей фильтрации. [2] [3] [4] Он назван в честь Леопольда Виеториса и Элияху Рипса .

Определение

Фильтрация Виеториса–Рипса — это вложенный набор комплексов Виеториса–Рипса , индексированных по возрастающему параметру масштаба. Комплекс Виеториса–Рипса — это классическая конструкция в математике, которая восходит к статье 1927 года [5] Леопольда Виеториса , хотя она была независимо рассмотрена Элияху Рипсом при изучении гиперболических групп , как отметил Михаил Громов в 1980-х годах. [6] Совместное название «Виеторис–Рипс» принадлежит Жан-Клоду Хаусманну. [7]

Пример комплекса Виеториса–Рипса, построенного по точкам евклидовой плоскости.

При наличии метрического пространства и параметра масштаба (иногда называемого пороговым или параметром расстояния ) , комплекс Виеториса–Рипса (относительно ) определяется как , где — диаметр , т.е. максимальное расстояние точек, лежащих в . [8] Х {\displaystyle X} г ∈ [ 0 , ∞ ) {\displaystyle r\in [0,\infty )} г {\displaystyle r} В Р г ( Х ) = { ∅ ≠ С ⊆ Х ∣ С  конечный ; диам. ⁡ С ≤ г } {\displaystyle \mathbf {VR} _{r}(X)=\{\emptyset \neq S\subseteq X\mid S{\text{ конечное}};\operatorname {диаметр} S\leq r\}} диам. ⁡ С {\displaystyle \operatorname {диаметр} S} С {\displaystyle S}

Обратите внимание, что если , то существует симплициальное отображение включения . Фильтрация Виеториса–Рипса представляет собой вложенный набор комплексов  : г ≤ с ∈ [ 0 , ∞ ) {\displaystyle r\leq s\in [0,\infty )} В Р г ( Х ) ↪ В Р с ( Х ) {\displaystyle \mathbf {VR} _{r}(X)\hookrightarrow \mathbf {VR} _{s}(X)} В Р г ( Х ) {\displaystyle \mathbf {VR} _{r}(X)}

В Р ( Х ) = { В Р г ( Х ) } г ∈ [ 0 , ∞ ) {\displaystyle \mathbf {VR} (X)=\{\mathbf {VR} _{r}(X)\}_{r\in [0,\infty)}}

Если неотрицательные действительные числа рассматривать как посетальную категорию посредством отношения , то фильтрацию Виеториса–Рипса можно рассматривать как функтор, принимающий значения в категории симплициальных комплексов и симплициальных отображений, где морфизмы (т.е. отношения в посете) в исходной категории индуцируют отображения включения между комплексами. [9] Обратите внимание, что категорию симплициальных комплексов можно рассматривать как подкатегорию , категории топологических пространств , путем посткомпозиции с функтором геометрической реализации . [ 0 , ∞ ) {\displaystyle [0,\infty )} ≤ {\displaystyle \leq} В Р ( Х ) : [ 0 , ∞ ) → С я м п {\displaystyle \mathbf {VR} (X):[0,\infty)\to \mathbf {Simp} } Т о п {\displaystyle \mathbf {Вверх} }

Характеристики

Размер фильтрации относится к числу симплексов в наибольшем комплексе, предполагая, что лежащее в основе метрическое пространство конечно. Известно, что -скелет, т. е. число симплексов вплоть до размерности , фильтрации Виеториса–Рипса равен , где — число точек. [10] Размер полного скелета имеет ровно симплексов, по одному на каждое непустое подмножество точек. [9] Поскольку это экспоненциально, исследователи обычно вычисляют скелет фильтрации Виеториса–Рипса только до малых значений . [2] к {\displaystyle к} к {\displaystyle к} О ( н к + 1 ) {\displaystyle O\left(n^{k+1}\right)} н {\displaystyle n} 2 н − 1 {\displaystyle 2^{n}-1} к {\displaystyle к}

Когда базовое метрическое пространство конечно, фильтрация Виеториса–Рипса иногда упоминается как существенно дискретная , [9] имея в виду, что существует некоторый конечный или максимальный параметр масштаба такой, что для всех , и, кроме того, что отображение включения является изоморфизмом для всех, кроме конечного числа параметров . Другими словами, когда базовое метрическое пространство конечно, фильтрация Виеториса–Рипса имеет наибольший комплекс, и комплекс изменяется только за конечное число шагов. Последнее подразумевает, что фильтрация Виеториса–Рипса на конечном метрическом пространстве может рассматриваться как индексированная по дискретному множеству , такому как , ограничивая фильтрацию параметрами масштаба, при которых изменяется фильтрация, а затем переименовывая комплексы с использованием натуральных чисел . г макс ∈ [ 0 , ∞ ) {\displaystyle r_{\text{макс}}\in [0,\infty )} В Р с ( Х ) = В Р г макс ( Х ) {\displaystyle \mathbf {VR} _{s}(X)=\mathbf {VR} _{r_{\max }}(X)} с ≥ г макс {\displaystyle s\geq r_{\max }} В Р с → т ( Х ) : В Р с ( Х ) ↪ В Р т ( Х ) {\displaystyle \mathbf {VR} _{s\to t}(X):\mathbf {VR} _{s}(X)\hookrightarrow \mathbf {VR} _{t}(X)} с ≤ т {\displaystyle s\leq t} Н {\displaystyle \mathbb {N} }

Явная граница может быть также дана для числа шагов, на которых изменяется фильтрация Виеториса–Рипса. Комплекс Виеториса–Рипса является кликовым комплексом , то есть он полностью определяется своим 1-скелетом. [11] Поэтому число шагов, на которых изменяется фильтрация Виеториса–Рипса, ограничено числом ребер в наибольшем комплексе. Число ребер в наибольшем комплексе равно , поскольку все вершины соединены ребром. Поэтому фильтрация Виеториса–Рипса изменяется на шагах, где обозначает асимптотическую верхнюю границу . ( н 2 ) = н ( н − 1 ) / 2 {\displaystyle {n \choose 2}=n(n-1)/2} n {\displaystyle n} O ( n 2 ) {\displaystyle O(n^{2})} O ( − ) {\displaystyle O(-)}

Для точек в евклидовом пространстве фильтрация Виеториса–Рипса является приближением к фильтрации Чеха в смысле расстояния перемежения. [1] Это следует из того факта, что для любого масштабного параметра комплексы Виеториса–Рипса и Чеха на конечном множестве точек в евклидовом пространстве удовлетворяют соотношению включения , которое иногда называют леммой Виеториса–Рипса. [12] В общих метрических пространствах прямое применение неравенства треугольника показывает, что для любого масштабного параметра . α {\displaystyle \alpha } X {\displaystyle X} V R α ( X ) ⊆ C ˇ e c h 2 α ⁡ ( X ) ⊆ V R 2 α ( X ) {\displaystyle \mathbf {VR} _{\alpha }(X)\subseteq \operatorname {{\check {C}}ech} _{{\sqrt {2}}\alpha }(X)\subseteq \mathbf {VR} _{{\sqrt {2}}\alpha }(X)} V R α ( X ) ⊆ C ˇ e c h 2 α ⁡ ( X ) ⊆ V R 2 α ( X ) {\displaystyle \mathbf {VR} _{\alpha }(X)\subseteq \operatorname {{\check {C}}ech} _{2\alpha }(X)\subseteq \mathbf {VR} _{2\alpha }(X)} α {\displaystyle \alpha }

Варианты

Приближения

Поскольку фильтрация Виеториса–Рипса имеет экспоненциальное число симплексов в своем полном скелете, было проведено значительное количество исследований по аппроксимации устойчивой гомологии фильтрации Виеториса–Рипса с использованием конструкций меньшего размера. Первая работа в этом направлении была опубликована ученым-компьютерщиком Дональдом Шихи в 2012 году, который показал, как построить фильтрацию размера во времени, которая аппроксимирует устойчивую гомологию фильтрации Виеториса–Рипса до желаемого предела погрешности. [10] Этот тип фильтрации известен как S- разборная фильтрация Виеториса–Рипса , поскольку она удаляет точки из стандартной фильтрации Виеториса–Рипса, используя идеи из вычислительной геометрии, связанные с геометрическими остовами . [13] С тех пор было разработано несколько более эффективных методов аппроксимации фильтрации Виеториса–Рипса, в основном использующих идеи Шихи, но также и основанных на схемах аппроксимации, разработанных для фильтраций Чеха [14] и Делоне [15] . [16] [2] O ( n ) {\displaystyle O(n)} O ( n log ⁡ n ) {\displaystyle O(n\log n)}

Многопараметрические расширения

Известно, что постоянная гомология может быть чувствительна к выбросам в базовом наборе данных. [17] Чтобы исправить это, в 2009 году Гуннар Карлссон и Афра Зомородян предложили многомерную версию постоянной, которая рассматривает фильтрацию по нескольким параметрам, таким как масштаб и плотность. [18]

С этой целью было разработано несколько многопараметрических расширений фильтрации Виеториса–Рипса.

  • Бифильтрация Degree -Rips расширяет фильтрацию Виеториса–Рипса, строя подграф 1-скелета каждого комплекса в фильтрации Виеториса–Рипса, ограничиваясь только вершинами, степень которых не ниже заданного параметра , а затем строя комплекс клики на этом подграфе. Степень вершины кодирует информацию о плотности данных, поскольку она количественно определяет, насколько «центральной» является эта точка посредством того, сколько других вершин с ней связано. Коллекция по всем параметрам степени определяет фильтрацию каждого комплекса в фильтрации Виеториса–Рипса, где комплексы становятся меньше по мере увеличения. В целом это определяет 2-параметрическое расширение фильтрации Виеториса–Рипса, рассматривая коллекцию бифильтрованных комплексов по всем параметрам масштаба , где «op» обозначает противоположный частично упорядоченный набор . [19] a ∈ [ 0 , ∞ ) {\displaystyle a\in [0,\infty )} a {\displaystyle a} a {\displaystyle a} ( a , r ) ∈ R op × R {\displaystyle (a,r)\in \mathbb {R} ^{\operatorname {op} }\times \mathbb {R} }
  • Бифильтрация Function -Rips расширяет фильтрацию Vietoris–Rips, бифильтруя каждый комплекс в соответствии с суперуровневыми множествами некоторой функции , где может быть функцией плотности, функцией эксцентриситета или любой другой функцией. А именно, каждый комплекс определяется через , что дает бифильтрацию, индексированную по . [20] γ : X → R {\displaystyle \gamma :X\to \mathbb {R} } γ {\displaystyle \gamma } F - V R a , r ( γ ) = V R r ( γ − 1 [ a , ∞ ) ) {\displaystyle \mathbf {F} {\text{-}}\mathbf {VR} _{a,r}(\gamma )=\mathbf {VR} _{r}(\gamma ^{-1}[a,\infty ))} R op × [ 0 , ∞ ) {\displaystyle \mathbb {R} ^{\operatorname {op} }\times [0,\infty )}
  • Бифильтрация subdivision -Rips расширяет фильтрацию Vietoris–Rips, беря барицентрическое подразделение каждого комплекса в фильтрации Vietoris–Rips, а затем фильтруя эти комплексы по размерности каждого флага. А именно, барицентрическое подразделение симплициального комплекса является абстрактным симплициальным комплексом, определенным с использованием флагов симплексов в базовом комплексе, где флаг (иногда называемый цепью ) является вложенной серией симплексов . Затем, имея барицентрическое подразделение комплекса, можно отфильтровать его, взяв подкомплекс, охватываемый вершинами, соответствующими симплексам в исходном комплексе некоторой минимальной размерности . Совокупность всех таких комплексов дает бифильтрацию, индексированную по . [21] σ 0 ⊂ ⋯ ⊂ σ m {\displaystyle \sigma _{0}\subset \cdots \subset \sigma _{m}} k {\displaystyle k} [ 0 , ∞ ) op × [ 0 , ∞ ) {\displaystyle [0,\infty )^{\operatorname {op} }\times [0,\infty )}

Ссылки

  1. ^ ab Chazal, Frédéric; Oudot, Steve Y. (2013). «Interleaved Filtrations: Theory and Applications in Point Cloud Data Analysis». В Nielsen, Frank; Barbaresco, Frédéric (ред.). Geometric Science of Information. Vol. 8085. Berlin, Heidelberg: Springer Berlin Heidelberg. pp.  587– 592. doi :10.1007/978-3-642-40020-9_65. ISBN 978-3-642-40019-3. S2CID  8701910 . Получено 2023-04-05 .
  2. ^ abc Dey, Tamal K.; Shi, Dayu; Wang, Yusu (2019-01-30). «SimBa: эффективный инструмент для аппроксимации устойчивости фильтрации Rips с помощью симплициального пакетного коллапса». ACM Journal of Experimental Algorithmics . 24 : 1.5:1–1.5:16. doi : 10.1145/3284360 . ISSN  1084-6654. S2CID  216028146.
  3. ^ Удо, Стив Ю.; Шихи, Дональд Р. (2013-06-17). "Зигзагообразная зоология". Труды двадцать девятого ежегодного симпозиума по вычислительной геометрии . SoCG '13. Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр.  387–396 . doi :10.1145/2462356.2462371. ISBN 978-1-4503-2031-3. S2CID  485245.
  4. ^ Ли, Хекёнг; Чунг, Му К.; Кан, Хеджин; Ким, Бунг-Нюн; Ли, Донг Су (2011). «Дискриминативная персистентная гомология мозговых сетей». Международный симпозиум IEEE 2011 года по биомедицинской визуализации: от нано до макро . С.  841– ​​844. doi :10.1109/ISBI.2011.5872535. ISBN 978-1-4244-4127-3. S2CID  12511452.
  5. ^ Виеторис, Л. (1 декабря 1927). «Über den höheren Zusammenhang kompakter Räume und eine Klasse von zusammenhangstreuen Abbildungen». Mathematische Annalen (на немецком языке). 97 (1): 454–472 . doi : 10.1007/BF01447877. ISSN  1432-1807. S2CID  121172198.
  6. ^ Громов, М. (1987). «Гиперболические группы». В Gersten, SM (ред.). Очерки по теории групп. Издательства Mathematical Sciences Research Institute. Том 8. Нью-Йорк, Нью-Йорк: Springer New York. С.  75–263 . doi :10.1007/978-1-4613-9586-7_3. ISBN 978-1-4613-9588-1. Получено 2023-04-05 .
  7. ^ Рейтбергер, Генрих (2002), «Леопольд Виеторис (1891–2002)», Notices of the American Mathematical Society, 49 (20).
  8. ^ Бауэр, Ульрих; Ролл, Фабиан (2022). «Гиперболичность Громова, геодезический дефект и кажущиеся пары в фильтрациях Вьеториса – Рипса». В Гоаоке, Ксавьер; Кербер, Майкл (ред.). 38-й Международный симпозиум по вычислительной геометрии (SoCG 2022). Международные труды Лейбница по информатике (LIPIcs). Том. 224. Дагштуль, Германия: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. стр. 15:1–15:15. дои : 10.4230/LIPIcs.SoCG.2022.15 . ISBN 978-3-95977-227-3. S2CID  245124031.
  9. ^ abc Лесник, Майкл (1 апреля 2023 г.). «Конспект лекций для AMAT 840: Многопараметрическая устойчивость» (PDF) . Университет в Олбани, SUNY : 33.
  10. ^ ab Sheehy, Donald R. (2012-06-17). "Линейно-размерные аппроксимации фильтрации Виеториса-Рипса". Труды двадцать восьмого ежегодного симпозиума по вычислительной геометрии . SoCG '12. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр.  239–248 . arXiv : 1203.6786 . doi :10.1145/2261250.2261286. ISBN 978-1-4503-1299-8. S2CID  2392303.
  11. ^ Чемберс, Эрин В .; де Сильва, Вин; Эриксон, Джефф; Грист, Роберт (2010). «Комплексы Виеториса–Рипса плоских точечных множеств». Дискретная и вычислительная геометрия . 44 (1): 75– 90. doi : 10.1007/s00454-009-9209-8 . ISSN  0179-5376. S2CID  7900163.
  12. ^ Эдельсбруннер, Герберт (2010). Вычислительная топология: введение. Дж. Харер. Провиденс, Род-Айленд: Американское математическое общество. ISBN 978-0-8218-4925-5. OCLC  427757156.
  13. ^ Har-Peled, Sariel; Mendel, Manor (2006). «Быстрое построение сетей в маломерных метриках и их применение». SIAM Journal on Computing . 35 (5): 1148– 1184. doi :10.1137/S0097539704446281. ISSN  0097-5397. S2CID  37346335.
  14. ^ Кербер, Майкл; Шараткумар, Р. (2013). «Приблизительный комплекс Чеха в низких и высоких размерностях». В Cai, Leizhen; Cheng, Siu-Wing; Lam, Tak-Wah (ред.). Алгоритмы и вычисления. Конспект лекций по информатике. Том 8283. Берлин, Гейдельберг: Springer. стр.  666– 676. doi :10.1007/978-3-642-45030-3_62. ISBN 978-3-642-45030-3. S2CID  5770506.
  15. ^ Шихи, Дональд Р. (2020-12-03). «Разреженная фильтрация Делоне». arXiv : 2012.01947 [cs.CG].
  16. ^ Чоудхари, Аруни; Кербер, Майкл; Рагвендра, Шарат (2021-09-01). «Улучшенные приближенные фильтрации разрывов со смещенными целочисленными решетками и кубическими комплексами». Журнал прикладной и вычислительной топологии . 5 (3): 425– 458. doi :10.1007/s41468-021-00072-4. ISSN  2367-1734. PMC 8549989. PMID 34722862  . 
  17. ^ Вишванат, Сиддхарт; Шриперумбудур, Бхарат К.; Фукумизу, Кэндзи; Курики, Сатоши (2022-06-03). «Надежный топологический вывод при наличии выбросов». arXiv : 2206.01795 [math.ST].
  18. ^ Карлссон, Гуннар; Зомородян, Афра (2009). «Теория многомерного сохранения». Дискретная и вычислительная геометрия . 42 (1): 71– 93. doi : 10.1007/s00454-009-9176-0 . ISSN  0179-5376.
  19. ^ Лесник, Майкл; Райт, Мэтью (2015-12-01). «Интерактивная визуализация двумерных модулей сохранения». arXiv : 1512.00180 [math.AT].
  20. ^ Ботнан, Магнус Бакке; Лесник, Майкл (13 марта 2023 г.). «Введение в многопараметрическую устойчивость». arXiv : 2203.14289 [math.AT].
  21. ^ DR Sheehy, «Многослойный нерв для геометрического вывода», в CCCG: Канадская конференция по вычислительной геометрии , 2012.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Vietoris–Rips_filtration&oldid=1251187137"