Signal Processing - March 2016 - 97

vertices {v 1, v 2, ..., v n} corresponding to the given points. We
connect the vertices v i, v j by an edge if the balls B r (x i) and
B r (x j) intersect. If all three of the balls B r (x i), B r (x j), B r (x k)
intersect, we add the triangle [v i, v j, v k] and similarly proceed for
higher-dimension simplices. The result of this procedure is the
ˇ ech complex, which is also often referred to as the nerve of the
C
cover of radius r. An example is shown in Figure 5. The nerve
theorem states that, under certain conditions, the topological
invariants of the union of balls of a cover coincide with those of
ˇ
the Cech
complex [16]. This complex is thus an enlargement of
the point cloud and can be used to glean its topological properties.
ˇ
Unfortunately, the information needed to construct a Cech
complex is not always available since one needs the actual
embedding of these points in some high-dimensional Euclidean space. If, instead, one is just given the distance matrix D of
the points X, the following construction may be used to get a
simplicial complex with, clearly, less information; nevertheless,
it is suitable for further analysis. As a first step, we consider
an abstract collection of vertices {v 1, v 2, ..., v n} corresponding to the given set of data points. We then choose a parameter
r 2 0 and connect the vertices v i, v j by an edge if the distance
between the point x i and x j is less than or equal to 2r. This
ˇ
will yield the same vertices and edges as the Cech
complex
defined previously. Since the actual embedding of the points
ˇ
is not given, we cannot proceed with the Cech
construction.
Instead, we continue by adding a filled-in triangle (2-simplex)
[v i, v j, v k], if all three edges [v i, v j], [v j, v k], [v k, v i] exist. We
then continue by adding higher-dimensional simplices if all
their lower-dimensional faces exist. This is referred to as the flag
complex construction over the one-dimensional (1-D) skeleton.
It is important to note that this flag complex [Figure 6(c)] is
ˇ
different from the corresponding Cech
complex [Figure 6(b)].
It is, in fact, even more of an approximation of the topological
space in question, since embedding is not required as in the
ˇ ech complex case.
C

0.5

0

-0.5

1
0.5

0.5
0

0
-0.5

-0.5

figure 2. A triangulated 2-D ellipsoid.

(a)

(b)

(c)

(d)

figure 3. Some basic simplices: (a) 0-simplex, (b) 1-simplex, (c) 2-simplex, and (d) 3-simplex.

Vietoris-Rips complex
Another construction of a simplicial complex related to a pointcloud X = {x 1, x 2, ..., x n} in a metric space is the Vietoris-Rips
complex. Again, fix a parameter r 2 0. Then, consider an
abstract set of vertices {v 1, v 2, ..., v n} corresponding to the
given set of data points. The simplex [v 1, v 2, ..., v k] is added to
the simplicial complex if and only if the diameter of the set
x 1, x 2, ... x k is less than r. For a big family of metric spaces, the
Vietoris-Rips complex thus constructed has the same points
ˇ
and edges as the Cech
complex with parameter r/2. One advantage of the Vietoris-Rips complex is that it can be determined
from only the distances between the points, without having to
know their exact embedding. The relationship between the
ˇ
Vietoris-Rips and the Cech
complex is as follows [10]:
R r l (X) 1 C r (X) 1 R r (X), r $
rl

2d ,
d+1

where R l (X) is a Vietoris-Rips complex using proximity
ˇ
parameter l, C l (X) is the Cech
complex theoretically
obtained by balls of radius l, and d is the interpoint

figure 4. The standard 2-simplex embedded in R 3 .

figure 5. The construction of a Cˇ ech complex from a set of points.

Euclidean distance. In the following section, we describe how
the aforementioned tools can be applied to signals in a
meaningful and easy-to-understand way.

IEEE Signal Processing Magazine

|

March 2016

|

97



Table of Contents for the Digital Edition of Signal Processing - March 2016

