0
# Witness Complexes
1

2
Classes for constructing witness complexes, which provide memory-efficient approximations of complex topological structures using landmark points. Witness complexes are particularly useful for large datasets where full complex construction is computationally prohibitive.
3

4
## Capabilities
5

6
### WitnessComplex
7

8
Basic witness complex construction using abstract distance functions between landmarks and witnesses.
9

10
```python { .api }
11
class WitnessComplex:
12
    def __init__(self, landmarks, witnesses):
13
        """
14
        Initialize witness complex constructor.
15
        
16
        Parameters:
17
        - landmarks: List of landmark point indices or points
18
        - witnesses: List of witness point indices or points
19
        """
20

21
    def create_simplex_tree(self, max_alpha_square: float, limit_dimension: int = float('inf')):
22
        """
23
        Create simplex tree from the witness complex.
24
        
25
        Parameters:
26
        - max_alpha_square: Maximum alpha square value for filtration
27
        - limit_dimension: Maximum dimension of simplices to include
28
        
29
        Returns:
30
        SimplexTree: Filtered witness complex as simplex tree
31
        """
32
```
33

34
### StrongWitnessComplex
35

36
Strong witness complex variant that requires all faces of a simplex to be witnessed, providing more stable topological features.
37

38
```python { .api }
39
class StrongWitnessComplex:
40
    def __init__(self, landmarks, witnesses):
41
        """
42
        Initialize strong witness complex constructor.
43
        
44
        Parameters:
45
        - landmarks: List of landmark point indices or points
46
        - witnesses: List of witness point indices or points
47
        """
48

49
    def create_simplex_tree(self, max_alpha_square: float, limit_dimension: int = float('inf')):
50
        """
51
        Create simplex tree from the strong witness complex.
52
        
53
        Parameters:
54
        - max_alpha_square: Maximum alpha square value for filtration
55
        - limit_dimension: Maximum dimension of simplices to include
56
        
57
        Returns:
58
        SimplexTree: Filtered strong witness complex as simplex tree
59
        """
60
```
61

62
### EuclideanWitnessComplex
63

64
Witness complex optimized for point clouds embedded in Euclidean space, using efficient distance computations.
65

66
```python { .api }
67
class EuclideanWitnessComplex:
68
    def __init__(self, landmarks, witnesses):
69
        """
70
        Initialize Euclidean witness complex constructor.
71
        
72
        Parameters:
73
        - landmarks: List of landmark points in Euclidean space
74
        - witnesses: List of witness points in Euclidean space
75
        """
76

77
    def create_simplex_tree(self, max_alpha_square: float, limit_dimension: int = float('inf')):
78
        """
79
        Create simplex tree from the Euclidean witness complex.
80
        
81
        Parameters:
82
        - max_alpha_square: Maximum alpha square value for filtration
83
        - limit_dimension: Maximum dimension of simplices to include
84
        
85
        Returns:
86
        SimplexTree: Filtered Euclidean witness complex as simplex tree
87
        """
88
```
89

90
### EuclideanStrongWitnessComplex
91

92
Combination of Euclidean optimization and strong witness conditions, providing the most stable witness complex construction.
93

94
```python { .api }
95
class EuclideanStrongWitnessComplex:
96
    def __init__(self, landmarks, witnesses):
97
        """
98
        Initialize Euclidean strong witness complex constructor.
99
        
100
        Parameters:
101
        - landmarks: List of landmark points in Euclidean space
102
        - witnesses: List of witness points in Euclidean space
103
        """
104

105
    def create_simplex_tree(self, max_alpha_square: float, limit_dimension: int = float('inf')):
106
        """
107
        Create simplex tree from the Euclidean strong witness complex.
108
        
109
        Parameters:
110
        - max_alpha_square: Maximum alpha square value for filtration
111
        - limit_dimension: Maximum dimension of simplices to include
112
        
113
        Returns:
114
        SimplexTree: Filtered Euclidean strong witness complex as simplex tree
115
        """
116
```
117

118
## Usage Examples
119

120
### Basic Witness Complex Construction
121

122
```python
123
import gudhi
124
import numpy as np
125

126
# Generate large point cloud
127
all_points = np.random.random((1000, 3))
128

129
# Select landmarks using farthest point sampling
130
num_landmarks = 50
131
landmark_indices = gudhi.choose_n_farthest_points(all_points, num_landmarks)
132
landmarks = all_points[landmark_indices]
133

134
# Use all points as witnesses
135
witnesses = all_points
136

137
# Create Euclidean witness complex
138
witness_complex = gudhi.EuclideanWitnessComplex(landmarks, witnesses)
139
simplex_tree = witness_complex.create_simplex_tree(
140
    max_alpha_square=0.1,
141
    limit_dimension=2
142
)
143

144
# Compute persistence
145
persistence = simplex_tree.persistence()
146

147
print(f"Landmarks: {len(landmarks)}")
148
print(f"Witnesses: {len(witnesses)}")
149
print(f"Simplices: {simplex_tree.num_simplices()}")
150
print(f"Persistence pairs: {len(persistence)}")
151
```
152

153
### Comparing Witness Complex Variants
154

