Signal Processing - March 2016 - 99

instance, 2 3 acts on tetrahedra to yield the sum of its 2-simplex
faces (triangles), 2 4 acts on pentatopes to yield the sum of its
3-simplex faces (tetrahedra), and so on.
A matrix representation of these linear operators is thus
obtained, and all of the computations reduce to manipulating
tables as shown here:

v1
21 = v2
v3
v4

e1
1
1
0
0

e2
0
1
1
0

v1

v1
2 1 c2 2 = v 2
v3
v4

e3
1
0
1
0

e4
1
0
0
1

e5
e1
0
e2
1 , 22 =
e3
0
e4
1
e5

21

C0 .

Ker (2 i) .
Im (2 i + 1)

e1

v4
e4

figure 8. An example simplicial complex composed of one 2-simplex v 1
and two 1-simplices e 4, e 5 .

(1)

Note that the element e 1 + e 2 + e 3 of C 1 is but a loop that
follows the cycle v 1 " v 2 " v 3 " v 1 . Another loop that is visible in our example is e 1 + e 5 + e 4 . There is a fundamental
difference between these two loops. The first one bounds a
filled-in triangle, while the second bounds an empty triangle,
or what conceptually can be considered as a true hole. Both of
these loops are elements of the vector space C 1 (X) and, for
both of them, we get 2 1 (e 1 + e 2 + e 3) = 0 = 2 1 (e 1 + e 5 + e 4) .
Thus, both are in the kernel of 2 1 defined as
Ker (2 1) = {x ! C 1 (X): 2 1 (x) = 0} .
The element e 1 + e 2 + e 3 is obtained as the image of
the triangle v 1 under the map 2 2, whereas e 1 + e 5 + e 4
is not the image of a triangle. In other words, define
Im (2 2) = {y ! C 1 (X): 7 x ! C 2 (X) with 2 2 (x) = y}, then e 1 +
e 2 + e 3 ! Im (2 2) and e 1 + e 5 + e 4 " Im (2 2) .
It is also not hard to show that 2 1 o 2 2 = 0 so
Im (2 2) 3 Ker (2 1) . The 1-D homology is obtained by considering the quotient space H 1 (X) = [Ker (2 1) / Im (2 2)] . The quotient space of a vector space V1 with respect to V2 ^V1 /V2 h is the
space of equivalent sets, where two elements in V1 are equivalent if their difference is in V2 . The dimension of V1 /V2 is equal
to dim (V1) - dim (V2) . For more on quotient spaces, we refer
the reader to the chapter "Vector Spaces," Theorem 7 [15]. From
the previous discussion, this construction contains information
about the holes or cycles bounding areas that are not filled in.
The algebraic structure that is imposed on the basic
construction of the spaces makes sequential application of
boundary operators possible in any higher dimension. Formally, one defines these quotients as the homology spaces
H i (X) =

σ1

v3

v1

Formally, the sequential application of these operators on
the different spaces may be written as
C1

e5

e3

1
1
,
1
0
0

v1

22

e2

v1

2 v1 0
2 = v2 0 .
2 v3 0
0 v4 0

C2

v2

The dimensions of these spaces, which are called Betti
numbers, b i = dim (H i), can be used to coarsely describe the
simplicial complex at hand. Intuitively, b 0 counts the number
of connected components, b 1 the number of nonvanishing
holes, b 2 the number of voids, etc.

Higher-order Laplacians
A direct computation of the homology spaces as quotient
vector spaces is computationally expensive and often
unnecessary [5]. Combinatorial Laplacian operators, the
matrix representations of which may be viewed as a generalization of the graph Laplacian, are very useful in providing alternative ways to gather information about the
homology spaces. These operators are related to combinatorial Hodge theory [25]. The motivation of the graph
Laplacian operators on graphs is directly related to probing the structure of graphs by tracking a diffusion (much
like heat diffusion in a solid) through it by way of the
spectral properties of the operator. A similar strategy can
be developed using the boundary operators acting on a
simplicial complex.
Given the boundary operators defined previously, a zeroorder Laplacian defined as L 0 = 2 1 2 T1 , operates on vertices and
in fact coincides with the so-called graph Laplacian, which is
widely used in numerous applications. It is easy to check that
L 0 = D - A, where A is the adjacency matrix of the underlying graph of the complex, and D is the diagonal matrix with
the degrees of the vertices. It is also well known that the spectrum of a graph Laplacian yields clustering information about
a given graph [6]; specifically, the cardinality of the number of
0 - eigenvalues equals the number of disjoint connected components of the graph. As we explain below, this property is generalized by higher-order Laplacian operators, providing efficient
algebraic tools to assess the higher-order topological properties
of any simplicial complex.
In a similar way, we can construct higher-order Laplacian operators, L i = 2 Ti 2 i + 2 i + 1 2 Ti + 1 such that L 1 operates
on edges, L 2 operates on triangular faces, and so on. Much
like the null-space dimension of a graph Laplacian uncovers the number of connected components in a graph (which
can be viewed as zero-cycles), the null space dimension of

IEEE Signal Processing Magazine

|

March 2016

|

99



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