Стойкость штрих-кода

В топологическом анализе данных штрих -код постоянства , иногда сокращаемый до штрих-кода , представляет собой алгебраический инвариант, связанный с фильтрованным цепным комплексом или модулем постоянства , который характеризует стабильность топологических признаков во всем растущем семействе пространств . ^[1] Формально штрих-код персистентности состоит из мультинабора интервалов фильтрации в расширенной вещественной линии , где длина каждого интервала соответствует времени жизни топологического признака в , обычно построенной на облаке точек , графике , функции или, в более общем смысле — симплициальный комплекс или цепной комплекс . Как правило, более длинные интервалы в штрих-коде соответствуют более надежным характеристикам, тогда как более короткие интервалы с большей вероятностью будут помехой в данных. Постоянный штрих-код — это полный инвариант, который фиксирует всю топологическую информацию при фильтрации. ^[2] В алгебраической топологии персистентные штрих-коды были впервые представлены Сергеем Баранниковым в 1994 году как инварианты «канонических форм». ^[2] состоящий из мультинабора отрезков линий с концами на двух параллельных линиях, а позже, при обработке геометрии, Gunnar Carlsson et al. в 2004 году. ^[3]

Определение

Позволять $\mathbb {F}$ быть фиксированным полем . Рассмотрим вещественную функцию на цепном комплексе $f:K\rightarrow \mathbb {R}$ совместим с дифференциалом, так что $f(\sigma _{i})\leq f(\tau )$ в любое время $\partial \tau =\sum _{i}\sigma _{i}$ в $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

.