155
```python
156
import gudhi
157
import numpy as np
158

159
# Generate point cloud
160
points = np.random.random((500, 2))
161

162
# Select landmarks
163
num_landmarks = 30
164
landmark_indices = gudhi.choose_n_farthest_points(points, num_landmarks)
165
landmarks = points[landmark_indices]
166
witnesses = points
167

168
# Create different witness complex variants
169
complexes = {
170
    'Witness': gudhi.EuclideanWitnessComplex(landmarks, witnesses),
171
    'Strong Witness': gudhi.EuclideanStrongWitnessComplex(landmarks, witnesses)
172
}
173

174
max_alpha = 0.05
175
results = {}
176

177
for name, complex_obj in complexes.items():
178
    simplex_tree = complex_obj.create_simplex_tree(
179
        max_alpha_square=max_alpha,
180
        limit_dimension=1
181
    )
182
    persistence = simplex_tree.persistence()
183
    
184
    results[name] = {
185
        'simplices': simplex_tree.num_simplices(),
186
        'persistence_pairs': len(persistence),
187
        'betti_0': len([p for p in persistence if p[0] == 0]),
188
        'betti_1': len([p for p in persistence if p[0] == 1])
189
    }
190

191
for name, stats in results.items():
192
    print(f"{name}:")
193
    print(f"  Simplices: {stats['simplices']}")
194
    print(f"  Persistence pairs: {stats['persistence_pairs']}")
195
    print(f"  Betti numbers: β₀={stats['betti_0']}, β₁={stats['betti_1']}")
196
    print()
197
```
198

199
### Memory-Efficient Large Dataset Analysis
200

201
```python
202
import gudhi
203
import numpy as np
204

205
# Simulate very large dataset
206
np.random.seed(42)
207
large_dataset = np.random.random((10000, 5))  # 10k points in 5D
208

209
# Use witness complex for memory efficiency
210
num_landmarks = 100  # Much smaller than full dataset
211

212
# Select diverse landmarks
213
landmark_indices = gudhi.choose_n_farthest_points(large_dataset, num_landmarks)
214
landmarks = large_dataset[landmark_indices]
215

216
# Subsample witnesses for computational efficiency
217
num_witnesses = 2000
218
witness_indices = gudhi.pick_n_random_points(large_dataset, num_witnesses)
219
witnesses = large_dataset[witness_indices]
220

221
# Create witness complex
222
witness_complex = gudhi.EuclideanStrongWitnessComplex(landmarks, witnesses)
223
simplex_tree = witness_complex.create_simplex_tree(
224
    max_alpha_square=0.2,
225
    limit_dimension=2
226
)
227

228
# Analyze topology
229
persistence = simplex_tree.persistence()
230

231
# Extract significant features
232
significant_features = [
233
    (dim, (birth, death)) for dim, (birth, death) in persistence
234
    if death - birth > 0.01  # Minimum persistence threshold
235
]
236

237
print(f"Original dataset: {len(large_dataset)} points")
238
print(f"Landmarks: {len(landmarks)} points")
239
print(f"Witnesses: {len(witnesses)} points")
240
print(f"Significant topological features: {len(significant_features)}")
241

242
# Visualize persistence diagram
243
gudhi.plot_persistence_diagram(persistence)
244
```
245

246
### Landmark Selection Strategies
247

248
```python
249
import gudhi
250
import numpy as np
251
from sklearn.cluster import KMeans
252

253
# Generate point cloud with clusters
254
np.random.seed(42)
255
cluster_centers = np.array([[0, 0], [3, 0], [1.5, 2.6]])
256
points = []
257
for center in cluster_centers:
258
    cluster_points = np.random.normal(center, 0.3, (100, 2))
259
    points.append(cluster_points)
260
all_points = np.vstack(points)
261

262
# Compare different landmark selection strategies
263
strategies = {
264
    'Farthest Point': lambda pts, n: gudhi.choose_n_farthest_points(pts, n),
265
    'Random': lambda pts, n: gudhi.pick_n_random_points(pts, n),
266
    'K-means Centers': lambda pts, n: KMeans(n_clusters=n, random_state=42).fit(pts).cluster_centers_
267
}
268

269
num_landmarks = 15
270
results = {}
271

272
for strategy_name, strategy_func in strategies.items():
273
    if strategy_name == 'K-means Centers':
274
        landmarks = strategy_func(all_points, num_landmarks)
275
    else:
276
        landmark_indices = strategy_func(all_points, num_landmarks)
277
        landmarks = all_points[landmark_indices]
278
    
279
    # Create witness complex
280
    witness_complex = gudhi.EuclideanWitnessComplex(landmarks, all_points)
281
    simplex_tree = witness_complex.create_simplex_tree(
282
        max_alpha_square=0.5,
283
        limit_dimension=1
284
    )
285
    
286
    persistence = simplex_tree.persistence()
287
    betti_1 = len([p for p in persistence if p[0] == 1 and p[1][1] != float('inf')])
288
    
289
    results[strategy_name] = {
290
        'simplices': simplex_tree.num_simplices(),
291
        'holes_detected': betti_1
292
    }
293

294
print("Landmark selection strategy comparison:")
295
for strategy, stats in results.items():
296
    print(f"{strategy}: {stats['simplices']} simplices, {stats['holes_detected']} holes detected")
297
```