Персистентные гомологии: линейная алгебра в топологическом анализе данных (TDA)

От облака точек к симплициальным комплексам

Алгоритм начинается с построения симплициального комплекса из набора точек данных. Симплексы — это обобщения треугольников на любые размерности: 0-симплексы (вершины), 1-симплексы (ребра), 2-симплексы (треугольники), 3-симплексы (тетраэдры). Вокруг каждой точки данных раздувается сфера радиуса R. Если сферы пересекаются, точки соединяются ребром. Если пересекаются три сферы, образуется заполненный треугольник (комплекс Вьеториса-Рипса). Изменяя радиус R от нуля до бесконечности, мы получаем фильтрацию — вложенную последовательность симплициальных комплексов. Топологические характеристики комплекса (компоненты связности, дыры) рождаются при одном радиусе R и «умирают» (заполняются высшими симплексами) при большем радиусе. Жизненный цикл этих дыр и называется персистентностью (устойчивостью).

Граничный оператор и матрица инцидентности

Для перевода геометрии в алгебру каждому симплексу присваивается индекс в порядке их появления в фильтрации. Затем строится Граничный оператор, который математически описывается гигантской матрицей инцидентности D над конечным полем Галуа GF(2) (где 1+1=0). Столбцы и строки этой матрицы соответствуют всем симплексам. Столбец для треугольника (2-симплекса) содержит единицы в строках, соответствующих его трем ребрам (1-симплексам), формирующим его границу. Фундаментальное топологическое свойство граничного оператора: граница границы всегда равна нулю. В терминах матричной алгебры это означает, что квадрат граничной матрицы строго равен нулевой матрице: D^2 = 0. Это уравнение гарантирует, что образ оператора D вложен в его ядро.

Матричная редукция: вычисление чисел Бетти

Задача нахождения дыр (гомологических классов) сводится к вычислению чисел Бетти, которые алгебраически определяются как размерность ядра граничной матрицы минус размерность ее образа (dim(Ker D) - dim(Im D)). В TDA эта задача решается с помощью алгоритма матричной редукции. По сути, это стандартное Гауссово исключение по столбцам (сложение столбцов по модулю 2), но с одним жестким ограничением: мы можем прибавлять столбец только к столбцу, расположенному правее него. Это ограничение (которое не позволяет матрице превратиться в диагональную) критически важно, так как оно сохраняет информацию о порядке фильтрации (времени рождения и смерти симплексов). Алгоритм заканчивается, когда в каждой строке матрицы остается не более одного самого нижнего ненулевого элемента.

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

Считывание результата с редуцированной матрицы — процесс изящный. Каждый столбец j, который был обнулен в процессе редукции, означает рождение новой топологической дыры (гомологического цикла) на радиусе R_j. Каждый столбец i, в котором остался нижний ненулевой элемент на строке j, означает, что цикл, родившийся на шаге j, был заполнен и «умер» на шаге i. Эти пары (рождение, смерть) наносятся на двумерный график, называемый персистентной диаграммой. Точки, расположенные близко к диагонали (быстро умершие дыры), интерпретируются как математический шум, в то время как точки, живущие долго (расположенные высоко над диагональю), представляют собой фундаментальные, истинные топологические характеристики набора данных, устойчивые к деформациям и шуму.