Тогда теорема классификации фильтрованных комплексов утверждает, что для любого фильтрованного цепного комплекса над $\mathbb {F}$ , существует линейное преобразование, сохраняющее фильтрацию и приводящее отфильтрованный комплекс к так называемому каноническому виду , канонически определенную прямую сумму отфильтрованных комплексов двух типов: двумерных комплексов с тривиальными гомологиями. $d(e_{a_{j}})=e_{a_{i}}$ и одномерные комплексы с тривиальным дифференциалом $d(e_{a'_{i}})=0$ . ^[2] Мультисет ${\mathcal {B}}_{f}$ интервалов $[a_{i},a_{j})$ или $[a_{i}',\infty )$ описывающий каноническую форму, называется штрих-кодом и является полным инвариантом фильтруемого цепного комплекса.

Понятие постоянного модуля тесно связано с понятием фильтруемого цепного комплекса. Модуль персистентности $M$ проиндексировано более $\mathbb {R}$ состоит из семьи $\mathbb {F}$ - векторные пространства $\{M_{t}\}_{t\in \mathbb {R} }$ и линейные карты $\varphi _{s,t}:M_{s}\to M_{t}$ для каждого $s\leq t$ такой, что $\varphi _{s,t}\circ \varphi _{r,s}=\varphi _{r,t}$ для всех $r\leq s\leq t$ . ^[4] Эта конструкция не является специфичной для $\mathbb {R}$ ; действительно, он работает одинаково с любым полностью упорядоченным набором .

Модуль персистентности $M$ называется конечным типом , если оно содержит конечное число уникальных конечномерных векторных пространств. Последнее условие иногда называют поточечной конечномерностью . ^[5]

Позволять $I$ быть интервалом в $\mathbb {R}$ . Определить модуль персистентности $Q(I)$ с помощью $Q(I_{s})={\begin{cases}0,&{\text{if }}s\notin I;\\\mathbb {F} ,&{\text{otherwise}}\end{cases}}$ , где линейные карты — это тождественная карта внутри интервала. Модуль $Q(I)$ иногда называют интервальным модулем. ^[6]

Тогда для любого $\mathbb {R}$ -индексированный модуль персистентности $M$ конечного типа, существует мультимножество ${\mathcal {B}}_{M}$ интервалов таких, что $M\cong \bigoplus _{I\in {\mathcal {B}}_{M}}Q(I)$ , где прямая сумма модулей персистентности осуществляется по индексу. Мультисет ${\mathcal {B}}_{M}$ называется -кодом штрих $M$ , и он уникален с точностью до перестановки интервалов. ^[3]

Этот результат был распространен на случай поточечных конечномерных модулей персистентности, индексированных по произвольному полностью упорядоченному набору, Уильямом Кроули-Бови и Магнусом Ботнаном в 2020 году: ^[7] основываясь на известных результатах структурной теоремы для конечно порожденных модулей над PID , а также на работе Кэри Уэбба для случая целых чисел . ^[8]

Ссылки

^ Грист, Роберт (26 октября 2007 г.). «Штрих-коды: постоянная топология данных» . Бюллетень Американского математического общества . 45 (1): 61–76. дои : 10.1090/S0273-0979-07-01191-3 . ISSN 0273-0979 .
^ Jump up to: ^а ^б ^с Баранников, Сергей (1994). «Оформленный комплекс Морса и его инварианты» (PDF) . Успехи советской математики . АДВСОВ. 21 : 93–115. дои : 10.1090/advsov/021/03 . ISBN 9780821802373 . S2CID 125829976 .
^ Jump up to: ^а ^б Карлссон, Гуннар; Зомородян, Афра; Коллинз, Энн; Гибас, Леонидас (8 июля 2004 г.). «Постоянство штрих-кодов для фигур» . Материалы симпозиума Eurographics/ACM SIGGRAPH 2004 г. по геометрической обработке . Ницца, Франция: ACM. стр. 124–135. дои : 10.1145/1057432.1057449 . ISBN 978-3-905673-13-5 . S2CID 456712 .
^ Зомородян, Афра; Карлссон, Гуннар (2005). «Вычисление устойчивой гомологии» . Дискретная и вычислительная геометрия . 33 (2): 249–274. дои : 10.1007/s00454-004-1146-y . ISSN 0179-5376 .
^ Кроули-Бови, Уильям (2015). «Декомпозиция поточечных конечномерных модулей персистентности» . Журнал алгебры и ее приложений . 14 (5): 1550066. arXiv : 1210.0819 . дои : 10.1142/S0219498815500668 . ISSN 0219-4988 . S2CID 119635797 .
^ Шазал, Фредерик; де Сильва, Вин; Глисс, Марк; Удо, Стив (2016). Структура и стабильность модулей персистентности . Швейцария. ISBN 978-3-319-42545-0 . OCLC 960458101 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Ботнан, Магнус и Уильям Кроули-Бови. « Декомпозиция модулей персистентности ». Труды Американского математического общества 148, вып. 11 (2020): 4581-4596.
^ Уэбб, Кэри. « Декомпозиция градуированных модулей ». Труды Американского математического общества 94, вып. 4 (1985): 565-571.

[1] Грист, Роберт (26 октября 2007 г.). «Штрих-коды: постоянная топология данных» . Бюллетень Американского математического общества . 45 (1): 61–76. дои : 10.1090/S0273-0979-07-01191-3 . ISSN 0273-0979 .

[Barannikov_1994-2] Jump up to: ^а ^б ^с Баранников, Сергей (1994). «Оформленный комплекс Морса и его инварианты» (PDF) . Успехи советской математики . АДВСОВ. 21 : 93–115. дои : 10.1090/advsov/021/03 . ISBN 9780821802373 . S2CID 125829976 .

[:0-3] Jump up to: ^а ^б Карлссон, Гуннар; Зомородян, Афра; Коллинз, Энн; Гибас, Леонидас (8 июля 2004 г.). «Постоянство штрих-кодов для фигур» . Материалы симпозиума Eurographics/ACM SIGGRAPH 2004 г. по геометрической обработке . Ницца, Франция: ACM. стр. 124–135. дои : 10.1145/1057432.1057449 . ISBN 978-3-905673-13-5 . S2CID 456712 .

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

[5] Кроули-Бови, Уильям (2015). «Декомпозиция поточечных конечномерных модулей персистентности» . Журнал алгебры и ее приложений . 14 (5): 1550066. arXiv : 1210.0819 . дои : 10.1142/S0219498815500668 . ISSN 0219-4988 . S2CID 119635797 .

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

[7] Ботнан, Магнус и Уильям Кроули-Бови. « Декомпозиция модулей персистентности ». Труды Американского математического общества 148, вып. 11 (2020): 4581-4596.

[8] Уэбб, Кэри. « Декомпозиция градуированных модулей ». Труды Американского математического общества 94, вып. 4 (1985): 565-571.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]