🔵Witness complex на практике

Идея конструкции: вместо построения симплексов на всём облаке X из n точек выбирается подмножество lanlandmark размера m <= n, симплексы строятся только на landmarks, а остальные точки выступают в роли «свидетелей»(не знаю как иначе переформулировать), определяющих, какой симплекс включить в комплекс.
Пример на синтетике через GUDHI:

import numpy as np
import gudhi as gd
import time

np.random.seed(0)
n = 5000
theta = np.linspace(0, 2 * np.pi, n)
X = np.column_stack([np.cos(theta), np.sin(theta)]) + np.random.normal(0, 0.05, (n, 2))

t0 = time.time()
rips = gd.RipsComplex(points=X, max_edge_length=0.5)
st_rips = rips.create_simplex_tree(max_dimension=2)
st_rips.persistence()
t_rips = time.time() - t0

m = 100
landmark_idx = np.random.choice(n, size=m, replace=False)
landmarks = X[landmark_idx]

t0 = time.time()
witness = gd.EuclideanWitnessComplex(landmarks=landmarks, witnesses=X)
st_wit = witness.create_simplex_tree(max_alpha_square=0.25, limit_dimension=2)
st_wit.persistence()
t_wit = time.time() - t0



На облаке n = 5000 точек witness complex с m = 100 landmarks даёт ускорение в 50-100 раз при сохранении основной топологической структуры (одна устойчивая петля H1, соответствующая окружности).
Lazy witness complex добавляет параметр v регулирующий жёсткость остальных нод: при v=0 свидетелем считается точка, которая удовлетворяет условию близости ко всем вершинам симплекса; при v>0 условие ослабляется на расстояние до (v+1)-й по близости landmark. В реальности v=2 даёт хороший баланс между чувствительностью и устойчивостью к шуму.