Офсетная фильтрация

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

Фильтрация смещения (также называемая «объединением шаров») или «объединение дисков» фильтрация ) — это растущая последовательность метрических шаров, используемая для определения размера и масштаба топологических особенностей набора данных. Фильтрация смещения обычно возникает в области устойчивой гомологии и в области анализа топологических данных . Использование объединения шаров для аппроксимации формы геометрических объектов было впервые предложено Фрозини в 1992 году в контексте подмногообразий евклидова пространства . Конструкция была независимо исследована Робинсом в 1998 году и расширена до рассмотрения набора смещений, индексированных по ряду возрастающих масштабных параметров (т. е. растущей последовательности шаров), чтобы наблюдать стабильность топологических особенностей по отношению к аттракторам . Гомологическая персистенция, представленная в этих статьях Фрозини и Робинсом, была впоследствии формализована Эдельсбруннером и др. в своей плодотворной статье 2002 года «Топологическая устойчивость и упрощение». С тех пор фильтрация смещения стала основным примером в изучении вычислительной топологии и анализе данных.

Определение

Позволять $X$ быть конечным множеством в метрическом пространстве $(M,d)$, и для любого $x\in X$ позволять $B(x,\varepsilon )=\{y\in X\mid d(x,y)\leq \varepsilon \}$ быть замкнутым шаром радиуса $\varepsilon$ сосредоточено в $x$. Тогда союз ${\textstyle X^{(\varepsilon )}:=\bigcup _{x\in X}B(x,\varepsilon )}$ известен как смещение $X$ по параметру $\varepsilon$ (или просто $\varepsilon$-смещение $X$).

Рассмотрев совокупность смещений по всем $\varepsilon \in [0,\infty )$ мы получаем семейство пространств ${\mathcal {O}}(X):=\{X^{(\varepsilon )}\mid \varepsilon \in [0,\infty )\}$ где $X^{(\varepsilon )}\subseteq X^{(\varepsilon ^{\prime })}$ в любое время $\varepsilon \leq \varepsilon ^{\prime }$. Так ${\mathcal {O}}(X)$ — это семейство вложенных топологических пространств, индексированных по $\varepsilon$, который определяет фильтрацию , известную как фильтрация смещения на $X$.

Обратите внимание, что фильтрацию смещения также можно рассматривать как функтор. ${\mathcal {O}}(X):[0,\infty )\to \mathbf {Top}$ от категории ЧУМ неотрицательных действительных чисел к категории топологических пространств и непрерывных отображений. У категорической точки зрения есть некоторые преимущества, как это исследовали Бубеник и другие.

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

Стандартное применение теоремы о нерве показывает, что объединение шаров имеет тот же гомотопический тип, что и его нерв, поскольку замкнутые шары выпуклы , а пересечение выпуклых множеств выпукло. Нерв сращения клубочков известен также как комплекс Чеха . который является подкомплексом комплекса Виеторис-Рипс. Поэтому фильтрация смещения слабо эквивалентна фильтрации Чеха (определяемой как нерв каждого смещения по всем параметрам масштаба), поэтому их гомологии изоморфны группы .

Хотя фильтрация Виеториса-Рипса в целом не идентична фильтрации Чеха, в некотором смысле она является приближением. В частности, для набора $X\subset \mathbb {R} ^{d}$ у нас есть цепочка включений $\operatorname {Rips} _{\varepsilon }(X)\subset \operatorname {Cech} _{\varepsilon ^{\prime }}(X)\subset \operatorname {Rips} _{\varepsilon ^{\prime }}(X)$ между комплексами Рипс и Чех на $X$ в любое время $\varepsilon ^{\prime }/\varepsilon \geq {\sqrt {2d/d+1}}$. В общих метрических пространствах мы имеем, что $\operatorname {Cech} _{\varepsilon }(X)\subset \operatorname {Rips} _{2\varepsilon }(X)\subset \operatorname {Cech} _{2\varepsilon }(X)$ для всех $\varepsilon >0$, подразумевая, что фильтры Рипса и Чеха 2-перемежаются относительно расстояния перемежения, введенного Chazal et al. в 2009 году.

Это хорошо известный результат Нийоги, Смейла и Вайнбергера о том, что при наличии достаточно плотной случайной выборки облака точек гладкого подмногообразия в евклидовом пространстве объединение шаров определенного радиуса восстанавливает гомологию объекта посредством деформационного сокращения Комплекс Чех.

Также известно, что фильтрация смещения устойчива к возмущениям базового набора данных. Это следует из того, что фильтрацию смещения можно рассматривать как фильтрацию множества подуровней по отношению к функции расстояния метрического пространства. Устойчивость фильтрации множества подуровней можно сформулировать следующим образом: для любых двух вещественных функций $\gamma ,\kappa$ в топологическом пространстве $T$ такой, что для всех $i\geq 0$, $i{\text{th}}$-мерные модули гомологии на фильтрациях подуровней по $\gamma ,\kappa$ являются поточечными конечномерными, мы имеем $d_{B}({\mathcal {B}}_{i}(\gamma ),{\mathcal {B}}_{i}(\kappa ))\leq d_{\infty }(\gamma ,\kappa )$ где $d_{B}(-)$ и $d_{\infty }(-)$ обозначают расстояния «узкого места» и «sup-norm», соответственно, и ${\mathcal {B}}_{i}(-)$ обозначает $i{\text{th}}$-мерный штрих-код постоянной гомологии. Впервые этот результат устойчивости подуровней был заявлен в 2005 году, но он также следует непосредственно из свойства алгебраической устойчивости, иногда известного как «Теорема изометрии». что было доказано в одном направлении в 2009 году, и другое направление в 2011 году.

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