Signal Processing - March 2016 - Cover1
Signal Processing - March 2016 - Cover2
Signal Processing - March 2016 - 1
Signal Processing - March 2016 - 2
Signal Processing - March 2016 - 3
Signal Processing - March 2016 - 4
Signal Processing - March 2016 - 5
Signal Processing - March 2016 - 6
Signal Processing - March 2016 - 7
Signal Processing - March 2016 - 8
Signal Processing - March 2016 - 9
Signal Processing - March 2016 - 10
Signal Processing - March 2016 - 11
Signal Processing - March 2016 - 12
Signal Processing - March 2016 - 13
Signal Processing - March 2016 - 14
Signal Processing - March 2016 - 15
Signal Processing - March 2016 - 16
Signal Processing - March 2016 - 17
Signal Processing - March 2016 - 18
Signal Processing - March 2016 - 19
Signal Processing - March 2016 - 20
Signal Processing - March 2016 - 21
Signal Processing - March 2016 - 22
Signal Processing - March 2016 - 23
Signal Processing - March 2016 - 24
Signal Processing - March 2016 - 25
Signal Processing - March 2016 - 26
Signal Processing - March 2016 - 27
Signal Processing - March 2016 - 28
Signal Processing - March 2016 - 29
Signal Processing - March 2016 - 30
Signal Processing - March 2016 - 31
Signal Processing - March 2016 - 32
Signal Processing - March 2016 - 33
Signal Processing - March 2016 - 34
Signal Processing - March 2016 - 35
Signal Processing - March 2016 - 36
Signal Processing - March 2016 - 37
Signal Processing - March 2016 - 38
Signal Processing - March 2016 - 39
Signal Processing - March 2016 - 40
Signal Processing - March 2016 - 41
Signal Processing - March 2016 - 42
Signal Processing - March 2016 - 43
Signal Processing - March 2016 - 44
Signal Processing - March 2016 - 45
Signal Processing - March 2016 - 46
Signal Processing - March 2016 - 47
Signal Processing - March 2016 - 48
Signal Processing - March 2016 - 49
Signal Processing - March 2016 - 50
Signal Processing - March 2016 - 51
Signal Processing - March 2016 - 52
Signal Processing - March 2016 - 53
Signal Processing - March 2016 - 54
Signal Processing - March 2016 - 55
Signal Processing - March 2016 - 56
Signal Processing - March 2016 - 57
Signal Processing - March 2016 - 58
Signal Processing - March 2016 - 59
Signal Processing - March 2016 - 60
Signal Processing - March 2016 - 61
Signal Processing - March 2016 - 62
Signal Processing - March 2016 - 63
Signal Processing - March 2016 - 64
Signal Processing - March 2016 - 65
Signal Processing - March 2016 - 66
Signal Processing - March 2016 - 67
Signal Processing - March 2016 - 68
Signal Processing - March 2016 - 69
Signal Processing - March 2016 - 70
Signal Processing - March 2016 - 71
Signal Processing - March 2016 - 72
Signal Processing - March 2016 - 73
Signal Processing - March 2016 - 74
Signal Processing - March 2016 - 75
Signal Processing - March 2016 - 76
Signal Processing - March 2016 - 77
Signal Processing - March 2016 - 78
Signal Processing - March 2016 - 79
Signal Processing - March 2016 - 80
Signal Processing - March 2016 - 81
Signal Processing - March 2016 - 82
Signal Processing - March 2016 - 83
Signal Processing - March 2016 - 84
Signal Processing - March 2016 - 85
Signal Processing - March 2016 - 86
Signal Processing - March 2016 - 87
Signal Processing - March 2016 - 88
Signal Processing - March 2016 - 89
Signal Processing - March 2016 - 90
Signal Processing - March 2016 - 91
Signal Processing - March 2016 - 92
Signal Processing - March 2016 - 93
Signal Processing - March 2016 - 94
Signal Processing - March 2016 - 95
Signal Processing - March 2016 - 96
Signal Processing - March 2016 - 97
Signal Processing - March 2016 - 98
Signal Processing - March 2016 - 99
Signal Processing - March 2016 - 100
Signal Processing - March 2016 - 101
Signal Processing - March 2016 - 102
Signal Processing - March 2016 - 103
Signal Processing - March 2016 - 104
Signal Processing - March 2016 - 105
Signal Processing - March 2016 - 106
Signal Processing - March 2016 - 107
Signal Processing - March 2016 - 108
Signal Processing - March 2016 - 109
Signal Processing - March 2016 - 110
Signal Processing - March 2016 - 111
Signal Processing - March 2016 - 112
Signal Processing - March 2016 - 113
Signal Processing - March 2016 - 114
Signal Processing - March 2016 - 115
Signal Processing - March 2016 - 116
Signal Processing - March 2016 - 117
Signal Processing - March 2016 - 118
Signal Processing - March 2016 - 119
Signal Processing - March 2016 - 120
Signal Processing - March 2016 - 121
Signal Processing - March 2016 - 122
Signal Processing - March 2016 - 123
Signal Processing - March 2016 - 124
Signal Processing - March 2016 - 125
Signal Processing - March 2016 - 126
Signal Processing - March 2016 - 127
Signal Processing - March 2016 - 128
Signal Processing - March 2016 - Cover3
Signal Processing - March 2016 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201809
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201807
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201805
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201803
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201801
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0917
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0717
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0517
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0317
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0916
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0716
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0516
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0316
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0915
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0715
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0515
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0315
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0914
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0714
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0514
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0314
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0913
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0713
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0513
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0313
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0912
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0712
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0512
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0312
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0911
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0711
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0511
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0311
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0910
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0710
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0510
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0310
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0909
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0709
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0509
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0309
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1108
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0908
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0708
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0508
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0308
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0108
https://www.nxtbookmedia.com