# Simplicial Convolutional Filters

Maosheng Yang  Dept. of Intelligent Systems
Delft University of Technology
Delft, The Netherlands
<EMAIL_ADDRESS>Elvin Isufi  Dept. of Intelligent Systems
Delft University of Technology
Delft, The Netherlands
<EMAIL_ADDRESS>Michael T. Schaub  Dept. of Computer Science
RWTH Aachen University
Aachen, Germany
<EMAIL_ADDRESS>Geert Leus  Dept. of Microelectronics
Delft University of Technology
Delft, The Netherlands
<EMAIL_ADDRESS>Maosheng Yang∗, Elvin Isufi∗, Michael T. Schaub† and
Geert Leus‡ Preliminary results were presented at EUSIPCO 2021 [1]. ∗Dept. of
Intelligent Systems, Delft University of Technology (m.yang-2,
e.isufi-1@tudelft.nl). †Dept. of Computer Science, RWTH Aachen University
(schaub@cs.rwth-aachen.de). ‡Dept. of Microelectronics, Delft University of
Technology (g.j.t.leus@tudelft.nl). MY is supported by the TU Delft AI Labs
Programme. MTS received funding from the Ministry of Culture and Science (MKW)
of the German State of North Rhine-Westphalia (”NRW Rückkehrprogramm”).

###### Abstract

We study linear filters for processing signals supported on abstract
topological spaces modeled as simplicial complexes, which may be interpreted
as generalizations of graphs that account for nodes, edges, triangular faces
etc. To process such signals, we develop simplicial convolutional filters
defined as matrix polynomials of the lower and upper Hodge Laplacians. First,
we study the properties of these filters and show that they are linear and
shift-invariant, as well as permutation and orientation equivariant. These
filters can also be implemented in a distributed fashion with a low
computational complexity, as they involve only (multiple rounds of) simplicial
shifting between upper and lower adjacent simplices. Second, focusing on edge-
flows, we study the frequency responses of these filters and examine how we
can use the Hodge-decomposition to delineate gradient, curl and harmonic
frequencies. We discuss how these frequencies correspond to the lower- and the
upper-adjacent couplings and the kernel of the Hodge Laplacian, respectively,
and can be tuned independently by our filter designs. Third, we study
different procedures for designing simplicial convolutional filters and
discuss their relative advantages. Finally, we corroborate our simplicial
filters in several applications: to extract different frequency components of
a simplicial signal, to denoise edge flows, and to analyze financial markets
and traffic networks.

###### Index Terms:

Simplicial complexes, Hodge Laplacians, simplicial filters, filter design,
Chebyshev polynomial

##  I Introduction

Methods to process signals supported on non-Euclidean domains modeled as
graphs have attracted substantial research interests over the last years. Most
of these graph signal processing (GSP) methods focus on signals supported on
nodes, e.g., temperature and humidity measurements in a weather station
network and EEG signals in a brain network [2, 3]. Using linear shift
operators that couple node signals to each other via the edges of the graph,
e.g., in terms of the adjacency or a Laplacian matrix of a graph, we can
design graph filters to process such node signals in manifold ways [2, 3, 4,
5].

However, we are often confronted with signals that are naturally associated to
edges or sets of nodes in real-world applications. For example, for the blood
flow between different areas in the brain [6], the water flow in a
hydrological network, the data flow in a communication network, or the traffic
flow in a road network [7], we typically model them as the flow over the edges
of the network. Edge flows have also been used in statistical ranking,
financial market, game theory and so on [8, 9, 10, 11]. Similarly, in a
coauthorship network, the number of publications with more than two authors
can be seen as a signal supported on sets of nodes [12, 13, 14].

In these cases, rather than focusing on relationships between entities modeled
as nodes, it can be fruitful to study relations between those relationships
modeled as edges themselves. That is, we want to understand couplings between
edges, e.g., mediated through a common incident node (lower adjacency) or
because these edges contribute to a triadic relation (upper adjacency). To
account for such relationships, we can model a (network) system as a
simplicial complex (SC) and analyze signals associated to subsets of nodes,
i.e., simplicial signals, with algebraic tools, the so-called Hodge Laplacians
[15], which generalizes the familiar graph Laplacians.

In addition, the Hodge Laplacian admits a Hodge decomposition, which allows
for an intuitive physical interpretation of signals supported on SCs[15, 16].
Namely, the Hodge decomposition states that any edge flow can be decomposed
into gradient (curl-free), curl (divergence-free) and harmonic components,
respectively. For instance, a water flow may contain a non-cyclic component
which can be seen as the potential difference between water stations, a
locally cyclic component with non-zero curl and a harmonic component being
flow-conservative [17].

Previous works [18, 19] have established a framework to analyze simplicial
signals and focused mostly on low-pass filtering applications. However,
general linear filters for simplicial signals have not been considered in
detail. In this paper, to enable a flexible simplicial signal filtering, we
propose a _simplicial convolutional filter_ via the shift-and-sum operation as
a matrix polynomial of the Hodge Laplacians. It accounts for the lower and
upper adjacencies in an SC, e.g., the relationships between edges via a common
node and a common filled triangle that they form. It allows to filter the
three components given by the Hodge decomposition.

Contributions. Our three main contributions include:

1) Simplicial convolution. We study simplicial shifting via the Hodge
Laplacians as a basic operation to propagate signals locally using both lower-
and upper-connectivities in an SC. Leveraging this shifting and the shift-and-
sum operation, we develop simplicial convolutional filters by aggregating
multi-step shifted signals. Their local shifting operation allows a
distributed implemention of the filter with a cost linear in the number of
simplices. We show such filters are linear, shift-invariant, and equivariant
to permutation and orientation of simplices, which make the labeling and the
orientation of simplices inconsequential to the filter output.

2) Filtering in the spectral domain. Leveraging recent concepts of the
simplicial Fourier transform (SFT) [18], we show that the principles of the
convolutional theorem apply to the proposed filter, i.e., the filter output in
the frequency domain operates as a point-wise multiplication between the
filter frequency response and the SFT of the input signal. We further the
simplicial frequencies and divide them into the gradient, curl and harmonic
frequencies in terms of the subspaces provided by the Hodge decomposition,
ultimately, showing the proposed filter can regulate signals independently in
the three subspaces.

3) Filter Design. To implement a desired frequency response, we first consider
a standard least-squares (LS) approach to design the filter. To avoid the
eigenvalue computation, we then consider a grid-based universal design. While
both strategies may suffer the numerical instability, we finally propose a
Chebyshev polynomial design.

Related works. The idea of processing of signals defined on manifolds and
topological spaces has been discussed in various areas, such as geometry
processing [20], and topological data analysis [21]. For an introduction that
is geared more towards a signal processing perspective see [16, 22, 18].

Filtering of simplicial signals has been partly approached from a
regularization perspective. The works in [17, 19] proposed a regularization
framework based on the edge-Laplacian and the Hodge Laplacian, to promote the
flow conservation property arising as a natural assumption on edge flows. The
solution is essentially a low-pass simplicial filter, as we demonstrate in
this paper. The same regularizer was used in [23, 19] to perform edge flow
interpolation by exploiting the divergence-free and curl-free behaviors of
real-world flows. Nevertheless these assumptions do not always hold true and
the filtering via regularizations has limited degree of freedom.

Filtering simplicial signals has been further analyzed in the Fourier domain,
akin to how graph filters are analyzed via the graph Fourier transform (GFT)
[2]. The simplicial Fourier transform (SFT) through the eigendecomposition of
the Hodge Laplacian was introduced in [18]. The eigenvectors provide the
simplicial Fourier basis and the eigenvalues carry the frequency notion.
However, filtering in the spectral domain via a pointwise multiplication is
computationally expensive.

In parallel, different neural network architectures on SCs have been developed
to learn from the simplicial data, e.g., [24, 25, 26, 27, 28, 29]. Throughout
the works, it is seen that the linear operation in different neural
convolutional layers can be understood as a simplicial filtering step with
different filter parameters.

Outline. We begin by introducing some preliminaries in Section II. Then we
propose the simplicial convolutional filter in Section III and investigate its
properties. In Section IV, we first introduce the simplicial Fourier transform
and study the simplicial frequency. We then analyze the simplicial filter in
the spectral domain. To achieve a desired filtering, different filter design
approaches are discussed in Section V. Finally, we use the simplicial filter
for subcomponent extraction and edge flow denoising, and apply it to the
financial market and transportation networks in Section VI.

##  II Simplicial Complexes, Signals and Hodge Laplacians

In this section, we review SCs [15, 30] and signals supported on simplices
[18, 19]. We also introduce the Hodge Laplacians as an algebraic
representation of a simplicial complex, that acts as a shift operator for
simplicial signals.

Simplicial complexes. Given a finite set of vertices $\mathcal{V}$, an order
$k$-simplex $\mathcal{S}^{k}$ is a subset of $\mathcal{V}$ with cardinality
$k+1$. A subset of a $k$-simplex $\mathcal{S}^{k}$ with cardinality $k$ is
called a _face_ of $\mathcal{S}^{k}$; hence, $\mathcal{S}^{k}$ has $k+1$
faces. A _coface_ of a $k$-simplex is a simplex $\mathcal{S}^{k+1}$ that
includes it. Based on the geometric realizations, we call a $0$-simplex a
node, a $1$-simplex an edge and a $2$-simplex a filled triangle. An empty
triangle formed by three vertices which has no pairwise relations between them
is not a 2-simplex. In this paper, we refer to 2-simplices as triangles for
simplicity. In Fig. 1a, edge $\\{5,6\\}$ has nodes $\\{5\\}$ and $\\{6\\}$ as
its faces and triangle $\\{5,6,7\\}$ as its coface.

A simplicial complex $\mathcal{X}$ is a finite collection of simplices with an
inclusion property: for any $\mathcal{S}^{k}\in\mathcal{X}$ all its faces
$\mathcal{S}^{k-1}\subset\mathcal{S}^{k}$ are also part of the simplicial
complex, i.e., $\mathcal{S}^{k-1}\in\mathcal{X}$. The order of an SC is the
largest order of its simplices. For an SC of order $K$, we collect the
$k$-simplices into a set
$\mathcal{X}^{k}=\\{\mathcal{S}_{1}^{k},\dots,\mathcal{S}^{k}_{N_{k}}\\}$
where $N_{k}=|\mathcal{X}^{k}|$ is the number of $k$-simplices [15, 18]. A
graph is an SC of order $1$ with $N_{0}$ nodes and $N_{1}$ edges. Fig. 1a is
an SC of order 2 including nodes, edges and triangles.

(a) A simplicial complex. (b) A random edge flow.

Figure 1: (a): an SC of order 2 containing seven nodes, ten edges and three
triangles (the shaded areas). The reference orientation of a node is trivial,
that of an edge is indicated by the arrow on the edge and that of a triangle
by the arc arrow. (b): A random edge flow, where a negative flow indicates
that the actual flow direction is opposite to the reference edge orientation
and the magnitude is denoted by the edge width.

Two $k$-simplices in an SC are _lower adjacent_ if they have a common face and
are _upper adjacent_ if they are both faces of a common $(k+1)$-simplex. Thus,
for the simplex $\mathcal{S}_{i}^{k}$, we define its _lower neighbourhood_
$\mathcal{N}^{k}_{i,{\ell}}$ as the set of its lower adjacent $k$-simplices
and its _upper neighbourhood_ $\mathcal{N}^{k}_{i,{\rm{u}}}$ as the set of its
upper adjacent $k$-simplices. For the $i$th edge $\\{5,6\\}$ in Fig. 1a, we
have that
$\mathcal{N}^{1}_{i,{{\ell}}}=\\{\\{4,5\\},\\{3,6\\},\\{5,7\\},\\{6,7\\}\\}$,
and the upper neighborhood is $\mathcal{N}^{1}_{i,{{\rm
u}}}=\\{\\{5,7\\},\\{6,7\\}\\}$.

Simplicial signals. For computational purposes, we fix an (arbitrary)
reference orientation (see [15] for more details) for each simplex according
to the lexicographical ordering of its vertices. Given this reference
orientation for $k$-simplices, we define a $k$-_simplicial signal_
$\mathbf{s}^{k}=[s^{k}_{1},\dots,s^{k}_{N_{k}}]^{\top}\in\mathbb{R}^{N_{k}}$
by attributing the value $s^{k}_{i}$ to the $i$th $k$-simplex
$\mathcal{S}_{i}^{k}$. If the signal value $s_{i}^{k}$ is positive, then the
corresponding signal is along the reference orientation; otherwise, opposite
to the reference orientation. To ease the exposition, we denote a node signal
by $\mathbf{v}=[v_{1},\dots,v_{N_{0}}]^{\top}\in\mathbb{R}^{N_{0}}$ and an
edge flow by $\mathbf{f}=[f_{1},\dots,f_{N_{1}}]^{\top}\in\mathbb{R}^{N_{1}}$.
In Fig. 1b, an edge flow is shown where a negative value indicates the flow
direction is opposite to the reference orientation of the edge.

Hodge Laplacians. We can describe the relationships between $(k-1)$-simplices
and $k$-simplices by the $k$th incidence matrix
$\mathbf{B}_{k}\in\mathbb{R}^{N_{k-1}\times N_{k}}$, which maps each
$k$-simplex to its faces, $(k-1)$-simplices. See more details in [18, 30].
Specifically, $\mathbf{B}_{1}$ is the node-edge incidence matrix, and
$\mathbf{B}_{2}$ is the edge-triangle incidence matrix. By definition,
incidence matrices follow a property [15]

$\mathbf{B}_{k}\mathbf{B}_{k+1}=\mathbf{0}.$ (1)

Upon defining the incidence matrices, we can describe an SC $\mathcal{X}$ of
order $K$ via the Hodge Laplacians

$\mathbf{L}_{k}=\mathbf{B}_{k}^{\top}\mathbf{B}_{k}+\mathbf{B}_{k+1}\mathbf{B}_{k+1}^{\top},\quad
k=1,\dots,K-1,\\\ $ (2)

with the graph Laplacian $\mathbf{L}_{0}=\mathbf{B}_{1}\mathbf{B}_{1}^{\top}$
and $\mathbf{L}_{K}=\mathbf{B}_{K}^{\top}\mathbf{B}_{K}$. The $k$th-_Hodge
Laplacian_ $\mathbf{L}_{k}$ contains the _lower Laplacian_
$\mathbf{L}_{k,\ell}\triangleq\mathbf{B}_{k}^{\top}\mathbf{B}_{k}$ and the
_upper Laplacian_
$\mathbf{L}_{k,\rm{u}}\triangleq\mathbf{B}_{k+1}\mathbf{B}_{k+1}^{\top}$. The
lower Laplacian encodes the lower adjacency relationships between simplices
through faces while the upper one encodes the upper adjacency relationships
through cofaces. In particular, $\mathbf{L}_{1,\ell}$ encodes the edge
adjacencies through their incident nodes and $\mathbf{L}_{1,\rm{u}}$ through
the common triangles that they form.

##  III Simplicial convolutional filters

In this section, we propose a simplicial convolutional filter based on the
Hodge Laplacian. We study its basic building block, the simplicial shifting,
and show how its local characteristics make it amenable to a distributed
implementation. We then look into the properties of shift-invariance and
permutation and orientation equivariance in the simplicial domain.

Given the $k$th-Hodge Laplacian $\mathbf{L}_{k}$, we define a _simplicial
convolutional filter_ to process a $k$-simplicial signal $\mathbf{s}^{k}$ as

$\mathbf{H}_{k}=h_{0}\mathbf{I}+\sum_{l_{1}=1}^{L_{1}}\alpha_{l_{1}}(\mathbf{B}_{k}^{\top}\mathbf{B}_{k})^{l_{1}}+\sum_{l_{2}=1}^{L_{2}}\beta_{l_{2}}(\mathbf{B}_{k+1}\mathbf{B}_{k+1}^{\top})^{l_{2}},$
(3)

where
$\mathbf{H}_{k}:=\mathbf{H}(\mathbf{L}_{k,{\ell}},\mathbf{L}_{k,{\rm{u}}})$ is
a matrix polynomial of the lower and upper Hodge Laplacians with filter
coefficients $h_{0}$,
$\boldsymbol{\alpha}=[\alpha_{1},\dots,\alpha_{L_{1}}]^{\top}$,
$\boldsymbol{\beta}=[\beta_{1},\dots,\beta_{L_{2}}]^{\top}$ and filter orders
$L_{1},L_{2}$. When $k=0$, we obtain the graph convolutional filter
$\mathbf{H}_{0}:=\mathbf{H}(\mathbf{L}_{0})$ built upon the graph Laplacian
$\mathbf{L}_{0}$ [2, 4, 5].

Through the following discussions, it is seen that by assigning two different
sets of coefficients to the lower and upper Laplacian parts in (3), the filter
can account for the lower and upper adjacencies differently which corresponds
to a more flexible control on the frequency response. Instead, if
$L_{1}=L_{2}$ and $\boldsymbol{\alpha}=\boldsymbol{\beta}$, it does not
differentiate between the two adjacencies and loses the expressive power.

When applying $\mathbf{H}_{k}$ to a $k$-simplicial signal $\mathbf{s}^{k}$, it
generates an output $\mathbf{s}^{k}_{\rm o}=\mathbf{H}_{k}\mathbf{s}^{k}$
which is a _shift-and-sum_ operation where the filter $\mathbf{H}_{k}$ first
shifts the signal $L_{1}$ times over the lower neighborhoods and $L_{2}$ times
over the upper neighbourhoods, and then sums the shifted results. This is
analogous to the convolutions of graph signals, images and time series [2].

Simplicial shifting and local implementation. For simplicity, we study the
edge filter $\mathbf{H}_{1}$ applied to an edge flow $\mathbf{f}$. We can
express the output as

$\textstyle\mathbf{f}_{\rm{o}}=\mathbf{H}_{1}\mathbf{f}=h_{0}\mathbf{f}+\sum_{l_{1}=1}^{L_{1}}\alpha_{l_{1}}\mathbf{L}_{1,\ell}^{l_{1}}\mathbf{f}+\sum_{l_{2}=1}^{L_{2}}\beta_{l_{2}}\mathbf{L}_{1,\rm{u}}^{l_{2}}\mathbf{f},$
(4)

where the basic operation consists of applying different powers of the
lower/upper Hodge Laplacian to the edge flow. This basic operation is denoted
_simplicial shifting_. Let us first consider the one-step lower shifting
$\mathbf{f}_{\ell}^{(1)}\triangleq\mathbf{L}_{1,\ell}\mathbf{f}$ and one-step
upper shifting
$\mathbf{f}_{\rm{u}}^{(1)}\triangleq\mathbf{L}_{1,\rm{u}}\mathbf{f}$. We can
express the one-step shifted results on the $i$th edge,
$[\mathbf{f}_{\ell}^{(1)}]_{i}$ and $[\mathbf{f}_{\rm{u}}^{(1)}]_{i}$, as

i
$\displaystyle=\textstyle\sum_{j\in\\{\mathcal{N}^{1}_{{\ell},i}\cup\;i\\}}[\mathbf{L}_{1,{\ell}}]_{ij}[\mathbf{f}]_{j},$
(5) $\displaystyle[\mathbf{f}_{\rm{u}}^{(1)}]_{i}$
$\displaystyle=\textstyle\sum_{j\in\\{\mathcal{N}^{1}_{{\rm
u},i}\cup\;i\\}}[\mathbf{L}_{1,{\rm u}}]_{ij}[\mathbf{f}]_{j},$

which are the weighted linear combinations of the edge flows on the lower and
upper neighbourhoods, $\mathcal{N}^{1}_{{\ell},i}$ and $\mathcal{N}^{1}_{{\rm
u},i}$, of edge $i$. This implies that one-step shifting is a _local
operation_ in the edge space within the direct lower/upper neighbourhoods.

(a) An indicator flow $\mathbf{f}$ (b) $\mathbf{L}_{1,\ell}\mathbf{f}$ (c)
$\mathbf{L}^{2}_{1,\ell}\mathbf{f}$ (d) $\mathbf{L}_{1,\rm{u}}\mathbf{f}$ (e)
$\mathbf{L}^{2}_{1,\rm{u}}\mathbf{f}$ (f) $\mathbf{L}^{2}_{1,\ell}\mathbf{f}$
\+ $\mathbf{L}^{2}_{1,\rm{u}}\mathbf{f}$

Figure 2: Simplicial shifting. (a): An edge flow indicator $\mathbf{f}$ of
edge $\\{5,6\\}$. (b): One-step lower shifting
$\mathbf{L}_{1,\ell}\mathbf{f}$. Edge $\\{5,6\\}$ and its direct lower
neighbouring edges (green) update their flows by aggregating information from
their lower neighbours and themselves. (c): Two-step lower shifting
$\mathbf{L}_{1,\ell}^{2}\mathbf{f}$. Lower neighbouring edges (green) update
their flows through faces within two hops away from edge $\\{5,6\\}$, which
can be obtained by one-step shifting $\mathbf{L}_{1,\ell}\mathbf{f}_{\ell}$.
(d): One-step upper shifting $\mathbf{L}_{1,\rm{u}}\mathbf{f}$. Edge
$\\{5,6\\}$ and its upper neighbours (red) update their flows through local
information aggregation. (e): Two-step upper shifting
$\mathbf{L}_{1,\rm{u}}^{2}\mathbf{f}$. The output is localized within the one-
hop upper neighbourhood, as there is no upper neighbouring edge two hops away
from $\\{5,6\\}$. (f): Two-step shifting result
$\mathbf{L}_{1}^{2}\mathbf{f}$, as the sum of (c) and (e).

Consider now the $l$-step lower shifting of an edge flow $\mathbf{f}$,
$\textstyle\mathbf{f}_{\ell}^{(l)}\triangleq\mathbf{L}_{1,\ell}^{l}\mathbf{f}=\mathbf{L}_{1,\ell}\mathbf{f}_{\ell}^{(l-1)}$,
where the second equality indicates that the $l$-step lower shifting can be
computed as a one-step shifting of the previously shifted result,
$\mathbf{f}_{\ell}^{(l-1)}$. Accordingly, the $l$-step upper shifting follows
$\mathbf{f}_{\rm{u}}^{(l)}\triangleq\mathbf{L}_{1,\rm{u}}^{l}\mathbf{f}=\mathbf{L}_{1,\rm{u}}\mathbf{f}_{\rm{u}}^{(l-1)}$.
Thus, the simplicial shifting allows a recursive implementation. For example,
the two-step shifted results, $\mathbf{f}_{\ell}^{(2)}$ and
$\mathbf{f}_{\rm{u}}^{(2)}$, can be computed from $\mathbf{f}_{\ell}^{(1)}$
and $\mathbf{f}_{\rm{u}}^{(1)}$ via another shifting. Each edge collects the
flows on its lower and upper neighbours two hops away. Fig. 2 illustrates such
shifting operations. Thus, the $l$-step shifted results
$\mathbf{f}_{\ell}^{(l)}$ and $\mathbf{f}_{\rm{u}}^{(l)}$ contain the
information over the $l$-hop lower and upper neighbourhoods. Finally, we can
express the output (4) as

$\textstyle\mathbf{f}_{\rm{o}}=h_{0}\mathbf{f}^{(0)}+\sum_{l_{1}=1}^{L_{1}}\alpha_{l_{1}}\mathbf{f}^{(l_{1})}_{\ell}+\sum_{l_{2}=1}^{L_{2}}\beta_{l_{2}}\mathbf{f}^{(l_{2})}_{\rm{u}},$
(6)

which is a weighted linear combination of the different step lower and upper
shifted simplicial signals. Fig. 3 illustrates such a shift-and-sum operation.
Thus, the simplicial convolutional filter is _simplicial local_ , i.e., the
output $\mathbf{f}_{\rm o}$ is localized in the $L_{1}$-hop lower neighborhood
and $L_{2}$-hop upper neighborhood of an edge. If two edges are lower adjacent
more than $L_{1}$ hops away or upper adjacent more than $L_{2}$ hops away,
$\mathbf{H}_{1}$ does not cause any interaction between them.

As a local operation within the simplicial neighborhood, the simplicial
shifting allows for a distributed filter implementation, in which each edge
updates its information only by a direct communication with its lower and
upper neighbors. The communication complexity mainly comes from operation (5),
which is of order $\mathcal{O}(D_{\ell})$ with
$D_{\ell}:=\text{max}\\{|\mathcal{N}_{{\ell},i}^{1}|_{i=1}^{N_{1}}\\}$ for the
lower simplicial shifting at each edge and $\mathcal{O}(D_{\rm u})$ with
$D_{\rm{u}}:=\text{max}\\{|\mathcal{N}_{{\rm u},i}^{1}|_{i=1}^{N_{1}}\\}$ for
the upper simplicial shifting, i.e., the maximum number of lower and upper
neighbors among all edges, respectively. Then, the total communication cost of
the distributed implementation for each edge is
$\mathcal{O}(D_{\ell}L_{1}+D_{\rm u}L_{2})$ due to the $L_{1}$ lower shifting
steps and $L_{2}$ upper ones.

Figure 3: Simplicial convolutional filtering is a shift-and-sum operation.

Linearity and shift invariance. Simplicial convolutional filters are linear
operators that are invariant to shifts as stated by the following proposition.

###### Proposition 1

The simplicial filter $\mathbf{H}_{k}$ [cf. (3)] is linear and shift-
invariant. Specifically, in the edge space, given two edge flows
$\mathbf{f}_{1}$ and $\mathbf{f}_{2}$ and a simplicial filter
$\mathbf{H}_{1}$, we have

$\displaystyle\text{Linearity}:$
$\displaystyle\,\,\mathbf{H}_{1}(a\mathbf{f}_{1}+b\mathbf{f}_{2})=a\mathbf{H}_{1}\mathbf{f}_{1}+b\mathbf{H}_{1}\mathbf{f}_{2},$
(7) $\displaystyle\text{Shift-invariance}:$
$\displaystyle\,\,\mathbf{L}_{1,\ell}\big{(}\mathbf{H}_{1}\mathbf{f}_{1}\big{)}=\mathbf{H}_{1}\big{(}\mathbf{L}_{1,\ell}\mathbf{f}\big{)},$
$\displaystyle\,\,\mathbf{L}_{1,\rm{u}}\big{(}\mathbf{H}_{1}\mathbf{f}_{1}\big{)}=\mathbf{H}_{1}\big{(}\mathbf{L}_{1,\rm{u}}\mathbf{f}\big{)}.$

###### Proof:

See Appendix. A in supplementary materials. ∎

The linearity of the simplicial filter states that the simplicial filter
output of a linear combination of input simplicial signals equals the linear
combination of the outputs to each signal. The shift-invariance implies that
applying a lower or upper Hodge Laplacian to the simplicial output is
equivalent to applying them to the input signal prior to filtering.
Consequently, it holds that
$\mathbf{H}_{1}\mathbf{H}_{1}^{\prime}\mathbf{f}=\mathbf{H}_{1}^{\prime}\mathbf{H}_{1}\mathbf{f}$
for two filters $\mathbf{H}_{1}$ and $\mathbf{H}_{1}^{\prime}$.

Equivariances. In an SC, the labeling and the reference orientation of the
simplices should not affect the filter output. We show that this is indeed the
case. We can model the simplex relabeling of simplices by a set of permutation
matrices

$\textstyle\mathcal{P}=\\{\mathbf{P}_{k}\in\\{0,1\\}^{N_{k}\times
N_{k}}:\mathbf{P}_{k}\mathbf{1}=\mathbf{1},\mathbf{P}_{k}^{\top}\mathbf{1}=\mathbf{1},k\geq
0\\}.$ (8)

Let a set of matrices
$\bar{\mathcal{P}}=(\mathbf{P}_{0},\mathbf{P}_{1},\dots)\subset\mathcal{P}$
denote a sequence of permutations in an SC. After a relabeling of the
simplices by $\bar{\mathcal{P}}$, signal $\mathbf{s}^{k}$ becomes
$\mathbf{P}_{k}\mathbf{s}^{k}$, i.e., a reordering of the entries of
$\mathbf{s}^{k}$. Incidence matrix $\mathbf{B}_{k}$ becomes
$\bar{\mathbf{B}}_{k}=\mathbf{P}_{k-1}\mathbf{B}_{k}\mathbf{P}_{k}$, i.e., a
reordering of the rows and columns of $\mathbf{B}_{k}$. Likewise, for
$\mathbf{L}_{k}$, we get
$\bar{\mathbf{L}}_{k}=\mathbf{P}_{k}\mathbf{L}_{k}\mathbf{P}^{\top}$.

######  Proposition 2 (Permutation equivariance)

Consider the Hodge Laplacians $\mathbf{L}_{k}$ and
$\bar{\mathbf{L}}_{k}=\mathbf{P}_{k}\mathbf{L}_{k}\mathbf{P}^{\top}$ for a
permutation sequence $\bar{\mathcal{P}}$. For the simplicial signals
$\mathbf{s}^{k}$ and $\bar{\mathbf{s}}^{k}=\mathbf{P}_{k}\mathbf{s}^{k}$, with
$\bar{\mathbf{H}}_{k}:=\mathbf{H}(\bar{\mathbf{L}}_{k})$ [cf. (3)], the
simplicial filter outputs
$\mathbf{s}^{k}_{\rm{o}}:=\mathbf{H}_{k}\mathbf{s}^{k}$ and
$\bar{\mathbf{s}}^{k}_{\rm{o}}:=\bar{\mathbf{H}}_{k}\bar{\mathbf{s}}^{k}$
satisfy

$\bar{\mathbf{s}}^{k}_{\rm{o}}:=\bar{\mathbf{H}}_{k}\bar{\mathbf{s}}^{k}=\bar{\mathbf{H}}_{k}(\mathbf{P}_{k}\mathbf{s}^{k})=\mathbf{P}_{k}\mathbf{H}_{k}\mathbf{s}^{k}:=\mathbf{P}_{k}\mathbf{s}_{\rm{o}}^{k}.$
(9)

###### Proof:

See Appendix. B in supplementary materials. ∎

A new reference orientation of a $k$-simplex leads to a multiplication by $-1$
of the rows and columns of the incidence matrices $\mathbf{B}_{k}$ and
$\mathbf{B}_{k+1}$ where the $k$-simplex appears and it also flips the sign of
the corresponding simplicial signal. This can be modeled by a diagonal matrix
$\mathbf{D}_{k}$ from the set

$\textstyle\mathcal{D}=\\{\mathbf{D}_{k}=\text{diag}(\mathbf{d}_{k}):\mathbf{d}_{k}\in\\{\pm
1\\}^{N_{k}},k\geq 1,\mathbf{d}_{0}=\mathbf{1}\\},$ (10)

with $\mathbf{d}_{0}=\mathbf{1}$ indicating that the orientation of the nodes
is trivial. Denote a sequence of orientation changes by
$\bar{\mathcal{D}}=(\mathbf{D}_{0},\mathbf{D}_{1},\dots)\subset\mathcal{D}$. A
$k$-simplicial signal $\mathbf{s}^{k}$ becomes $\mathbf{D}_{k}\mathbf{s}^{k}$
after an orientation change by $\bar{\mathcal{D}}$. Accordingly, the incidence
matrix $\mathbf{B}_{k}$ becomes
$\bar{\mathbf{B}}_{k}=\mathbf{D}_{k-1}\mathbf{B}_{k}\mathbf{D}_{k}$ and the
Hodge Laplacian $\mathbf{L}_{k}$ becomes
$\bar{\mathbf{L}}_{k}=\mathbf{D}_{k}\mathbf{L}_{k}\mathbf{D}_{k}$.

######  Proposition 3 (Orientation equivariance)

Consider the Hodge Laplacians $\mathbf{L}_{k}$ and
$\bar{\mathbf{L}}_{k}=\mathbf{D}_{k}\mathbf{L}_{k}\mathbf{D}_{k}$ for a
sequence of orientation changes $\bar{\mathcal{D}}$. For the simplicial
signals $\mathbf{s}^{k}$ and
$\bar{\mathbf{s}}^{k}=\mathbf{D}_{k}\mathbf{s}^{k}$, with
$\bar{\mathbf{H}}_{k}=\mathbf{H}(\bar{\mathbf{L}}_{k})$, the simplicial filter
outputs $\mathbf{s}^{k}_{\rm{o}}:=\mathbf{H}_{k}\mathbf{s}^{k}$ and
$\bar{\mathbf{s}}^{k}_{\rm{o}}:=\bar{\mathbf{H}}_{k}\bar{\mathbf{s}}^{k}$
satisfy

$\bar{\mathbf{s}}^{k}_{\rm{o}}:=\bar{\mathbf{H}}_{k}\bar{\mathbf{s}}^{k}=\bar{\mathbf{H}}_{k}(\mathbf{D}_{k}\mathbf{s}^{k})=\mathbf{D}_{k}\mathbf{H}_{k}\mathbf{s}^{k}:=\mathbf{D}_{k}\mathbf{s}_{\rm{o}}^{k}.$
(11)

###### Proof:

See Appendix C in supplementary materials. ∎

The above two propositions state that the simplicial filter $\mathbf{H}_{k}$
is equivariant to permutation and orientation changes, which asserts that the
labeling and the reference orientation of simplices are inconsequential to the
filter output. These equivariances also imply that we can learn a filter to
process a given simplex by seeing as examples only permuted and reoriented
versions of it: if two parts of an SC are topologically identical and the
simplices support identical flows, a simplicial convolutional filter yields
identical outputs. These two properties have been previously reported in the
context neural network on SCs [28, 24, 26].

##  IV Spectral Analysis of Simplicial Filters

We now analyze the spectral properties of the simplicial convolutional filter.
First, we introduce the Hodge decomposition and review the simplicial Fourier
transform (SFT) [18]. Then, we investigate the simplicial frequency in terms
of the Hodge decomposition. By defining three frequency types, we characterize
the frequency response of the filter.

###  IV-A Hodge Decomposition

The Hodge decomposition in the edge space states that:

$\mathbb{R}^{N_{1}}=\text{im}(\mathbf{B}_{1}^{\top})\oplus\text{im}(\mathbf{B}_{2})\oplus\text{ker}(\mathbf{L}_{1})$
(12)

where $\text{im}(\cdot)$ and $\text{ker}(\cdot)$ are the image and kernel of a
matrix. This implies that the edge space is composed of three orthogonal
subspaces, namely, the gradient space $\text{im}(\mathbf{B}_{1}^{\top})$, the
curl space $\text{im}(\mathbf{B}_{2})$, and the harmonic space
$\text{ker}(\mathbf{L}_{1})$ [15, 19]. Thus, any edge flow
$\mathbf{f}\in\mathbb{R}^{N_{1}}$ can be decomposed into three orthogonal
components
$\mathbf{f}=\mathbf{f}_{\rm{G}}+\mathbf{f}_{\rm{C}}+\mathbf{f}_{\rm{H}},$
which are the _gradient component_
$\mathbf{f}_{\rm{G}}\in\text{im}(\mathbf{B}_{1}^{\top})$, the _curl component_
$\mathbf{f}_{\rm{C}}\in\text{im}(\mathbf{B}_{2})$, and the _harmonic
component_ $\mathbf{f}_{\rm{H}}\in\text{ker}(\mathbf{L}_{1})$, respectively.
Furthermore, the incidence matrices $\mathbf{B}_{1}$, $\mathbf{B}_{2}$ and
their adjoints can be interpreted as follows [19, 18].

Divergence operator $\mathbf{B}_{1}$. The incidence matrix $\mathbf{B}_{1}$
acts as a _divergence operator_. By applying it to an edge flow $\mathbf{f}$,
we compute the divergence of the flow,
$\text{div}(\mathbf{f})=\mathbf{B}_{1}\mathbf{f}$. The $i$th entry of
$\text{div}(\mathbf{f})$ is the netflow passing through the $i$th vertex,
i.e., the difference between the total inflow and outflow at vertex $i$. A
vertex is a source or sink if it has a nonzero netflow.

Gradient operator $\mathbf{B}_{1}^{\top}$. The adjoint operator
$\mathbf{B}_{1}^{\top}$ is called the _gradient operator_ , which takes the
difference between node signals along the oriented edges to induce an edge
flow, $\mathbf{f}_{\rm{G}}=\mathbf{B}_{1}^{\top}\mathbf{v}$. We call
$\mathbf{f}_{\rm{G}}\in\text{im}(\mathbf{B}_{1}^{\top})$ a _gradient flow_ and
subspace $\text{im}(\mathbf{B}_{1}^{\top})$ the _gradient space_ , as any
gradient flow can be induced from a node signal via the gradient operator.

Curl adjoint $\mathbf{B}_{2}$. By applying matrix $\mathbf{B}_{2}$ to a
triangle signal $\mathbf{t}\in\mathbb{R}^{N_{3}}$, we can induce a _curl flow_
, $\mathbf{f}_{\rm{C}}=\mathbf{B}_{2}\mathbf{t}$, corresponding to a flow
locally circling along the edges of triangles. The space
$\text{im}(\mathbf{B}_{2})$ is the _curl space_ as any flow in it can be
induced from a triangle signal.

Curl operator $\mathbf{B}_{2}^{\top}$. By applying the operator
$\mathbf{B}_{2}^{\top}$ to an edge flow $\mathbf{f}$, we compute its curl as
$\text{curl}(\mathbf{f})=\mathbf{B}_{2}^{\top}\mathbf{f}$, where the $i$th
entry is the netflow circulating along the $i$th triangle, i.e., the sum of
the edge flows forming the triangle. This can be seen as a rotational
variation measure of the edge flow.

The two incidence matrices and their adjoints provide insights into the three
orthogonal subspaces and signal components given by the Hodge decomposition.

  1. i)

If edge flow $\mathbf{f}$ has zero divergence at each vertex, i.e.,
$\mathbf{B}_{1}\mathbf{f}=\mathbf{0}\Leftrightarrow\mathbf{f}\in\text{ker}(\mathbf{B}_{1})$,
then it is cyclic or _divergence-free_. The space $\text{ker}(\mathbf{B}_{1})$
is called the _cycle space_ , orthogonal to the gradient space, i.e.,
$\mathbb{R}^{N_{1}}=\text{im}(\mathbf{B}_{1}^{\top})\oplus\text{ker}(\mathbf{B}_{1})$.
A gradient flow always has nonzero divergence, while a curl flow is
divergence-free due to (1).

  2. ii)

If edge flow $\mathbf{f}$ has zero curl on each triangle, it is _curl-free_
and $\mathbf{f}\in\text{ker}(\mathbf{B}_{2}^{\top})$. The curl space
$\text{im}(\mathbf{B}_{2})$ is orthogonal to the space
$\text{ker}(\mathbf{B}_{2}^{\top})$ and we have
$\mathbb{R}^{N_{1}}=\text{im}(\mathbf{B}_{2})\oplus\text{ker}(\mathbf{B}_{2}^{\top})$.
A gradient flow $\mathbf{f}_{\rm{G}}$ is curl-free due to (1).

  3. iii)

The space $\text{ker}(\mathbf{L}_{1})$ is called the harmonic space. Any flow
$\mathbf{f}_{\rm{H}}\in\text{ker}(\mathbf{L}_{1})$ satisfies
$\mathbf{L}_{1}\mathbf{f}_{\rm{H}}=\mathbf{0}$, which is harmonic, i.e., both
divergence- and curl-free.

(a) $\mathbf{f}$ (b) $\mathbf{f}_{\rm{G}}$ (c) $\mathbf{f}_{\rm{C}}$ (d)
$\mathbf{f}_{\rm{H}}$

Figure 4: Flow decomposition. (a): A synthetic edge flow $\mathbf{f}$. (b):
Gradient component $\mathbf{f}_{\rm{G}}$ has a nonzero netflow at each node,
but a zero netflow circulating each triangle, i.e., curl-free. (c): Curl
component $\mathbf{f}_{\rm{C}}$ has a zero netflow at each node, i.e.,
divergence-free, but a nonzero curl on each triangle. (d): Harmonic component
$\mathbf{f}_{\rm{H}}$ has a zero netflow at each node and a zero circulating
flow along each triangle, i.e., divergence- and curl-free. The decomposition
is detailed in Section VI-A.

The decomposition of an edge flow into its three components reveals different
properties of the flow, as shown in Fig. 4. For instance, we can study the
effect of an external source or sink by extracting the gradient component of
the edge flow [18]. In Section VI-A, we will discuss this subcomponent
extraction problem and solve it with simplicial filters.

###  IV-B Simplicial Fourier Transform

The Hodge Laplacians are positive semidefinite matrices and admit an
eigendecomposition

$\mathbf{L}_{k}=\mathbf{U}_{k}\mathbf{\Lambda}_{k}\mathbf{U}_{k}^{\top},$ (13)

where the orthonormal matrix
$\mathbf{U}_{k}=[\mathbf{u}_{k,1},\dots,\mathbf{u}_{k,N_{k}}]$ collects the
eigenvectors, and the diagonal matrix
$\mathbf{\Lambda}_{k}=\text{diag}(\lambda_{k,1},\dots,\lambda_{k,N_{k}})$ the
associated eigenvalues. There exists a correspondence between $\mathbf{U}_{1}$
and the three orthogonal subspaces given by the Hodge decomposition (12),
detailed in the following proposition.

###### Proposition 4

Given the $1$-Hodge Laplacian of an SC
$\mathbf{L}_{1}=\mathbf{L}_{1,\ell}+\mathbf{L}_{1,\rm{u}}$, the following
holds.

  1. 1.

Gradient eigenvectors
$\mathbf{U}_{\rm{G}}=[\mathbf{u}_{\rm{G},1},\dots,\mathbf{u}_{{\rm{G}},N_{\rm{G}}}]\in\mathbb{R}^{N_{1}\times
N_{\rm{G}}}$ of $\mathbf{L}_{1,\ell}$ associated with nonzero eigenvalues span
the gradient space $\text{im}(\mathbf{B}_{1}^{\top})$ with dimension
$N_{\rm{G}}$, i.e.,
$\text{im}(\mathbf{B}_{1}^{\top})=\text{im}(\mathbf{U}_{\rm{G}})$.

  2. 2.

Curl eigenvectors
$\mathbf{U}_{\rm{C}}=[\mathbf{u}_{\rm{C},1},\dots,\mathbf{u}_{{\rm{C}},N_{\rm{C}}}]\in\mathbb{R}^{N_{1}\times
N_{\rm{C}}}$ of $\mathbf{L}_{1,\rm{u}}$ associated with nonzero eigenvalues
span the curl space $\text{im}(\mathbf{B}_{2})$ with dimension $N_{\rm{C}}$,
i.e., $\text{im}(\mathbf{B}_{2})=\text{im}(\mathbf{U}_{\rm{C}})$.

  3. 3.

Gradient eigenvectors $\mathbf{U}_{\rm{G}}$ are orthogonal to curl ones
$\mathbf{U}_{\rm{C}}$. Matrix $[\mathbf{U}_{\rm{G}}\,\,\mathbf{U}_{\rm{C}}]$
forms the eigenvectors of $\mathbf{L}_{1}$ associated with nonzero
eigenvalues, which span the space $\text{im}(\mathbf{L}_{1})$ with dimension
$N_{\rm{G}}+N_{\rm{C}}$.

  4. 4.

Harmonic eigenvectors
$\mathbf{U}_{\rm{H}}=[\mathbf{u}_{{\rm{H}},1},\dots,\mathbf{u}_{{\rm{H}},N_{\rm{H}}}]\in\mathbb{R}^{N_{1}\times
N_{\rm{H}}}$ of $\mathbf{L}_{1}$ associated with zero eigenvalues span the
harmonic space $\text{ker}(\mathbf{L}_{1})$ with dimension $N_{\rm{H}}$, i.e.,
$\text{ker}(\mathbf{L}_{1})=\text{im}(\mathbf{U}_{\rm{H}})$. Matrices
$[\mathbf{U}_{\rm{H}}\,\,\mathbf{U}_{\rm{C}}]$ and
$[\mathbf{U}_{\rm{H}}\,\,\mathbf{U}_{\rm{G}}]$ provide the eigenvectors of
$\mathbf{L}_{1,\ell}$ and $\mathbf{L}_{1,\rm{u}}$ associated with zero
eigenvalues, respectively.

  5. 5.

The columns of $\mathbf{U}_{1}$ can be ordered such that
$\mathbf{U}_{1}=[\mathbf{U}_{\rm{H}}\,\,\mathbf{U}_{\rm{G}}\,\,\mathbf{U}_{\rm{C}}]$.
Matrix $\mathbf{U}_{1}$ forms an eigenvector basis for $\mathbf{L}_{1}$,
$\mathbf{L}_{1,\ell}$ and $\mathbf{L}_{1,\rm{u}}$, and
$N_{1}=N_{\rm{H}}+N_{\rm{G}}+N_{\rm{C}}$.

###### Proof:

See Appendix D in supplementary materials. ∎

Proposition 4 shows that:  i) the eigenvectors in $\mathbf{U}_{1}$ can fully
span the three orthogonal subspaces given by the Hodge decomposition;  ii) the
Hodge Laplacian $\mathbf{L}_{1}$ and its lower and upper counterparts,
$\mathbf{L}_{1,\ell}$ and $\mathbf{L}_{1,\rm{u}}$, can be simultaneously
diagonalized by $\mathbf{U}_{1}$; and,  iii) from
$\text{im}(\mathbf{B}_{1}^{\top})=\text{im}(\mathbf{L}_{1,\ell})$, we have
that the image of the lower Hodge Laplacian $\mathbf{L}_{1,\ell}$ coincides
with the gradient space, and from
$\text{im}(\mathbf{B}_{2})=\text{im}(\mathbf{L}_{1,\rm{u}})$, the image of
$\mathbf{L}_{1\rm{u}}$ coincides with the curl space.  These results are
applicable to the $k$-Hodge Laplacian accordingly. See [18, Prop. 1] and [19,
Thm. 1] for related discussions.

Thus, the lower shifting of a curl or harmonic flow leads to zero as the
harmonic and curl space correspond to the null space of $\mathbf{L}_{1,\ell}$.
Likewise, the upper shifting of a gradient or harmonic flow leads to zero,
i.e.,

$\mathbf{L}_{1,\ell}\mathbf{f}_{\rm{C}}=\mathbf{0},\,\,\mathbf{L}_{1,\rm{u}}\mathbf{f}_{\rm{G}}=\mathbf{0},\,\,\mathbf{L}_{1,\ell}\mathbf{f}_{\rm{H}}=\mathbf{L}_{1,\rm{u}}\mathbf{f}_{\rm{H}}=\mathbf{0}.$
(14)

Given a $k$-simplicial signal $\mathbf{s}^{k}$, the _simplicial Fourier
transform (SFT)_ is given by its projection onto the eigenvectors
$\mathbf{U}_{k}$, i.e.,
$\tilde{\mathbf{s}}^{k}\triangleq\mathbf{U}^{\top}_{k}\mathbf{s}^{k}$. Entry
$[\mathbf{s}^{k}]_{i}$ represents the weight eigenvector $\mathbf{u}_{k,i}$
has on expressing $\mathbf{s}^{k}$. The inverse SFT is given by
$\mathbf{s}^{k}=\mathbf{U}_{k}\tilde{\mathbf{s}}^{k}$. For $k=0$, the SFT
coincides with the GFT [18]. As for the GFT, the eigenvalues of
$\mathbf{L}_{k}$ carry the notion of simplicial frequencies. But in the
simplex domain, this frequency notion is more involved. As we illustrate in
the sequel for $k=1$, the eigenvalues in the set
$\mathcal{Q}=\\{\lambda_{1,1},\dots,\lambda_{1,N_{1}}\\}$ of $\mathbf{L}_{1}$
measure three types of simplicial frequencies.

Gradient frequency. For any unit norm gradient eigenvector
$\mathbf{u}_{\rm{G}}\in\mathbf{U}_{\rm{G}}$, associated to the gradient space
$\text{im}(\mathbf{B}_{1}^{\top})$, its corresponding eigenvalue follows

$\lambda_{\rm{G}}=\mathbf{u}_{\rm{G}}^{\top}\mathbf{L}_{1}\mathbf{u}_{\rm{G}}=\lVert\mathbf{B}_{1}\mathbf{u}_{\rm{G}}\lVert_{2}^{2}+\lVert\mathbf{B}_{2}^{\top}\mathbf{u}_{\rm{G}}\lVert_{2}^{2}=\lVert\mathbf{B}_{1}\mathbf{u}_{\rm{G}}\lVert_{2}^{2},$
(15)

where the last equality is due to the fact that $\mathbf{u}_{\rm{G}}$ is curl-
free, i.e., $\mathbf{B}_{2}^{\top}\mathbf{u}_{\rm{G}}=\mathbf{0}$. Thus,
eigenvalue $\lambda_{\rm{G}}$ is the squared $\ell_{2}$-norm of the divergence
$\mathbf{B}_{1}\mathbf{u}_{\rm{G}}$ of the eigenvector edge flow
$\mathbf{u}_{\rm{G}}$. The magnitude of $\lambda_{\rm{G}}$ measures the extent
of total divergence, i.e., the nodal variation. The gradient eigenvectors
associated with a large eigenvalue have a large total divergence. If the SFT
$\tilde{\mathbf{f}}=\mathbf{U}_{1}^{\top}\mathbf{f}$ of an edge flow has a
large weight on such an eigenvector, we say that it contains a high gradient
frequency, corresponding to its large divergence. We call any eigenvalue
$\lambda_{\rm{G}}$ associated to the gradient eigenvectors
$\mathbf{U}_{\rm{G}}$ a _gradient frequency_ and collect them in the set
$\mathcal{Q}_{\rm
G}=\\{\lambda_{\rm{G},1},\dots,\lambda_{{\rm{G}},N_{\rm{G}}}\\}$.

Curl frequency. For any unit norm curl eigenvector
$\mathbf{u}_{\rm{C}}\in\mathbf{U}_{\rm{C}}$ associated to the curl space
$\text{im}(\mathbf{B}_{2})$, its corresponding eigenvalue follows

$\lambda_{\rm{C}}=\mathbf{u}_{\rm{C}}^{\top}\mathbf{L}_{1}\mathbf{u}_{\rm{C}}=\lVert\mathbf{B}_{1}\mathbf{u}_{\rm{C}}\lVert_{2}^{2}+\lVert\mathbf{B}_{2}^{\top}\mathbf{u}_{\rm{C}}\lVert_{2}^{2}=\lVert\mathbf{B}_{2}^{\top}\mathbf{u}_{\rm{C}}\lVert_{2}^{2},$
(16)

where the last equality is due to the fact that $\mathbf{u}_{\rm{C}}$ is
divergence-free, i.e., $\mathbf{B}_{1}\mathbf{u}_{\rm{C}}=\mathbf{0}$.
Eigenvalue $\lambda_{\rm{C}}$ is the squared $\ell_{2}$-norm of the curl
$\mathbf{B}_{2}^{\top}\mathbf{u}_{\rm{C}}$ of the eigenvector
$\mathbf{u}_{\rm{C}}$. Thus, the magnitude of $\lambda_{\rm{C}}$ measures the
extent of total curl, i.e., the rotational variation. Any eigenvector in the
curl space corresponding to a large eigenvalue has a large total curl. If the
SFT of an edge flow contains large weights on such eigenvectors, we say that
it has a high curl frequency. We name any eigenvalue $\lambda_{\rm{C}}$
associated to the curl eigenvectors $\mathbf{U}_{\rm{C}}$ a _curl frequency_
and collect them in the set $\mathcal{Q}_{\rm
C}=\\{\lambda_{\rm{C},1},\dots,\lambda_{{\rm{C}},N_{\rm{C}}}\\}$.

Harmonic frequency. The remaining eigenvalues $\lambda_{\rm{H}}$ are
associated to the eigenvectors $\mathbf{u}_{\rm{H}}\in\mathbf{U}_{\rm{H}}$
which span the harmonic space $\text{ker}(\mathbf{L}_{1})$. They can be
expressed as

$\lambda_{\rm{H}}=\mathbf{u}_{\rm{H}}^{\top}\mathbf{L}_{1}\mathbf{u}_{\rm{H}}=\lVert\mathbf{B}_{1}\mathbf{u}_{\rm{H}}\lVert_{2}^{2}+\lVert\mathbf{B}_{2}^{\top}\mathbf{u}_{\rm{H}}\lVert_{2}^{2}=0,$
(17)

because $\mathbf{u}_{\rm{H}}$ is harmonic, i.e., both divergence- and curl-
free. If the SFT of an edge flow has only nonzeros at the harmonic frequencies
(which are all zeros), then it is a harmonic flow. We collect the harmonic
frequencies (all zeros) in the set $\mathcal{Q}_{\rm
H}=\\{\lambda_{\rm{H},1},\dots,\lambda_{{\rm{H}},N_{\rm{H}}}\\}$.

With these three types of simplicial frequencies, low and high frequency
notions in an SC are only meaningful w.r.t. a certain type, as they are all
nonnegative and can be ordered. A higher gradient or curl frequency indicates
respectively a larger nodal or rotational variability. This is different from
the frequency notion in discrete and graph signal processing. A zero
simplicial frequency does not correspond to a constant edge flow but a
globally conservative flow, i.e., divergence- and curl-free. Fig. 5 shows
examples of different eigenvectors and the associated eigenvalues, which would
be the analogous of the complex exponentials in discrete-time signal
processing for the edge space in Fig. 1a.

Simplicial embeddings. From Proposition 4 and three types of simplicial
frequencies, we can interpret the SFT by the following diagonalization of
$\mathbf{L}_{1}$

$\mathbf{L}_{1}=\mathbf{U}_{1}\text{blkdiag}\big{(}\mathbf{\Lambda}_{\rm{H}},\mathbf{\Lambda}_{\rm{G}},\mathbf{\Lambda}_{\rm{C}}\big{)}\mathbf{U}_{1}^{\top}$
(18)

with
$\mathbf{U}_{1}=\big{[}\mathbf{U}_{\rm{H}}\,\,\mathbf{U}_{\rm{G}}\,\,\mathbf{U}_{\rm{C}}\big{]}$
and $\text{blkdiag}(\mathbf{A},\mathbf{B},\mathbf{C})$ a block-diagonal matrix
containing the square matrices $\mathbf{A},\mathbf{B},\mathbf{C}$ as diagonal
blocks. Similarly, we have

$\mathbf{L}_{1,\ell}=\mathbf{U}_{1}\text{blkdiag}\big{(}\mathbf{0},\mathbf{\Lambda}_{\rm{G}},\mathbf{0}\big{)}\mathbf{U}_{1}^{\top}$
(19)

for the lower Laplacian $\mathbf{L}_{1,\ell}$, and likewise for
$\mathbf{L}_{1,\rm{u}}$, we have

$\mathbf{L}_{1,\rm{u}}=\mathbf{U}_{1}\text{blkdiag}\big{(}\mathbf{0},\mathbf{0},\mathbf{\Lambda}_{\rm{C}}\big{)}\mathbf{U}_{1}^{\top}$
(20)

where $\mathbf{0}$ is an all-zero matrix of appropriate dimensions. Such
insightful eigendecompositions enable us to define the following three
embeddings of an edge flow $\mathbf{f}\in\mathbb{R}^{N_{1}}$,

$\begin{cases}\tilde{\mathbf{f}}_{\rm{H}}=\mathbf{U}_{\rm{H}}^{\top}\mathbf{f}=\mathbf{U}_{\rm{H}}^{\top}\mathbf{f}_{\rm{H}}\in\mathbb{R}^{N_{\rm{H}}},&\emph{harmonic
embedding}\\\
\tilde{\mathbf{f}}_{\rm{G}}=\mathbf{U}_{\rm{G}}^{\top}\mathbf{f}=\mathbf{U}_{\rm{G}}^{\top}\mathbf{f}_{\rm{G}}\in\mathbb{R}^{N_{\rm{G}}},&\emph{gradient
embedding}\\\
\tilde{\mathbf{f}}_{\rm{C}}=\mathbf{U}_{\rm{C}}^{\top}\mathbf{f}=\mathbf{U}_{\rm{C}}^{\top}\mathbf{f}_{\rm{C}}\in\mathbb{R}^{N_{\rm{C}}},&\emph{curl
embedding}.\\\ \end{cases}$ (21)

They follow from the orthogonality of the three components given by the Hodge
decomposition. Equivalently, we can write the SFT of $\mathbf{f}$ as
$\tilde{\mathbf{f}}=[\tilde{\mathbf{f}}_{\rm{H}}^{\top},\tilde{\mathbf{f}}_{\rm{G}}^{\top},\tilde{\mathbf{f}}_{\rm{C}}^{\top}]^{\top}$.
Each entry of an embedding represents the weight the flow has on the
corresponding eigenvector (simplicial Fourier basis vector), e.g., entry
$[\tilde{\mathbf{f}}_{\rm{G}}]_{i}$ is the SFT of $\mathbf{f}$ at the $i$th
gradient frequency $\lambda_{{\rm{G}},i}$. Such an embedding provides a
compressed representation of the edge flow if they present a degree of
sparsity and also allows us to differentiate different types of edge flow,
e.g., to cluster trajectories and analyze ocean drift data [31, 32].

(a) $\lambda_{{\rm{G}},1}=0.81$ (b) $\lambda_{{\rm{G}},3}=3.31$ (c)
$\lambda_{{\rm{G}},6}=5.49$ (d) $\lambda_{{\rm{C}},1}=2$ (e)
$\lambda_{{\rm{C}},3}=4$ (f) $\lambda_{{\rm{H}},1}=0$

Figure 5: Spectral analysis of the edge space in Fig. 1a. The flow value is
indicated by the edge width and annotated next to the edge. It is zero if the
edge is not annotated. If a flow orientation is opposite to the reference
orientation, the corresponding flow value is negative. (a)-(c): The 1st, 3rd,
and 6th eigenvectors in the gradient space $\mathbf{U}_{\rm{G}}$ with the
corresponding gradient frequencies $\lambda_{\rm{G}}$. The eigenvector total
divergence increases with the eigenvalue. (d)-(e): The 1st and 3rd
eigenvectors in the curl space $\mathbf{U}_{\rm{C}}$ with the corresponding
curl frequencies $\lambda_{\rm{C}}$. The eigenvector total curl increases with
the eigenvalue. (f): The only eigenvector in the harmonic space
$\mathbf{U}_{\rm{H}}$ with frequency 0, which has zero divergence and curl.

###  IV-C Filter Frequency Response

Upon defining the SFT, we can analyze the frequency response of the simplicial
convolutional filter (3). From the diagonalizations (19) and (21), we see that
the lower simplicial shifting of an edge flow affects only the gradient
component and the upper shifting affects only the curl component, i.e.,

$\mathbf{L}_{1,\ell}\mathbf{f}=\mathbf{U}_{\rm G}\mathbf{\Lambda}_{\rm
G}\tilde{\mathbf{f}}_{\rm G},\ \mathbf{L}_{1,\rm{u}}\mathbf{f}=\mathbf{U}_{\rm
C}\mathbf{\Lambda}_{\rm C}\tilde{\mathbf{f}}_{\rm C}.$ (22)

Through diagonalizing $\mathbf{H}_{1}$ by
$\mathbf{U}_{1}=\big{[}\mathbf{U}_{\rm{H}}\,\,\mathbf{U}_{\rm{G}}\,\,\mathbf{U}_{\rm{C}}\big{]}$,
we can find the frequency response of $\mathbf{H}_{1}$ as

$\tilde{\mathbf{H}}_{1}=\mathbf{U}_{1}^{\top}\mathbf{H}_{1}\mathbf{U}_{1}=\text{blkdiag}\big{(}\tilde{\mathbf{H}}_{\rm
H},\tilde{\mathbf{H}}_{\rm G},\tilde{\mathbf{H}}_{\rm C}\big{)},$ (23)

where $\tilde{\mathbf{H}}_{\rm H}=h_{0}\mathbf{I}$, $\tilde{\mathbf{H}}_{\rm
G}=h_{0}\mathbf{I}+\sum_{l_{1}=1}^{L_{1}}\alpha_{l_{1}}\mathbf{\Lambda}_{\rm{G}}^{l_{1}}$
and $\tilde{\mathbf{H}}_{\rm
C}=h_{0}\mathbf{I}+\sum_{l_{2}=1}^{L_{2}}\beta_{l_{2}}\mathbf{\Lambda}_{\rm{C}}^{l_{2}}$.
At an arbitrary frequency $\lambda$, the frequency response
$\tilde{H}_{1}(\lambda)$ is given by

$\begin{cases}\tilde{H}_{\rm H}(\lambda):=h_{0},&\text{ for
}\lambda\in\mathcal{Q}_{\rm{H}},\\\ \tilde{H}_{\rm
G}(\lambda):=h_{0}+\sum_{l_{1}=1}^{L_{1}}\alpha_{l_{1}}\lambda^{l_{1}},&\text{
for }\lambda\in\mathcal{Q}_{\rm{G}},\\\ \tilde{H}_{\rm
C}(\lambda):=h_{0}+\sum_{l_{2}=1}^{L_{2}}\beta_{l_{2}}\lambda^{l_{2}},&\text{
for }\lambda\in\mathcal{Q}_{\rm{C}},\\\ \end{cases}$ (24)

which is the filter frequency response at the harmonic, gradient and curl
frequencies, respectively. From (24), we make the following three
observations.

  1. 1.

Filter $\mathbf{H}_{1}$ controls the different frequency types independently.
The coefficient $h_{0}$ determines the harmonic frequency response and
contributes to the whole spectrum. The coefficients $\boldsymbol{\alpha}$ and
$\boldsymbol{\beta}$ contribute only to the gradient and curl frequency
response, respectively. This independent control on different signal subspaces
corresponds to the different parameters imposed on the lower and upper
adjacencies in the simplicial domain. In constrast, for $L_{1}=L_{2}$ and
$\boldsymbol{\alpha}=\boldsymbol{\beta}$, the filter cannot regulate the
gradient and curl spaces independently and has less flexibility.

  2. 2.

The gradient frequency response is fully determined by the matrix polynomial
in $\mathbf{L}_{1,\ell}$ [cf. (19) and (23)]. Thus, if $L_{2}=0$,
$\mathbf{H}_{1}$ has as response $h_{0}$ for
$\lambda\in\mathcal{Q}_{\rm{H}}\cup\mathcal{Q}_{\rm{C}}$, and
$h_{0}+\sum_{l_{1}=1}^{L_{1}}\alpha_{l_{1}}\lambda^{l_{1}},\text{ for
}\lambda\in\mathcal{Q}_{\rm{G}}$. This controls the gradient and non-gradient
frequencies with a reduced design burden due to fewer parameters. But we give
up the control on the curl frequencies. Likewise for the case of $L_{1}=0$,
which is beneficial when only curl components need to be tuned.

  3. 3.

The simplicial filter responds differently to an _overlapping frequency_ ,
i.e., an eigenvalue $\lambda\in\\{\mathcal{Q}_{\rm G}\cap\mathcal{Q}_{\rm
C}\\}$ with a multiplicity larger than one, associated to both the gradient
and the curl space. This is critical, e.g., when extracting the gradient
component. However, if $L_{1}=L_{2}$ and
$\boldsymbol{\alpha}=\boldsymbol{\beta}$, the filter responds the same at the
overlapping frequencies, and the unwanted component (curl component at the
overlapping frequency) will be partially preserved.

##  V Filter Design

Given a training set of input-output edge flow relations
$\mathcal{T}=\\{(\mathbf{f}_{1},\mathbf{f}_{\rm{o},1}),\dots,(\mathbf{f}_{|\mathcal{T}|},\mathbf{f}_{{\rm{o}},|\mathcal{T}|})\\}$,
we can learn the filter coefficients in a data-driven fashion by fitting the
filtered output $\mathbf{H}_{1}\mathbf{f}$ to the output
$\mathbf{f}_{\rm{o}}$. Specifically, consider a mean squared error (MSE) cost
function and a regularizer $r(h_{0},\boldsymbol{\alpha},\boldsymbol{\beta})$
to avoid overfitting, we formulate the problem as

$\underset{h_{0},\boldsymbol{\alpha},\boldsymbol{\beta}}{\text{min}}\frac{1}{|\mathcal{T}|}\sum_{(\mathbf{f}_{i},\mathbf{f}_{{\rm{o}},i})\in\mathcal{T}}\lVert\mathbf{H}_{1}\mathbf{f}_{i}-\mathbf{f}_{{\rm{o}},i}\lVert^{2}_{2}+\gamma
r(h_{0},\boldsymbol{\alpha},\boldsymbol{\beta}),$ (25)

with $\gamma>0$. A flow prediction based on (25) is detailed in [1].

In this section, we focus in detail on designing the simplicial filter given a
filter frequency response. Specifically, we assume a desired frequency
response $g_{0}$ at the harmonic frequency $\lambda=0$, a gradient frequency
response $g_{\rm{G}}(\lambda)$ for $\lambda\in\mathcal{Q}_{\rm{G}}$, and a
curl frequency response $g_{\rm{C}}(\lambda)$ for
$\lambda\in\mathcal{Q}_{\rm{C}}$. To design the coefficients
$h_{0},\boldsymbol{\alpha},\boldsymbol{\beta}$, our goal is then to
approximate the desired response by the filter frequency response
$\tilde{H}_{1}(\lambda)$ [cf. (24)], which can be formulated as

$\begin{cases}h_{0}\approx g_{0},&\text{ for }\lambda_{i}=0,\\\
h_{0}+\sum_{l_{1}=1}^{L_{1}}\alpha_{l_{1}}\lambda_{i}^{l_{1}}\approx
g_{\rm{G}}(\lambda_{i}),&\text{ for }\lambda_{i}\in\mathcal{Q}_{\rm{G}},\\\
h_{0}+\sum_{l_{2}=1}^{L_{2}}\beta_{l_{2}}\lambda_{i}^{l_{2}}\approx
g_{\rm{C}}(\lambda_{i}),&\text{ for
}\lambda_{i}\in\mathcal{Q}_{\rm{C}}.\end{cases}$ (26)

In the following, we first use a standard least-squares (LS) approach to solve
(26). Later, we consider a universal design so to avoid the eigenvalue
computation when a continuous desired frequency response is given. In
particular, we consider a grid-based and a Chebyshev polynomial approach.

###  V-A Least-Squares Filter Design

Denote the number of distinct gradient frequencies in $\mathcal{Q}_{\rm{G}}$
by $D_{\rm{G}}$, and that of distinct curl frequencies in
$\mathcal{Q}_{\rm{C}}$ by $D_{\rm{C}}$. Then, the three sets of equations in
(26) contain respectively one, $D_{\rm{G}}$ and $D_{\rm{C}}$ distinct linear
equations. Let $\mathbf{g}=[g_{0},\mathbf{g}_{\rm G}^{\top},\mathbf{g}_{\rm
C}^{\top}]^{\top}$ collect the desired responses at distinct frequencies where
$[\mathbf{g}_{\rm{G}}]_{i}=g_{\rm{G}}(\lambda_{{\rm{G}},i})$, for
$i=1\dots,D_{\rm{G}}$, is the response at the $i$th distinct gradient
frequency $\lambda_{{\rm{G}},i}$, and
$[\mathbf{g}_{\rm{C}}]_{i}=g_{\rm{C}}(\lambda_{{\rm{C}},i})$, for
$i=1\dots,D_{\rm{C}}$, at the $i$th distinct curl frequency. Then, we can
obtain the filter coefficients by solving the LS problem

$\underset{h_{0},\boldsymbol{\alpha},\boldsymbol{\beta}}{\text{min}}\left\|\begin{bmatrix}{\bf
1}\ \vline&\begin{matrix}{\bf 0}\\\
\hline\cr\begin{matrix}\mathbf{\Phi}_{\rm{G}}&{\bf 0}\\\ {\bf
0}&\mathbf{\Phi}_{\rm{C}}\end{matrix}\end{matrix}\end{bmatrix}\begin{bmatrix}h_{0}\\\
\boldsymbol{\alpha}\\\
\boldsymbol{\beta}\end{bmatrix}-\mathbf{g}\right\|^{2}_{2},$ (27)

where $\bf 1$ ($\bf 0$) is an all-one (all-zero) matrix or vector of an
appropriate dimension, $\mathbf{\Phi}_{\rm{G}}\in\mathbb{R}^{D_{\rm{G}}\times
L_{1}}$ and $\mathbf{\Phi}_{\rm{C}}\in\mathbb{R}^{D_{\rm{C}}\times L_{2}}$ are
Vandermonde matrices with respective entries
$[\mathbf{\Phi}_{\rm{G}}]_{ij}=\lambda_{{\rm{G}},i}^{j}$ and
$[\mathbf{\Phi}_{\rm{C}}]_{ij}=\lambda_{{\rm{C}},i}^{j}$. From the Cayley-
Hamilton theorem [33] and [4, Thm. 3], we have that any analytical function of
a matrix can be expressed as a matrix polynomial of degree less than its
minimal polynomial degree, which equals the number of distinct eigenvalues for
a positive semi-definite matrix. Thus, we can assume the filter orders
$L_{1}\leq D_{\rm G}$ and $L_{2}\leq D_{\rm C}$. Under this condition, problem
(27) admits a unique solution which can be obtained as the Moore-Penrose
inverse of the system matrix. Furthermore, when $L_{1}=D_{\rm{G}}$ and
$L_{2}=D_{\rm{C}}$, $\mathbf{\Phi}_{\rm{G}}$ and $\mathbf{\Phi}_{\rm{C}}$ are
square and any two rows in them are linearly independent, the solution leads
to a zero cost in (27). We refer to the design via problem (27) as the _joint
design_.

In addition, given a desired edge operator $\mathbf{G}$, the following
proposition states that it can be implemented by filter $\mathbf{H}_{1}$.

###### Proposition 5

A desired linear operator $\mathbf{G}\in\mathbb{R}^{N_{1}\times N_{1}}$ can be
perfectly implemented by a simplicial filter $\mathbf{H}_{1}$ if the following
three conditions hold true:

  1. i)

Matrices $\mathbf{G}$ and $\mathbf{L}_{1}$ are simultaneously diagonalizable,
i.e., $\mathbf{U}_{1}$ forms an eigenvector basis for $\mathbf{G}$. Let
$\mathbf{g}=[\mathbf{g}_{\rm{H}}^{\top},\mathbf{g}_{\rm{G}}^{\top},\mathbf{g}_{\rm{C}}^{\top}]^{\top}$
collect the eigenvalues of $\mathbf{G}$.

  2. ii)

If two eigenvalues of $\mathbf{L}_{1}$ are of the same frequency type and
equal, the corresponding eigenvalues of $\mathbf{G}$ are also equal. For
$\lambda_{{\rm{H}},i}=\lambda_{{\rm{H}},j}=0\in\mathcal{Q}_{\rm{H}}$, it holds
that $[\mathbf{g}_{\rm{H}}]_{i}=[\mathbf{g}_{\rm{H}}]_{j}$, for
$\lambda_{{\rm{G}},i}=\lambda_{{\rm{G}},j}\in\mathcal{Q}_{\rm G}$,
$[\mathbf{g}_{\rm{G}}]_{i}=[\mathbf{g}_{\rm{G}}]_{j}$, and for
$\lambda_{{\rm{C}},i}=\lambda_{{\rm{C}},j}\in\mathcal{Q}_{\rm C}$,
$[\mathbf{g}_{\rm{C}}]_{i}=[\mathbf{g}_{\rm{C}}]_{j}$.

  3. iii)

The filter orders of $\mathbf{H}_{1}$ follow that $L_{1}\geq D_{\rm{G}}$,
$L_{2}\geq D_{\rm{C}}$.

###### Proof:

See Appendix. E in supplementary materials. ∎

Decoupled design. We can reduce the computational complexity of solving (27)
by considering a decoupled design for different frequency types. First, let us
rewrite problem (27) as

$\displaystyle\underset{h_{0},\boldsymbol{\alpha},\boldsymbol{\beta}}{\text{min}}$
$\displaystyle\left\|\big{[}\mathbf{1}\,\,\mathbf{\Phi}_{\rm{G}}\big{]}\begin{bmatrix}h_{0}\\\
\boldsymbol{\alpha}\end{bmatrix}-\mathbf{g}_{\rm{G}}\right\|^{2}_{2}+\left\|\big{[}\mathbf{1}\,\,\mathbf{\Phi}_{\rm{C}}\big{]}\begin{bmatrix}h_{0}\\\
\boldsymbol{\beta}\end{bmatrix}-\mathbf{g}_{\rm{C}}\right\|^{2}_{2}$ (28)
$\displaystyle+\left\|h_{0}-g_{0}\right\|^{2}_{2}.$

Then, we ignore in (28) the dependence of the first two terms on coefficient
$h_{0}$ and solve the last term separately to estimate $h_{0}$. We then
substitute the estimate $\hat{h}_{0}$ in the first two terms to obtain
$\hat{\boldsymbol{\alpha}}$ and $\hat{\boldsymbol{\beta}}$. This leads to the
solution

$\hat{h}_{0}=g_{0},\,\hat{\boldsymbol{\alpha}}=\mathbf{\Phi}_{\rm{G}}^{\dagger}(\mathbf{g}_{\rm{G}}-g_{0}\mathbf{1}),\,\hat{\boldsymbol{\beta}}=\mathbf{\Phi}_{\rm{C}}^{\dagger}(\mathbf{g}_{\rm{C}}-g_{0}\mathbf{1}),$
(29)

which is suboptimal w.r.t. to that of (27). The following proposition
discusses this suboptimality.

###### Proposition 6

The solution (29) converges to the joint design solution of (27) as
$\lVert\mathbf{\Phi}_{\rm G}\mathbf{\Phi}_{\rm
G}^{\dagger}-\mathbf{I}\lVert_{F}\rightarrow 0$ and $\lVert\mathbf{\Phi}_{\rm
C}\mathbf{\Phi}_{\rm C}^{\dagger}-\mathbf{I}\lVert_{F}\rightarrow 0$ where
$\lVert\cdot\lVert_{F}$ is the Frobenius norm.

###### Proof:

See Appendix. F in supplementary materials. ∎

Proposition 6 says that as the pseudoinverses of $\mathbf{\Phi}_{\rm G}$ and
$\mathbf{\Phi}_{\rm C}$ get closer to their true inverses, which exist when
$L_{1}=D_{\rm{G}}$ and $L_{2}=D_{\rm{C}}$, the decoupled design converges to
the joint design. It also reduces the computational cost to
$\mathcal{O}(D_{\rm G}^{3}+D_{\rm C}^{3})$ from
$\mathcal{O}((1+D_{\rm{G}}+D_{\rm C})^{3})$ of the joint design. However, both
designs require the eigenvalues of the Hodge Laplacians, which takes in
general a computational complexity of $\mathcal{O}(N_{1}^{3})$ [34]. In the
sequel, we consider a universal design strategy to avoid the eigenvalue
computation, specifically, a grid-based design and a Chebyshev polynomial
implementation [35, 36].

###  V-B Grid-Based Design

The grid-based filter design aims to match the desired frequency response in a
continuous interval where the exact frequencies lie such that the eigenvalue
computation of $\mathbf{L}_{1}$ can be avoided. Given a harmonic frequency
response $g_{0}$, a continuous gradient one $g_{\rm
G}(\lambda),\lambda\in[\lambda_{\rm G,\text{min}},\lambda_{\rm G,\text{max}}]$
and a continuous curl one $g_{\rm C}(\lambda),\lambda\in[\lambda_{\rm
C,\text{min}},\lambda_{\rm C,\text{max}}]$, we want that

$\begin{cases}h_{0}-g_{0}\approx 0\\\
\int_{\lambda_{{\rm{G}},\text{min}}}^{\lambda_{{\rm{G}},\text{max}}}\big{|}h_{0}+\sum_{l_{1}=1}^{L_{1}}\alpha_{l_{1}}\lambda^{l_{1}}-g_{\rm{G}}(\lambda)\big{|}^{2}{\rm{d}}\lambda\approx
0\\\
\int_{\lambda_{{\rm{C}},\text{min}}}^{\lambda_{{\rm{C}},\text{max}}}\big{|}h_{0}+\sum_{l_{2}=1}^{L_{2}}\beta_{l_{2}}\lambda^{l_{2}}-g_{\rm{C}}(\lambda)\big{|}^{2}{\rm{d}}\lambda\approx
0,\\\ \end{cases}$ (30)

which is a continuous version of (26). An example is given in Fig. 6. To solve
(30), we can uniformly grid (sample) $M_{1}$ and $M_{2}$ points from the
intervals $[\lambda_{\rm G,\text{min}},\lambda_{\rm G,\text{max}}]$ and
$[\lambda_{\rm C,\text{min}},\lambda_{\rm C,\text{max}}]$. The problem (30)
can then be formulated as an LS problem of form (27) but with the sampled
frequencies as the entries of the system matrix instead of the true
eigenvalues. Similarly as before, we can follow either the joint [cf. (27)] or
the decoupled [cf. (28)] design to solve it. The largest true eigenvalue can
be approximated by efficient algorithms, e.g., power iteration, [34, 37]. For
the smallest, we can set a small value greater than 0 as the lower bound.

Figure 6: An example of continuous frequency response for the grid-based (top)
and Chebyshev (bottom) filter design, which promotes low gradient frequencies
and the high curl frequencies. The cut-off frequencies are subscripted by
$\tau$. The harmonic frequency is given at frequency 0. For the Chebyshev
polynomial design, we require that the gradient and curl continuous functions
are given starting from frequency 0 and $g_{\rm{G}}(0)=g_{\rm{C}}(0)$.

###  V-C Chebyshev Polynomial Design

Both the LS and the grid-based designs rely on the LS problem (27), which has
a Vandermonde matrix as the system matrix, and suffers from numerical
instability. To tackle this issue, we consider a Chebyshev polynomial filter
design [36, 38]. As illustrated in Fig. 6 (bottom), consider that we are given
a continuous gradient frequency response $g_{\rm
G}(\lambda),\lambda\in[0,\lambda_{\rm G,\text{max}}]$ and a continuous curl
one $g_{\rm C}(\lambda),\lambda\in[0,\lambda_{\rm C,\text{max}}]$. We further
assume that $g_{\rm G}(0)=g_{\rm C}(0)=g_{0}$, i.e., the harmonic frequency
response, which requires a domain extension. See Fig. 6 for an illustration.
We reason this subtle requirement for the Chebyshev polynomial design in the
following.

As the simplicial filter $\mathbf{H}_{1}$ is a sum of matrix polynomials of
$\mathbf{L}_{1,\ell}$ and $\mathbf{L}_{1,\rm u}$, we consider Chebyshev
polynomials of each of them to separately obtain the desired gradient and curl
responses, subsequently reaching the final design by summing these two
polynomials. However, this generates an unwanted influence on one frequency
type due to the identity matrix term appearing in the design for the other
type. We correct this by subtracting $g_{0}\mathbf{I}$ based on the
requirement that $g_{\rm{G}}(0)=g_{\rm{C}}(0)$.

First, we approximate the gradient frequency response via a truncated series
of shifted Chebyshev polynomials
$\mathbf{H}_{\ell}:=\mathbf{H}_{\ell}(\mathbf{L}_{1,\ell})$. Let
$\bar{P}_{l}(\lambda),\lambda\in[-1,1]$ be the $l$th Chebyshev polynomial of
the first kind [39]. We perform the transformation
$P_{l}(\lambda):=\bar{P}_{l}(\frac{\lambda-\omega}{\omega})$ with
$\omega:=\frac{\lambda_{{\rm{G}},\text{max}}}{2}$ to shift the domain to
$[0,\lambda_{{\rm{G}},\text{max}}]$. We can approximate the operator
$g_{\rm{G}}(\mathbf{L}_{1,\ell})$ with a desired response $g_{\rm
G}(\lambda),\lambda\in[0,\lambda_{\rm G,\text{max}}]$ by $\mathbf{H}_{\ell}$
of order $L_{1}$

$\textstyle\mathbf{H}_{\ell}=\frac{1}{2}c_{\ell,0}\mathbf{I}+\sum_{l_{1}=1}^{L_{1}}c_{{\ell},l_{1}}P_{l_{1}}(\mathbf{L}_{1,\ell})$
(31)

where we have $P_{0}(\mathbf{L}_{1,\ell})=\mathbf{I}$,
$P_{1}(\mathbf{L}_{1,\ell})=\frac{2}{\lambda_{\rm{G},\text{max}}}\mathbf{L}_{1,\ell}-\mathbf{I}$
and the $l_{1}$th Chebyshev term

$P_{l_{1}}(\mathbf{L}_{1,\ell})=2P_{1}(\mathbf{L}_{1,\ell})P_{l_{1}-1}(\mathbf{L}_{1,\ell})-P_{l_{1}-2}(\mathbf{L}_{1,\ell}),\text{
for }l_{1}\geq 2,$ (32)

and the Chebyshev coefficients $c_{{\ell},l_{1}}$ can be computed as

$c_{{\ell},l_{1}}=\frac{2}{\pi}\int_{0}^{\pi}\cos(l_{1}\phi)g_{\rm{G}}\big{(}\omega(\cos\phi+1)\big{)}{\rm
d}\phi.$ (33)

The frequency response $\tilde{H}_{\ell}(\lambda)$ of $\mathbf{H}_{\ell}$ can
be found as

$\begin{cases}p_{\ell,0}:=\frac{1}{2}c_{\ell,0}+\sum_{l_{1}=1}^{\lfloor
L_{1}/2\rfloor}(c_{{\ell},2l_{1}}-c_{{\ell},2l_{1}-1}),\text{for
}\lambda\in\mathcal{Q}_{\rm{H}}\cup\mathcal{Q}_{\rm{C}}\\\
\tilde{H}_{{\rm{l,G}}}(\lambda):=\frac{1}{2}c_{\ell,0}+\sum_{l_{1}=1}^{L_{1}}c_{{\ell},l_{1}}P_{l_{1}}(\lambda),\text{for
}\lambda\in\mathcal{Q}_{\rm{G}},\end{cases}$ (34)

with weight $p_{\ell,0}$ on the identity term being the frequency response at
the harmonic and curl frequencies as they are in the null space of
$\mathbf{L}_{1,\ell}$ [cf. (19)]. It holds that $p_{\ell,0}\approx g_{0}$ and
$\tilde{H}_{{\rm{l,G}}}(\lambda_{i})\approx g_{\rm{G}}(\lambda_{i})$ at
$\lambda_{i}\in\mathcal{Q}_{\rm{G}}$ with an appropriate order $L_{1}$.

Second, we follow the same procedure [cf. (31)-(33)] to obtain the Chebyshev
polynomial $\mathbf{H}_{\rm{u}}:=\mathbf{H}_{\rm{u}}(\mathbf{L}_{1,\rm{u}})$
of order $L_{2}$ to approximate the curl frequency response
$g_{\rm{C}}(\lambda)$ with $\lambda\in[0,\lambda_{\rm{C},\text{max}}]$, i.e.,

$\textstyle\mathbf{H}_{\rm{u}}=\frac{1}{2}c_{\rm{u},0}\mathbf{I}+\sum_{l_{2}=1}^{L_{2}}c_{{\rm{u}},l_{2}}P_{l_{2}}(\mathbf{L}_{1,\rm{u}}).$
(35)

Its frequency response $\tilde{H}_{\rm{u}}(\lambda)$ is given by

$\begin{cases}p_{\rm{u},0}:=\frac{1}{2}c_{\rm{u,0}}+\sum_{l_{2}=1}^{\lfloor
L_{2}/2\rfloor}(c_{{\rm{u}},2l_{2}}-c_{{\rm{u}},2l_{2}-1}),\text{for
}\lambda\in\mathcal{Q}_{\rm{H}}\cup\mathcal{Q}_{\rm{G}}\\\
\tilde{H}_{{\rm{u,C}}}(\lambda):=\frac{1}{2}c_{\rm{u},0}+\sum_{l_{2}=1}^{L_{2}}c_{{\rm{u}},l_{2}}P_{l_{2}}(\lambda),\text{for
}\lambda\in\mathcal{Q}_{\rm{C}}.\end{cases}$ (36)

with weight $p_{\rm{u},0}$ on the identity term being the frequency response
at the harmonic and gradient frequencies as they are in the null space of
$\mathbf{L}_{1,\rm{u}}$ [cf. (20)]. It holds that $p_{\rm{u},0}\approx g_{0}$
and $\tilde{H}_{{\rm{u,C}}}(\lambda_{i})\approx g_{\rm{C}}(\lambda_{i})$ at
$\lambda_{i}\in\mathcal{Q}_{\rm{C}}$ with an appropriate order $L_{2}$.

By summing $\mathbf{H}_{\ell}$ and $\mathbf{H}_{\rm{u}}$, we obtain the filter
that approximates the desired gradient and curl frequency responses. However,
from (34), we see that $\mathbf{H}_{\ell}$ generates a response $p_{\ell,0}$
at both harmonic and curl frequencies. This will shift up the curl frequency
response unwantedly by $p_{\ell,0}$. Similarly, $\mathbf{H}_{\rm{u}}$ has the
effect of lifting the gradient frequency response by $p_{\rm{u},0}$. By
assuming that $g_{\rm{G}}(0)=g_{\rm{C}}(0)$, we can remove this influence by
subtracting a term $g_{0}\mathbf{I}$ from the summation. Hence, the final
truncated series of Chebyshev polynomials $\mathbf{H}_{1}$ of orders $L_{1}$
and $L_{2}$ is

$\mathbf{H}_{1}=\mathbf{H}_{\ell}+\mathbf{H}_{\rm{u}}-g_{0}\mathbf{I},$ (37)

with a frequency response $\tilde{H}_{1}(\lambda)$ given by

$\begin{cases}p_{\ell,0}+p_{\rm{u},0}-g_{0},&\text{for
}\lambda\in\mathcal{Q}_{\rm{H}}\\\
\tilde{H}_{{\rm{l,G}}}(\lambda)+p_{\rm{u},0}-g_{0},&\text{for
}\lambda\in\mathcal{Q}_{\rm{G}}\\\
\tilde{H}_{{\rm{u,C}}}(\lambda)+p_{\ell,0}-g_{0},&\text{for
}\lambda\in\mathcal{Q}_{\rm{C}},\end{cases}$ (38)

where $p_{\ell,0}-g_{0}\approx 0$ and $p_{\rm{u},0}-g_{0}\approx 0$ for
appropriate orders. The following proposition states that the approximation
error of the Chebyshev polynomial implementation (37) is bounded.

###### Proposition 7

Let $\mathbf{G}$ be the desired operator corresponding to the continuous
gradient and curl frequency responses $g_{\rm G}(\lambda)$ with
$\lambda\in[0,\lambda_{\rm{G},\text{max}}]$ and $g_{\rm C}(\lambda)$ with
$\lambda\in[0,\lambda_{\rm{C},\text{max}}]$, as well as the harmonic one
$g_{\rm G}(0)=g_{\rm C}(0)=g_{0}$. Let $\mathbf{H}_{1}$ [cf. (37)] be a
truncated series of Chebyshev polynomials of orders $L_{1}$ and $L_{2}$ with
frequency response $\tilde{H}_{1}(\lambda)$ [cf. (38)]. Define

$\displaystyle
B_{1}(L_{1}):=\textstyle\text{sup}_{\lambda\in[0,\lambda_{\rm{G},\text{max}}]}\bigl{\\{}\big{|}\tilde{H}_{{\ell}}(\lambda)-g_{0}-g_{\rm{G}}(\lambda)\big{|}\bigr{\\}},$
(39) $\displaystyle
B_{2}(L_{2}):=\textstyle\text{sup}_{\lambda\in[0,\lambda_{\rm{C},\text{max}}]}\bigl{\\{}\big{|}\tilde{H}_{{\rm{u}}}(\lambda)-g_{0}-g_{\rm{C}}(\lambda)\big{|}\bigr{\\}},$

and $B:=\text{max}\big{\\{}B_{1}(L_{1}),B_{2}(L_{2})\big{\\}}$. Then, we have
that

$\lVert\mathbf{G}-\mathbf{H}_{1}\lVert_{2}:=\underset{\mathbf{f}\neq\mathbf{0}}{\text{max}}\frac{\lVert(\mathbf{G}-\mathbf{H}_{1})\mathbf{f}\lVert_{2}}{\lVert\mathbf{f}\lVert_{2}}\leq
B$ (40)

###### Proof:

See Appendix. G in supplementary materials. ∎

When $g_{\rm{G}}(\cdot)$ and $g_{\rm{C}}(\cdot)$ are real analytic, a stronger
bound can be found [36, 40]. We comment that,  1. for the case of $L_{2}=0$
where only the gradient frequency response $g_{\rm G}(\lambda)$ is of
interest, we can directly consider the Chebyshev polynomial
$\mathbf{H}_{\ell}$ [cf. (31)]. Likewise for the case of $L_{1}=0$.  2. For
the case of $L_{1}=L_{2}$ with $\boldsymbol{\alpha}=\boldsymbol{\beta}$, the
Chebyshev polynomial of $\mathbf{L}_{1}$ can be implemented to approximate a
continuous frequency response $g(\lambda)$ by following [36];  3. The
Chebyshev polynomial design does not require the eigenvalue computation of
$\mathbf{L}_{1}$. It also does not suffer from numerical instability, allows
to build simplicial filters of a large order for a more accurate approximation
and admits a recursive and distributed implementation due to (32).

##  VI Applications

In this section, we first use the simplicial filter for subcomponent
extraction and edge flow denoising. Then, we apply it to a financial market
and a street and traffic network [17, 18, 8, 41, 42]. We focus on processing
edge flows and evaluate the performance via the normalized root mean square
error (NRMSE),
$e=\lVert\hat{\mathbf{f}}-\mathbf{f}_{0}\lVert_{2}/\lVert\mathbf{f}_{0}\lVert_{2}$,
where $\hat{\mathbf{f}}$ is the flow estimate and $\mathbf{f}_{0}$ is the
groundtruth flow. For the Chebyshev polynomial design, we use the Chebfun
toolbox [43].

Figure 7: Subcomponent extraction performance by simplicial filters
$\mathbf{H}_{1}$ with different parameters. The extraction becomes better as
the filter order increases. For the gradient and curl components, the filter
with $L_{1}=L_{2}$ performs poorer than others because of its limited
expressive power. For the general setting, the joint and decoupled designs
have a smaller performance difference as the filter order grows, as stated in
Proposition 6.

###  VI-A Subcomponent Extraction

The three subcomponents given by the Hodge decomposition reveal different
properties of the edge flow. In pairwise ranking problems, we want to rank the
alternatives by comparing their scores. The work in [8] modeled the score
differences between alternatives as edge flows on a pairwise comparison graph.
Then, the gradient component gives a global ranking of the alternatives and
the curl one measures the validity of the ranking. See some other examples in
[9, 10, 11]. A common approach is to use the LS projection operators to obtain
the three components as follows [15, 8, 18]

$\hat{\mathbf{f}}_{\rm{G}}=\mathbf{P}_{\rm{G}}\mathbf{f},\,\,\hat{\mathbf{f}}_{\rm{C}}=\mathbf{P}_{\rm{C}}\mathbf{f},\,\,\hat{\mathbf{f}}_{\rm{H}}=\mathbf{P}_{\rm{H}}\mathbf{f}=\mathbf{f}-\hat{\mathbf{f}}_{\rm{G}}-\hat{\mathbf{f}}_{\rm{C}}.$
(41)

where the gradient projector is
$\mathbf{P}_{\rm{G}}=\mathbf{B}_{1}^{\top}(\mathbf{B}_{1}\mathbf{B}_{1}^{\top})^{\dagger}\mathbf{B}_{1}$,
the curl projector
$\mathbf{P}_{\rm{C}}=\mathbf{B}_{2}(\mathbf{B}_{2}^{\top}\mathbf{B}_{2})^{\dagger}\mathbf{B}_{2}^{\top}$
and the harmonic projector
$\mathbf{P}_{\rm{H}}=\mathbf{I}-\mathbf{L}_{1}\mathbf{L}_{1}^{\dagger}$. We
can use the simplicial filter $\mathbf{H}_{1}$ to implement these operators
stated by the following lemma.

###### Lemma 1

The projection operators [cf. (41)] are equivalent to
$\mathbf{P}_{\rm{G}}=\mathbf{U}_{\rm{G}}\mathbf{U}_{\rm{G}}^{\top}$,
$\mathbf{P}_{\rm{G}}=\mathbf{U}_{\rm{C}}\mathbf{U}_{\rm{C}}^{\top}$ and
$\mathbf{P}_{\rm{H}}=\mathbf{U}_{\rm{H}}\mathbf{U}_{\rm{H}}^{\top}$. There
exist $L_{1}=D_{\rm{G}}$, $L_{2}=D_{\rm{C}}$ and a unique
$\\{h_{0},\boldsymbol{\alpha},\boldsymbol{\beta}\\}$ such that
$\mathbf{H}_{1}=\mathbf{P}_{\rm{G}}$, which can be found by solving the system
(27) with $g_{0}=0,\mathbf{g}_{\rm{C}}=\mathbf{0}$ and
$\mathbf{g}_{\rm{G}}=\mathbf{1}$; likewise, the implementation leading to
$\mathbf{H}_{1}=\mathbf{P}_{\rm{C}}$ and $\mathbf{H}_{1}=\mathbf{P}_{\rm{H}}$.

###### Proof:

See Appendix. H in supplementary materials. ∎

Lemma 1 provides a distributed implementation of the projection operators via
the simplicial filter. For the gradient and curl components, this can be
further simplified.

###### Corollary 1

For the gradient projector $\mathbf{P}_{\rm{G}}$, there exist
$L_{1}=D_{\rm{G}},L_{2}=0$ and a unique $\\{h_{0},\boldsymbol{\alpha}\\}$ such
that $\mathbf{H}_{1}=\mathbf{P}_{\rm{G}}$. The solution is $h_{0}=0$ and
$\boldsymbol{\alpha}=\mathbf{\Phi}_{\rm{G}}^{-1}\mathbf{1}$. For the curl
projector $\mathbf{P}_{\rm{C}}$, there exist $L_{1}=0,L_{2}=D_{\rm{C}}$ and a
unique $\\{h_{0},\boldsymbol{\beta}\\}$ such that
$\mathbf{H}_{1}=\mathbf{P}_{\rm{C}}$. The solution is $h_{0}=0$ and
$\boldsymbol{\beta}=\mathbf{\Phi}_{\rm{C}}^{-1}\mathbf{1}$

###### Proof:

See Appendix. I in supplementary materials. ∎

Corollary 1 provides a simplicial filter built upon $\mathbf{L}_{1,\ell}$ to
implement the gradient projector. This is because $\mathbf{L}_{1,\rm{u}}$ has
no effect in the gradient space [cf. (14) and (22)]. Likewise for the curl
projector. Fig. 7 reports the performance of the subcomponent extraction based
on $\mathbf{H}_{1}$ via an LS design. We generated a synthetic edge flow
$\mathbf{f}=\mathbf{U}_{1}\tilde{\mathbf{f}}$ with a flat spectrum
$\tilde{\mathbf{f}}=\mathbf{1}$ on the SC in Fig. 1a. We observe that as the
filter order increases, the filter performs better as its expressive power
increases. Setting $L_{1}=L_{2}$ with $\boldsymbol{\alpha}=\boldsymbol{\beta}$
reduces the expressive power as expected. If filter orders obey $L_{1}\geq 6$
and $L_{3}\geq 3$, then the gradient (or curl) component can be perfectly
extracted, as indicated by Lemma 1 and Corollary 1. In the general parameter
setting, the decoupled design performs closer to the joint one as the filter
order grows as shown in Proposition 6.

###  VI-B Edge Flow Denoising

Figure 8: Frequency responses of the denoising filter
$\mathbf{H}_{P}=(\mathbf{I}+0.5\mathbf{L}_{1})^{-1}$ based on the grid design
with different filter orders.

Consider a noisy edge flow $\mathbf{f}=\mathbf{f}^{0}+\boldsymbol{\epsilon}$
with $\mathbf{f}^{0}$ the true edge flow and $\boldsymbol{\epsilon}$ a zero-
mean white Gaussian noise. To obtain an estimate $\hat{\mathbf{f}}$, we can
solve the regularized problem:

$\text{min}_{\hat{\mathbf{f}}}\lVert\hat{\mathbf{f}}-\mathbf{f}\lVert_{2}^{2}+\mu\hat{\mathbf{f}}\mathbf{P}\hat{\mathbf{f}},$
(42)

with an optimal solution
$\hat{\mathbf{f}}=\mathbf{H}_{P}\hat{\mathbf{f}}:=(\mathbf{I}+\mu\mathbf{P})^{-1}\mathbf{f}$
[19, 17]. For matrix $\mathbf{P}$ we have two choices:  (i) the edge Laplacian
$\mathbf{L}_{1,\ell}=\mathbf{B}_{1}^{\top}\mathbf{B}_{1}$, leading to a
regularizer $\lVert\mathbf{B}_{1}\hat{\mathbf{f}}\lVert_{2}^{2}$ to penalize
the flows with a nonzero divergence [17];  (ii) the Hodge Laplacian
$\mathbf{L}_{1}$, leading to a regularizer
$\hat{\mathbf{f}}\mathbf{L}_{1}\hat{\mathbf{f}}=\lVert\mathbf{B}_{1}\hat{\mathbf{f}}\lVert_{2}^{2}+\lVert\mathbf{B}_{2}^{\top}\hat{\mathbf{f}}\lVert_{2}^{2}$
to penalize the flows with a nonzero divergence or curl [19].

Operator $\mathbf{H}_{P}$ has the frequency response
$\tilde{H}_{P}(\lambda_{i})=1/(1+\mu\lambda_{i})$ with  (i) $\lambda_{i}=0$or
$\lambda_{i}\in\mathcal{Q}_{\rm{G}}$ for $\mathbf{P}=\mathbf{L}_{1,\ell}$,
(ii) $\lambda_{i}=0$or
$\lambda_{i}\in\mathcal{Q}_{\rm{G}}\cup\mathcal{Q}_{\rm{C}}$ for
$\mathbf{P}=\mathbf{L}_{1}$.  Thus, $\mathbf{H}_{P}$ is a low pass filter
which suppresses either the gradient frequencies or the non-harmonic
frequencies. We can implement a simplicial filter to approximate
$\mathbf{H}_{P}$. Fig. 8 shows the frequency responses of the filter
$\mathbf{H}_{P}$ with $\mathbf{P}=\mathbf{L}_{1}$, $\mu=0.5$ based on the
grid-based design, for which we considered 10 samples in the frequency
interval $[0,5.488]$ and the maximal eigenvalue is estimated with 50 steps of
power iterations.

(a) Noise-free flow $\mathbf{f}_{0}$ (b) Noisy flow $\mathbf{f}$ (c)
$\mathbf{H}=(\mathbf{I}+0.5\mathbf{L}_{1})^{-1}$ (d)
$\mathbf{H}=(\mathbf{I}+0.5\mathbf{L}_{1,\ell})^{-1}$ (e) $\mathbf{H}_{1}$,
$\boldsymbol{\alpha}=\boldsymbol{\beta}$ (f) $\mathbf{H}_{1}$, $L_{1},L_{2}=1$

Figure 9: Gradient flow denoising. (a) Edge flow $\mathbf{f}_{0}$ induced by a
node signal with a flat graph spectrum. (b) The noisy observation $\mathbf{f}$
with $e=0.46$. (c) Denoised by $\mathbf{H}_{P}$ with
$\mathbf{P}=\mathbf{L}_{1}$ with $e=0.70$ [19]. (d) Denoised by
$\mathbf{H}_{P}$ with $\mathbf{P}=\mathbf{L}_{1,\ell}$ with $e=0.73$ [17]. (e)
Denoised by a simplicial filter $\mathbf{H}_{1}$ with an order $L_{1}=L_{2}=4$
and $\boldsymbol{\alpha}=\boldsymbol{\beta}$ to preserve the gradient, with
$e=0.39$. (f) Denoised by a $\mathbf{H}_{1}$ with $L_{1}=L_{2}=1$ with
$e=0.23$.

This regularization framework relies on the assumption that the true edge flow
is either divergence-free or harmonic, which is not always true for real-world
flows [23, 8]. When different spectral properties of the underlying edge flow
are known, or certain spectral properties of the perturbed noise are known, we
are able to deal with various situations for denoising by properly designing
the simplicial filters.

We induced a gradient flow from a node signal with a flat spectrum and added
Gaussian noise with an error of $0.46$, shown in Figs. 9a and 9b. Fig. 9
illustrates the denoising results based on the regularization methods as well
as our filters to preserve the gradient component based on an LS design
(Corollary 1). From Figs. 9c to 9f, it is seen that rigidly applying the
regularization leads to large errors while the simplicial filters preserving
the gradient can denoise properly, though the setting
$\boldsymbol{\alpha}=\boldsymbol{\beta}$ again reduces the performance.

###  VI-C Currency Exchange Market

A currency exchange market can be described as a network where the vertices
represent currencies, and the edges indicate the pairwise exchange rates. If
all pairs of currencies are exchangeable, the vertex set $\mathcal{V}$ and
edge set $\mathcal{E}$ make up a complete graph. For any currencies
$i,j,k\in\mathcal{V}$, we expect an arbitrary-free condition,
$r^{i/j}r^{j/k}=r^{i/k}$ with the exchange rate $r^{i/j}$ between $i$ and $j$,
i.e., the exchange path $i\rightarrow j\rightarrow k$ provides no gain or loss
over a direct exchange $i\rightarrow k$. If we represent the exchange rates as
edge flows $f_{ij}=\log(r^{i/j})$, this can be translated into the fact that
$\mathbf{f}$ is curl-free, i.e., $f_{ij}+f_{jk}+f_{ki}=0$. Therefore, an ideal
exchange edge flow is a gradient flow. The Hodge decomposition was used to
evaluate if a market is arbitrage-free in [8] and a regularizer
$\mathbf{f}^{\top}\mathbf{L}_{1,\rm{u}}\mathbf{f}$ to promote the curl-free
property was considered to look for fair exchange rates between the bid and
ask in [23].

TABLE I: Currency exchange rates captured from Yahoo!Finance, not arbitrage-
free.

| USD | EUR | CNY | HKD | GBP | JPY | AUD
---|---|---|---|---|---|---|---
1 USD | 1 | 0.8422 | 6.3739 | 7.7666 | 0.7207 | 110.1020 | 1.3377
1 EUR | 1.1873 | 1 | 7.5681 | 9.2218 | 0.8557 | 130.7314 | 1.5883
1 CNY | 0.1539 | 0.1321 | 1 | 1.2185 | 0.1131 | 17.2683 | 0.2099
1 HKD | 0.1288 | 0.1085 | 0.8207 | 1 | 0.0928 | 14.1718 | 0.1723
1 GBP | 1.3871 | 1.1685 | 8.8414 | 10.7732 | 1 | 152.6758 | 1.8557
1 JPY | 0.0091 | 0.0077 | 0.0579 | 0.0706 | 0.0066 | 1 | 0.0122
1 AUD | 0.7475 | 0.6299 | 4.7602 | 5.8001 | 0.5385 | 82.1837 | 1
|  |  |  |  |  |  |

TABLE II: The gradient component, arbitrage-free, provides a fair market.

| USD | EUR | CNY | HKD | GBP | JPY | AUD
---|---|---|---|---|---|---|---
1 USD | 1 | 0.8422 | 6.3738 | 7.7665 | 0.7208 | 110.0171 | 1.3385
1 EUR | 1.1874 | 1 | 7.5680 | 9.2216 | 0.8559 | 130.6292 | 1.5893
1 CNY | 0.1569 | 0.1321 | 1 | 1.2185 | 0.1131 | 17.2608 | 0.2100
1 HKD | 0.1288 | 0.1084 | 0.8207 | 1 | 0.0928 | 14.1656 | 0.1723
1 GBP | 1.3873 | 1.1684 | 8.8425 | 10.7746 | 1 | 152.6286 | 1.8557
1 JPY | 0.0091 | 0.0077 | 0.0579 | 0.0706 | 0.0066 | 1 | 0.0122
1 AUD | 0.7471 | 0.6292 | 4.7618 | 5.8022 | 0.5385 | 82.1919 | 1
|  |  |  |  |  |  |

Here, we use the simplicial filter to look for an arbitrage-free exchange rate
if the market is not. We can achieve this by preserving the gradient component
of a given exchange rate flow. For a complete graph, there is one distinct
eigenvalue for the lower and upper Hodge Laplacians, which is equal to
$N_{0}$, the number of nodes. Then, with $L_{1}=1$ and $\alpha_{1}=1/N_{0}$ we
can extract the gradient component via
$\mathbf{H}_{1}=\frac{1}{N_{0}}\mathbf{L}_{1,\ell}$. Similarly, filter
$\mathbf{H}_{1}=\frac{1}{N_{0}}\mathbf{L}_{1,\rm{u}}$ can extract the curl
component.

In Table I, we captured a real-world exchange market of seven currencies at
2021/07/12 10:30 UTC from the Currency Converter Yahoo!Finance. If one unit
currency would yield more than $0.3\%$ benefit or loss after a successive
exchange, the corresponding exchange rates are seen to be non-arbitrage-free.
By computing the curl, we identified six such triangles (up to machine
precision), e.g., USD-JPY-AUD (1 USD would yield 1.0041 USD), EUR-JPY-AUD, and
HKD-GBP-JPY, and these triangular exchanges are not arbitrage-free. By
applying a filter $\mathbf{H}_{1}=1/N_{0}\mathbf{L}_{1,\ell}$ on this exchange
rate flow, we extracted its gradient flow, leading to the arbitrage-free
exchange rate flow in Table II. The same results can be obtained by solving
the LS problem considered in [8]. This simple example demonstrates the use of
simplicial filters to generate an efficient financial market. Especially in a
complete market, their form is trivial and the computational cost is much
smaller compared to the LS problems.

###  VI-D London Street Network: Fast PageRank of Edges

A PageRank approach on the edge space generating a centrality measure of edges
allows us to assess their topological importance [31]. The input edge flow
$\mathbf{f}$ is an indicator vector which has value one on the edge of
interest and zeros on the rest, then a PageRank vector $\boldsymbol{\pi}$
follows the linear system [31, Def. 6.2],
$(\gamma\mathbf{I}+\mathbf{L}_{1,\rm{n}})\boldsymbol{\pi}=\mathbf{f},$ with
$\mathbf{L}_{1,\rm{n}}$ being the normalized 1-Hodge
Laplacian111$\mathbf{L}_{1,\rm{n}}$ admits a similarity transformation to its
symmetric version, so its eigenvalues are real and carry the simplicial
frequency notion. [31, Def. 3.3] and $\gamma>0$. The solution is
$\boldsymbol{\pi}=(\gamma\mathbf{I}+\mathbf{L}_{1,\rm{n}})^{-1}\mathbf{f}$
with the PageRank operator
$\mathbf{H}_{\rm{PR}}:=(\gamma\mathbf{I}+\mathbf{L}_{1,\rm{n}})^{-1}$. For an
indicator edge flow $\mathbf{f}$ of edge $i$, the absolute values of the
entries of $\boldsymbol{\pi}$ are the influence measures edge $i$ has on the
edges and the signs the influence orientations w.r.t. the reference
orientations [31]. Furthermore, the overall importance of an edge can be
assessed with the $\ell_{2}$-norm $\lVert\boldsymbol{\pi}\lVert_{2}$ of its
PageRank vector $\boldsymbol{\pi}$. By extracting the gradient component
$\boldsymbol{\pi}_{\rm{G}}$,we can study the importance of this edge w.r.t.
the gradient space via its $\ell_{2}$-norm
$\lVert\boldsymbol{\pi}_{\rm{G}}\lVert_{2}$ or relative norm
$\frac{\lVert\boldsymbol{\pi}_{\rm{G}}\lVert_{2}}{\lVert\boldsymbol{\pi}\lVert_{2}}$;
likewise for the curl and harmonic components.

Figure 10: PageRank operator implementation analysis in the street network of
London. Top left: network illustration. Top right: Frequency responses of the
grid-based designed filter of order 9 and the Chebyshev filter of order 61
w.r.t. the desired continuous one. Bottom left: Spectral norm error of the
Chebyshev polynomial filter of different orders. Bottom right: Continuous
frequency response errors of the Chebyshev filter of different orders.

Experiment setup. The operator $\mathbf{H}_{\rm{PR}}$ can be interpreted as a
low pass filter which attenuates the high gradient and curl frequencies. But
to implement it we need to solve again an inverse problem. Differently, we
propose a faster version via a simplicial filter
$\mathbf{H}_{1}:=\mathbf{H}_{1}(\mathbf{L}_{1,\rm{n}})$ built on the
normalized Hodge Laplacian. To find the filter coefficients, we considered a
grid-based design and a Chebyshev polynomial with a desired response,
$g(\lambda)=\frac{1}{\gamma+\lambda}$ with $\lambda\in[0,1]$ and
$\gamma=0.01$.

We implemented the PageRank operator in the street network of London with 82
crossings (nodes), 130 streets (edges) and 12 triangles, as shown in the top
left of Fig. 10 [41, 42]. We considered a grid-based design with 200 samples
within the eigenvalue interval and a filter order of 9 and implemented the
Chebyshev polynomials $\mathbf{H}_{1}$ of different orders.

Results. From Fig. 10, we see that the performance of the grid-based design
decreases heavily when the filter order is larger than 9 due to the numerical
instability, while a Chebyshev design allows a more accurate design as shown
in Fig. 10.

Figure 11: PageRank vectors analysis. The scattered squares are the edges
whose PageRank vectors contain the top-five largest absolute (Top) and
relative (Bottom) total norm, gradient, curl and harmonic norms. The left
figures show the PageRank values w.r.t. edge indices. The rights figures show
the highlighted edges in the network with shaded grey indicating the total
norm, green the gradient norm, blue the curl norm and red the harmonic norm.
Figure 12: Examples of the PageRank vectors of four edges. The edge width and
color indicates the magnitude of the PageRank result on that edge. The labeled
edges are the chosen edges, also with the largest PageRank results.

We then computed the PageRank results of all edges with a Chebyshev filter of
order 61 and obtained the norms of their three components in the absolute and
relative senses. From Fig. 11, we can identify the most influential streets
(dark grey) in the network, as the indicator flow on these streets induce a
PageRank vector with the largest total norm. The streets (green) that have the
biggest influence on the gradient space are the ones on which a traffic change
leads to congestion on the intersections as the traffic flows on them have a
large divergence. The red streets induce the most impact on the harmonic space
and the blues ones on the curl space, where the traffic flows tend to induce a
global or local cyclic flow, thus a small chance of congestion. The influences
are measured in a relative sense in the bottom figures, and we notice that
most streets would not cause a large influence on the curl space.

Lastly, we showed the PageRank results of four edges to see where the
influences happen in Fig. 12. First, we observe that edges have the largest
influence on themselves as a flow change on one street usually affects itself
the most. Edge 19 (top left), sitting in the cut space, induces large
influences, containing mostly gradient components as shown in Fig. 11, on the
surrounding edges to which congestion on edge 19 would spread. Edge 27 (top
right) has large influences on the edges which form 1-dimensional ”holes”
[15], containing mostly harmonic components, saying that a traffic change on
edge 27 would less likely cause congestion. Edge 45 (bottom left), whose
PageRank result has a large total norm, as seen in Fig. 11, acts similar as
edge 27. Edge 96 (bottom right) induces smaller influences than the other
three, but they reach further in the network. The most influenced edges are
its direct upper neighbours, as also seen in the bottom (blue) of Fig. 11,
where congestion would rather not happen. Thus, we can use simplicial filters
to implement a PageRank operator for an optimal traffic network design or
control.

###  VI-E Chicago Road Network: Gradient Component Extraction

(a)  (b)

Figure 13: Chicago road network gradient component extraction. (a): Filter
frequency responses with different designs. (b): Left: SFT of the extracted
gradient component in frequency range $[0,1]$. Right: Approximation errors of
Chebyshev filters of different orders and the extracted gradient component.

We now focus on subcomponent extraction on a real-world larger network. We
consider the Chicago road network with 546 nodes, 1088 edges, and 112
triangles [44] and perform the gradient component extraction of the measured
traffic flow via $\mathbf{H}_{1}$ built on the lower Hodge Laplacian, which is
not divergence-free. Filter design in this setting has challenges because some
simplicial frequencies are close to each other, leading to the ill-
conditioning of the LS design. The Chebyshev design can avoid such issues.
This requires a continuous desired frequency response to perform gradient
extraction, which ideally is an indicator function $\mathbf{1}_{\lambda>0}$
with $\lambda\in[0,\lambda_{\rm{G},\text{max}}]$. Here we use the logistic
function $g(\lambda)=\frac{1}{1+\exp^{-k(\lambda-\lambda_{0})}}$ with growth
rate $k>0$ and the midpoint $\lambda_{0}$. If the smallest gradient frequency
is close to 0, a large $k$ and a small $\lambda_{0}$ are required for a good
approximation.

Here, we applied different filter design methods. For the LS-based methods, we
set a filter order of $9$ to avoid ill-conditioning. Moreover, we treated the
eigenvalues with a difference smaller than $0.3$ as the same for the LS
design, leading to 30 ”different” eigenvalues. For the grid-based design, we
sampled 100 points in the interval $[0,\lambda_{\rm{G},\text{max}}]$ with
$\lambda_{\rm{G},\text{max}}=10.8$ approximated by a 50-step power iteration.
Lastly, we set $k=100$ and $\lambda_{0}=0.01$ for the logistic function in the
Chebyshev polynomial design.

From Fig. 13a, the Chebyshev polynomial of an order $39$ only has one
frequency response smaller than 0.9 at the smallest gradient frequency, while
at the remaining frequencies, it is able to preserve the gradient component.
The other methods have a poorer performance especially at small gradient
frequencies. We then compared the gradient component extracted by above grid-
based and Chebyshev polynomial filters. Fig. 13b (left) reports the SFT of the
extracted flows at frequencies smaller than 1. The Chebyshev polynomial has a
good extraction ability as it performs well at the very small frequencies
while the grid-based design fails. Fig. 13b (right) shows the filter and the
extraction errors of the Chebyshev polynomial of different orders. The
extraction error cannot be further reduced as the traffic flow contains large
components at the small frequencies and the logistic function is an
approximate of the indicator function.

##  VII Conclusion

We proposed a simplicial convolutional filter as a matrix polynomial of the
Hodge Laplacians for simplicial signal processing. It generates an output as a
linear combination of the shifted simplicial signals. This shift-and-sum
operation is analogous to the convolutions of time series, images and graph
signals and allows for a distributed filter implementation. In the frequency
domain, the filter acts as a pointwise multiplication respecting the
convolution theorem. Furthermore, the lower and upper Hodge Laplacians encode
lower and upper adjacencies, respectively. For an edge flow, its lower
shifting propagates the flow to its neighbors via the common incident nodes,
while the upper one via the common triangles. By assigning two different sets
of coefficients on the lower and upper parts in the filter, we can
differentiate the lower and upper adjacencies. Via the Hodge decomposition, we
see that this corresponds to an independent control of the filter on the
gradient and curl spaces in the frequency domain. To achieve a desired
frequency response, different filter design approaches are considered with
pros and cons. The filter provides a faster and distributed solution for
subcomponent extraction, simplicial signal denoising and other tasks in
exploiting the higher-order connectivities of the network.

## References

  * [1] M. Yang, E. Isufi, M. T. Schaub, and G. Leus, “Finite impulse response filters for simplicial complexes,” in _2021 29th European Signal Processing Conference (EUSIPCO)_ , 2021, pp. 2005–2009.
  * [2] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,” _IEEE Signal Processing Magazine_ , vol. 30, no. 3, pp. 83–98, 2013.
  * [3] A. Ortega, P. Frossard, J. Kovačević, J. M. Moura, and P. Vandergheynst, “Graph signal processing: Overview, challenges, and applications,” _Proceedings of the IEEE_ , vol. 106, no. 5, pp. 808–828, 2018.
  * [4] A. Sandryhaila and J. M. Moura, “Discrete signal processing on graphs,” _IEEE Transactions on Signal Processing_ , vol. 61, no. 7, pp. 1644–1656, 2013.
  * [5] ——, “Discrete signal processing on graphs: Frequency analysis,” _IEEE Transactions on Signal Processing_ , vol. 62, no. 12, pp. 3042–3054, 2014.
  * [6] W. Huang, T. A. Bolton, J. D. Medaglia, D. S. Bassett, A. Ribeiro, and D. Van De Ville, “A graph signal processing perspective on functional brain imaging,” _Proceedings of the IEEE_ , vol. 106, no. 5, pp. 868–885, 2018\.
  * [7] K. K. Leung, W. A. Massey, and W. Whitt, “Traffic models for wireless communication networks,” _IEEE Journal on selected areas in Communications_ , vol. 12, no. 8, pp. 1353–1364, 1994.
  * [8] X. Jiang, L.-H. Lim, Y. Yao, and Y. Ye, “Statistical ranking and combinatorial hodge theory,” _Mathematical Programming_ , vol. 127, no. 1, pp. 203–244, 2011.
  * [9] O. Candogan, I. Menache, A. Ozdaglar, and P. A. Parrilo, “Flows and decompositions of games: Harmonic and potential games,” _Mathematics of Operations Research_ , vol. 36, no. 3, pp. 474–503, 2011.
  * [10] T. Gebhart, X. Fu, and R. Funk, “Go with the flow? a large-scale analysis of health care delivery networks in the united states using hodge theory,” _arXiv preprint arXiv:2110.09637_ , 2021.
  * [11] A. Mock and I. Volic, “Political structures and the topology of simplicial complexes,” _arXiv preprint arXiv:2104.02131_ , 2021.
  * [12] W. Huang and A. Ribeiro, “Metrics in the space of high order networks,” _IEEE Transactions on Signal Processing_ , vol. 64, no. 3, pp. 615–629, 2015\.
  * [13] A. Patania, G. Petri, and F. Vaccarino, “The shape of collaborations,” _EPJ Data Science_ , vol. 6, pp. 1–16, 2017.
  * [14] C. Bick, E. Gross, H. A. Harrington, and M. T. Schaub, “What are higher-order networks?” 2021.
  * [15] L.-H. Lim, “Hodge laplacians on graphs,” _SIAM Review_ , vol. 62, no. 3, pp. 685–715, 2020.
  * [16] L. J. Grady and J. R. Polimeni, _Discrete calculus: Applied analysis on graphs for computational science_. Springer, 2010, vol. 3.
  * [17] M. T. Schaub and S. Segarra, “Flow smoothing and denoising: Graph signal processing in the edge-space,” in _2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP)_. IEEE, 2018, pp. 735–739.
  * [18] S. Barbarossa and S. Sardellitti, “Topological signal processing over simplicial complexes,” _IEEE Transactions on Signal Processing_ , vol. 68, pp. 2992–3007, 2020.
  * [19] M. T. Schaub, Y. Zhu, J.-B. Seby, T. M. Roddenberry, and S. Segarra, “Signal processing on higher-order networks: Livin’on the edge… and beyond,” _arXiv preprint arXiv:2101.05510_ , 2021.
  * [20] M. Botsch, L. Kobbelt, M. Pauly, P. Alliez, and B. Lévy, _Polygon mesh processing_. CRC press, 2010.
  * [21] L. Wasserman, “Topological data analysis,” _Annual Review of Statistics and Its Application_ , vol. 5, pp. 501–532, 2018.
  * [22] M. Robinson, _Topological signal processing_. Springer, 2014, vol. 81.
  * [23] J. Jia, M. T. Schaub, S. Segarra, and A. R. Benson, “Graph-based semi-supervised & active learning for edge flows,” in _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2019, pp. 761–771.
  * [24] M. Yang, E. Isufi, and G. Leus, “Simplicial convolutional neural networks,” _arXiv preprint arXiv:2110.02585_ , 2021.
  * [25] S. Ebli, M. Defferrard, and G. Spreemann, “Simplicial neural networks,” _arXiv preprint arXiv:2010.03633_ , 2020.
  * [26] C. Bodnar, F. Frasca, Y. G. Wang, N. Otter, G. Montúfar, P. Lio, and M. Bronstein, “Weisfeiler and lehman go topological: Message passing simplicial networks,” _arXiv preprint arXiv:2103.03212_ , 2021.
  * [27] E. Bunch, Q. You, G. Fung, and V. Singh, “Simplicial 2-complex convolutional neural nets,” _arXiv preprint arXiv:2012.06010_ , 2020.
  * [28] T. M. Roddenberry, N. Glaze, and S. Segarra, “Principled simplicial neural networks for trajectory prediction,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 9020–9029.
  * [29] T. M. Roddenberry and S. Segarra, “Hodgenet: Graph neural networks for edge data,” in _2019 53rd Asilomar Conference on Signals, Systems, and Computers_. IEEE, 2019, pp. 220–224.
  * [30] J. R. Munkres, _Elements of algebraic topology_. CRC press, 2018.
  * [31] M. T. Schaub, A. R. Benson, P. Horn, G. Lippner, and A. Jadbabaie, “Random walks on simplicial complexes and the normalized hodge 1-laplacian,” _SIAM Review_ , vol. 62, no. 2, pp. 353–391, 2020.
  * [32] T. M. Roddenberry, F. Frantzen, M. T. Schaub, and S. Segarra, “Hodgelets: Localized spectral representations of flows on simplicial complexes,” _arXiv preprint arXiv:2109.08728_ , 2021.
  * [33] R. A. Horn and C. R. Johnson, _Matrix analysis_. Cambridge university press, 2012.
  * [34] D. S. Watkins, _The matrix eigenvalue problem: GR and Krylov subspace methods_. SIAM, 2007.
  * [35] E. Isufi, A. Loukas, A. Simonetto, and G. Leus, “Autoregressive moving average graph filtering,” _IEEE Transactions on Signal Processing_ , vol. 65, no. 2, pp. 274–288, 2016.
  * [36] D. I. Shuman, P. Vandergheynst, D. Kressner, and P. Frossard, “Distributed signal processing via chebyshev polynomial approximation,” _IEEE Transactions on Signal and Information Processing over Networks_ , vol. 4, no. 4, pp. 736–751, 2018.
  * [37] G. L. Sleijpen and H. A. Van der Vorst, “A jacobi–davidson iteration method for linear eigenvalue problems,” _SIAM review_ , vol. 42, no. 2, pp. 267–293, 2000.
  * [38] V. L. Druskin and L. A. Knizhnerman, “Two polynomial methods of calculating functions of symmetric matrices,” _USSR Computational Mathematics and Mathematical Physics_ , vol. 29, no. 6, pp. 112–121, 1989.
  * [39] J. C. Mason and D. C. Handscomb, _Chebyshev polynomials_. CRC press, 2002.
  * [40] D. K. Hammond, P. Vandergheynst, and R. Gribonval, “Wavelets on graphs via spectral graph theory,” _Applied and Computational Harmonic Analysis_ , vol. 30, no. 2, pp. 129–150, 2011.
  * [41] H. Youn, M. T. Gastner, and H. Jeong, “Price of anarchy in transportation networks: efficiency and optimality control,” _Physical review letters_ , vol. 101, no. 12, p. 128701, 2008.
  * [42] M. T. Schaub, J. Lehmann, S. N. Yaliraki, and M. Barahona, “Structure of complex networks: Quantifying edge-to-edge relations by failure-induced flow redistribution,” _Network Science_ , vol. 2, no. 1, pp. 66–89, 2014.
  * [43] T. A. Driscoll, N. Hale, and L. N. Trefethen, _Chebfun Guide_. Pafnuty Publications, 2014. [Online]. Available: http://www.chebfun.org/docs/guide/
  * [44] B. Stabler, H. Bar-Gera, and E. Sall, “Transportation networks for research core team,” 2018.

SUPPLEMENTARY MATERIALS

##  Appendix A Proof of Proposition 1

Due to the distributivity of matrix-vector multiplication, we have
$\mathbf{L}_{1,\ell}(a\mathbf{f}_{1}+b\mathbf{f}_{2})=a\mathbf{L}_{1,\ell}\mathbf{f}_{1}+b\mathbf{L}_{1,\ell}\mathbf{f}_{2}$,
and
$\mathbf{L}_{1,\rm{u}}(a\mathbf{f}_{1}+b\mathbf{f}_{2})=a\mathbf{L}_{1,\rm{u}}\mathbf{f}_{1}+b\mathbf{L}_{1,\rm{u}}\mathbf{f}_{2}$.
Then, by working out the expression
$\mathbf{H}_{1}(a\mathbf{f}_{1}+b\mathbf{f}_{2})$ and using the distributivity
w.r.t the addition, the linearity proof completes. Since we have
$\mathbf{L}_{1,\ell}^{l}\mathbf{L}_{1,\ell}=\mathbf{L}_{1,\ell}\mathbf{L}_{1,\ell}^{l}$,
and similarly for for $\mathbf{L}_{1,\rm{u}}$, and
$\mathbf{L}_{1,\ell}\mathbf{L}_{1,\rm{u}}=\mathbf{0}$, the shift-invariance
holds. The same proof applies to the general case with $k\neq 1$.

##  Appendix B Proof of Proposition 2

Permutation matrix $\mathbf{P}_{k}$ is orthogonal,
$\mathbf{P}_{k}\mathbf{P}_{k}^{\top}=\mathbf{P}_{k}^{\top}\mathbf{P}_{k}=\mathbf{I}$.
Following from that, we have that
$(\mathbf{P}_{k}\mathbf{L}_{k,\ell}\mathbf{P}^{\top}_{k})^{l_{1}}=\mathbf{P}_{k}\mathbf{L}_{k,\ell}^{l_{1}}\mathbf{P}^{\top}_{k}$,
and similar for
$(\mathbf{P}_{k}\mathbf{L}_{k,\rm{u}}\mathbf{P}^{\top}_{k})^{l_{2}}=\mathbf{P}_{k}\mathbf{L}_{k,\rm{u}}^{l_{2}}\mathbf{P}^{\top}_{k}$.
Then, the permuted simplicial filter is

$\displaystyle\bar{\mathbf{H}}_{k}$
$\displaystyle=h_{0}\mathbf{I}+\sum_{l_{1}=1}^{L_{1}}\alpha_{l_{1}}(\mathbf{P}_{k}\mathbf{L}_{k,\ell}\mathbf{P}^{\top}_{k})^{l_{1}}+\sum_{l_{2}=1}^{L_{2}}\beta_{l_{2}}(\mathbf{P}_{k}\mathbf{L}_{k,\rm{u}}\mathbf{P}^{\top}_{k})^{l_{2}}$
(43)
$\displaystyle=h_{0}\mathbf{I}+\sum_{l_{1}=1}^{L_{1}}\alpha_{l_{1}}\mathbf{P}_{k}\mathbf{L}_{k,\ell}^{l_{1}}\mathbf{P}^{\top}_{k}+\sum_{l_{2}=1}^{L_{2}}\beta_{l_{2}}\mathbf{P}_{k}\mathbf{L}_{k,\rm{u}}^{l_{2}}\mathbf{P}^{\top}_{k}$
$\displaystyle=\mathbf{P}_{k}\bigg{(}h_{0}\mathbf{I}+\sum_{l_{1}=1}^{L_{1}}\alpha_{l_{1}}\mathbf{L}_{k,\ell}^{l_{1}}+\sum_{l_{2}=1}^{L_{2}}\beta_{l_{2}}\mathbf{L}_{k,\rm{u}}^{l_{2}}\bigg{)}\mathbf{P}^{\top}_{k}$
$\displaystyle=\mathbf{P}_{k}\mathbf{H}_{k}\mathbf{P}^{\top}_{k}.$

Thus, the relabeled output
$\bar{\mathbf{s}}^{k}_{\rm{o}}:=\bar{\mathbf{H}}_{k}\bar{\mathbf{s}}^{k}=\bar{\mathbf{H}}_{k}(\mathbf{P}_{k}\mathbf{s}^{k})=\mathbf{P}_{k}\mathbf{H}_{k}\mathbf{P}^{\top}_{k}\mathbf{P}_{k}\mathbf{s}^{k}=\mathbf{P}_{k}\mathbf{H}_{k}\mathbf{s}^{k}:=\mathbf{P}_{k}\mathbf{s}^{k}_{\rm{o}}$.
The proof completes.

##  Appendix C Proof of Proposition 3

The diagonal matrix $\mathbf{D}_{k}$ satisfies that
$\mathbf{D}_{k}\mathbf{D}_{k}^{\top}=\mathbf{D}_{k}^{\top}\mathbf{D}_{k}=\mathbf{I}$.
Following from that, we have that
$(\mathbf{D}_{k}\mathbf{L}_{k,\ell}\mathbf{D}^{\top}_{k})^{l_{1}}=\mathbf{D}_{k}\mathbf{L}_{k,\ell}^{l_{1}}\mathbf{D}^{\top}_{k}$,
and similar for
$(\mathbf{D}_{k}\mathbf{L}_{k,\rm{u}}\mathbf{D}^{\top}_{k})^{l_{2}}=\mathbf{D}_{k}\mathbf{L}_{k,\rm{u}}^{l_{2}}\mathbf{D}^{\top}_{k}$.
Following (43), we have

$\displaystyle\bar{\mathbf{H}}_{k}$
$\displaystyle=h_{0}\mathbf{I}+\sum_{l_{1}=1}^{L_{1}}\alpha_{l_{1}}(\mathbf{D}_{k}\mathbf{L}_{k,\ell}\mathbf{D}^{\top}_{k})^{l_{1}}+\sum_{l_{2}=1}^{L_{2}}\beta_{l_{2}}(\mathbf{D}_{k}\mathbf{L}_{k,\rm{u}}\mathbf{D}^{\top}_{k})^{l_{2}}$
(44)
$\displaystyle=h_{0}\mathbf{I}+\sum_{l_{1}=1}^{L_{1}}\alpha_{l_{1}}\mathbf{D}_{k}\mathbf{L}_{k,\ell}^{l_{1}}\mathbf{D}^{\top}_{k}+\sum_{l_{2}=1}^{L_{2}}\beta_{l_{2}}\mathbf{D}_{k}\mathbf{L}_{k,\rm{u}}^{l_{2}}\mathbf{D}^{\top}_{k}$
$\displaystyle=\mathbf{D}_{k}\bigg{(}h_{0}\mathbf{I}+\sum_{l_{1}=1}^{L_{1}}\alpha_{l_{1}}\mathbf{L}_{k,\ell}^{l_{1}}+\sum_{l_{2}=1}^{L_{2}}\beta_{l_{2}}\mathbf{L}_{k,\rm{u}}^{l_{2}}\bigg{)}\mathbf{D}^{\top}_{k}$
$\displaystyle=\mathbf{D}_{k}\mathbf{H}_{k}\mathbf{D}^{\top}_{k}.$

Thus, the filter output on the reoriented simplices is
$\bar{\mathbf{s}}^{k}_{\rm{o}}:=\bar{\mathbf{H}}_{k}\bar{\mathbf{s}}^{k}=\bar{\mathbf{H}}_{k}(\mathbf{D}_{k}\mathbf{s}^{k})=\mathbf{D}_{k}\mathbf{H}_{k}\mathbf{s}^{k}:=\mathbf{D}_{k}\mathbf{s}_{\rm{o}}^{k}$.
The proof completes.

##  Appendix D Proof of Proposition 4

We show the proof for each item.

  1. 1.

First, we show that the image of $\mathbf{L}_{1,\ell}$ is equivalent to the
gradient space $\text{im}(\mathbf{B}_{1}^{\top})$.  (i) To show
$\text{im}(\mathbf{L}_{1,\ell})\subseteq\text{im}(\mathbf{B}_{1}^{\top})$:
From $\mathbf{L}_{1,\ell}=\mathbf{B}_{1}^{\top}\mathbf{B}_{1}$, for any non-
zero $\mathbf{x}\in\text{im}(\mathbf{L}_{1,\ell})$, we have
$\mathbf{x}=\mathbf{L}_{1,\ell}\mathbf{y}$, and we can always find a vector
$\mathbf{z}=\mathbf{B}_{1}\mathbf{y}\in\mathbb{R}^{N_{0}}$ such that
$\mathbf{x}=\mathbf{B}_{1}^{\top}\mathbf{z}$;  (ii) To show
$\text{im}(\mathbf{B}_{1}^{\top})\subseteq\text{im}(\mathbf{L}_{1,\ell})$: for
every non-zero $\mathbf{x}\in\text{im}(\mathbf{B}_{1}^{\top})$, we can find
some $\mathbf{y}\perp\text{ker}(\mathbf{B}^{\top}_{1})$ such that
$\mathbf{x}=\mathbf{B}_{1}^{\top}\mathbf{y}\neq\mathbf{0}$. This implies that
$\mathbf{y}\in\text{im}(\mathbf{B}_{1})$, so there exists some
$\mathbf{z}\in\mathbb{R}^{N_{1}}$ such that
$\mathbf{y}=\mathbf{B}_{1}\mathbf{z}$ and
$\mathbf{x}=\mathbf{B}_{1}^{\top}\mathbf{B}_{1}\mathbf{z}=\mathbf{L}_{1,\ell}\mathbf{z}$,
and hence
$\text{im}(\mathbf{B}_{1}^{\top})\subseteq\text{im}(\mathbf{L}_{1,\ell})$.
Combining (i) and (ii), we have that
$\text{im}(\mathbf{L}_{1,\ell})=\text{im}(\mathbf{B}_{1}^{\top})$.
Second, we show that the eigenvectors $\mathbf{U}_{\rm{G}}$ of
$\mathbf{L}_{1,\ell}$ associated with nonzero eigenvalues span the image of
$\mathbf{L}_{1,\ell}$. As the lower Laplacian $\mathbf{L}_{1,\ell}$ is
positive semidefinite, thus, diagonalizable, the geometric multiplicity of
every eigenvalue is equal to the algebraic multiplicity. This is saying that
all the eigenvectors are linearly independent and form an eigenbasis. Then,
matrix $\mathbf{U}_{\rm{G}}$ has a full column rank. Furthermore, for any
$\mathbf{x}\in\text{im}(\mathbf{L}_{1,\ell})$, we have
$\mathbf{x}=\mathbf{L}_{1,\ell}\mathbf{y}=\mathbf{U}_{\rm{G}}\mathbf{\Lambda}_{\rm{G}}\mathbf{U}_{\rm{G}}^{\top}\mathbf{y}$,
i.e., $\mathbf{x}\in\text{im}(\mathbf{U}_{\rm{G}})$ and
$\text{im}(\mathbf{L}_{1,\ell})\subseteq\text{im}(\mathbf{U}_{\rm{G}})$. Due
to
$\text{dim}\,\text{im}(\mathbf{L}_{1,\ell})=\text{rank}(\mathbf{L}_{1,\ell})=N_{\rm{G}}$,
matrix $\mathbf{U}_{\rm{G}}$ spans the image of $\mathbf{L}_{1,\ell}$ and the
gradient space $\text{im}(\mathbf{B}_{1}^{\top})$.

  2. 2.

The proof of 2) follows similarly as the proof of 1).

  3. 3.

For arbitrary eigenvectors $\mathbf{u}_{\rm{G}}$ in $\mathbf{U}_{\rm{G}}$ and
$\mathbf{u}_{\rm{C}}$ in $\mathbf{U}_{\rm{C}}$, we have
$\mathbf{u}_{\rm{G}}=\frac{1}{\lambda_{\rm{G}}}\mathbf{L}_{1,\ell}\mathbf{u}_{\rm{G}}$
and
$\mathbf{u}_{\rm{C}}=\frac{1}{\lambda_{\rm{C}}}\mathbf{L}_{1,\rm{u}}\mathbf{u}_{\rm{C}}$.
Thus, from (1), their inner product follows
$\mathbf{u}_{\rm{G}}^{\top}\mathbf{u}_{\rm{C}}=\frac{1}{\lambda_{\rm{G}}\lambda_{\rm{C}}}\mathbf{u}_{\rm{G}}^{\top}\mathbf{L}_{1,\ell}\mathbf{L}_{1,\rm{u}}\mathbf{u}_{\rm{C}}=0$,
i.e., $\mathbf{U}_{\rm{G}}\perp\mathbf{U}_{\rm{C}}$. Moreover, from the
definition of $\mathbf{L}_{1}$, matrix
$[\mathbf{U}_{\rm{G}}\,\mathbf{U}_{\rm{C}}]$ contains the eigenvectors of
$\mathbf{L}_{1}$ associated with nonzero eigenvalues. The Hodge decomposition
indicates that
$\text{im}(\mathbf{B}_{1}^{\top})\oplus\text{im}(\mathbf{B}_{2})=\text{im}(\mathbf{L}_{1})$.
By combining with 1) and 2), we have that
$\text{im}(\mathbf{B}_{1}^{\top})=\text{im}(\mathbf{U}_{\rm{G}})$ and
$\text{im}(\mathbf{B}_{2})=\text{im}(\mathbf{U}_{\rm{C}})$. The proof
completes.

  4. 4.

As $\mathbf{L}_{1}$ is positive semi-definite, the eigenvectors associated to
zero eigenvalues are linearly independent and form a basis. Any vector
$\mathbf{x}\in\text{ker}(\mathbf{L}_{1})$ in the kernel of $\mathbf{L}_{1}$
follows $\mathbf{L}_{1}\mathbf{x}=\mathbf{0}$, which means $\mathbf{x}$ is an
eigenvector associated with an eigenvalue $0$. The number of these
eigenvectors is the dimension of the kernel space. Thus, it holds that
$\text{ker}(\mathbf{L}_{1})=\text{im}(\mathbf{U}_{\rm{H}}$. Moreover, we have
$\text{ker}(\mathbf{L}_{1})=\text{ker}(\mathbf{L}_{1,\ell})\cap\text{ker}(\mathbf{L}_{1,\rm{u}})$
from the definition of $\mathbf{L}_{1}$, then the columns of
$\mathbf{U}_{\rm{H}}$ can be used as eigenvectors of $\mathbf{L}_{1,\ell}$ and
$\mathbf{L}_{1,\rm{u}}$ associated with zero eigenvalues. From 3) and
$\text{ker}(\mathbf{L}_{1})=\text{im}(\mathbf{U}_{\rm{H}}$, we have
$\mathbf{U}_{\rm{H}}\perp\mathbf{U}_{\rm{G}}$ and
$\mathbf{U}_{\rm{H}}\perp\mathbf{U}_{\rm{C}}$. Thus, matrix
$[\mathbf{U}_{\rm{H}}\,\,\mathbf{U}_{\rm{C}}]$ (or
$[\mathbf{U}_{\rm{H}}\,\,\mathbf{U}_{\rm{G}}]$) provides the eigenvectors of
$\mathbf{L}_{1,\ell}$ (or $\mathbf{L}_{1,\rm{u}}$) associated with zero
eigenvalues, and the proof completes.

  5. 5.

From 3) and 4), it is seen that matrix $\mathbf{U}_{1}$ collects all
eigenvectors of $\mathbf{L}_{1}$. From 1), 2), and 4), we have that
$\mathbf{U}_{1}$ provides all eigenvectors for $\mathbf{L}_{1,\ell}$ and
$\mathbf{L}_{1,\rm{u}}$.

##  Appendix E Proof of Proposition 5

With condition i), we can eigendecompose the operator $\mathbf{G}$ as
$\text{diag}(\mathbf{g})=\mathbf{U}_{1}^{\top}\mathbf{G}\mathbf{U}_{1}$, then
the equivalence between $\mathbf{G}$ and $\mathbf{H}_{1}$ can be achieved
through a set of linear equations in the spectral domain, i.e.,
$H_{1}(\lambda_{i})=g_{i}$, for all $i=1,\dots,N_{1}$. Based on condition ii),
this set of linear equations is equivalent to linear system (27) and (28) with
$1+D_{\rm{G}}+D_{\rm{C}}$ equations. With the filter order requirement in
condition iii), the Vandermonde matrices $\mathbf{\Phi}_{\rm G}$ and
$\mathbf{\Phi}_{\rm C}$ have full row rank. Thus, there exist at least one
solution to problem (27) and the proof completes.

##  Appendix F Proof of Proposition 6

The cost function $J$ in problem (28) is convex w.r.t. variables, $h_{0}$,
$\boldsymbol{\alpha}$ and $\boldsymbol{\beta}$. Thus, we could find the
optimality condition by setting the gradients of the cost function w.r.t. the
three variables to zeros, given by

$\begin{cases}\begin{aligned}
\nabla_{h_{0}}J=h_{0}&-g_{0}+(h_{0}\mathbf{1}+\mathbf{\Phi}_{\rm
G}\boldsymbol{\alpha}-\mathbf{g}_{\rm G})^{\top}\mathbf{1}\\\
&+(h_{0}\mathbf{1}+\mathbf{\Phi}_{\rm C}\boldsymbol{\beta}-\mathbf{g}_{\rm
C})^{\top}\mathbf{1}=0,\end{aligned}\\\
\nabla_{\boldsymbol{\alpha}}J=\mathbf{\Phi}_{\rm
G}^{\top}(h_{0}\mathbf{1}+\mathbf{\Phi}_{\rm
G}\boldsymbol{\alpha}-\mathbf{g}_{\rm G})=\mathbf{0},\\\
\nabla_{\boldsymbol{\beta}}J=\mathbf{\Phi}_{\rm
C}^{\top}(h_{0}\mathbf{1}+\mathbf{\Phi}_{\rm
C}\boldsymbol{\beta}-\mathbf{g}_{\rm C})=\mathbf{0}.\end{cases}$ (45)

First, consider the case where we have that $\lVert\mathbf{\Phi}_{\rm
G}\mathbf{\Phi}_{\rm G}^{\dagger}-\mathbf{I}\lVert_{F}=0$ and
$\lVert\mathbf{\Phi}_{\rm C}\mathbf{\Phi}_{\rm
C}^{\dagger}-\mathbf{I}\lVert_{F}=0$, i.e., $\mathbf{\Phi}_{\rm
G}\mathbf{\Phi}_{\rm G}^{\dagger}=\mathbf{I}$ and $\mathbf{\Phi}_{\rm
C}\mathbf{\Phi}_{\rm C}^{\dagger}=\mathbf{I}$, then the solution (29) results
in that $(\hat{h}_{0}\mathbf{1}+\mathbf{\Phi}_{\rm
G}\hat{\boldsymbol{\alpha}}-\mathbf{g}_{\rm G})=\mathbf{0}$ and
$(\hat{h}_{0}\mathbf{1}+\mathbf{\Phi}_{\rm
C}\hat{\boldsymbol{\beta}}-\mathbf{g}_{\rm C})=\mathbf{0}$, which satisfies
the optimality condition (45).

Secondly, consider the general case of that $\lVert\mathbf{\Phi}_{\rm
G}\mathbf{\Phi}_{\rm G}^{\dagger}-\mathbf{I}\lVert_{F}\neq 0$ and
$\lVert\mathbf{\Phi}_{\rm C}\mathbf{\Phi}_{\rm
C}^{\dagger}-\mathbf{I}\lVert_{F}\neq 0$. By substituting the solution (29)
into the optimality condition (45), we have

$\begin{cases}\begin{aligned} \nabla_{h_{0}}J=&\big{(}(\mathbf{\Phi}_{\rm
G}\mathbf{\Phi}_{\rm G}^{\dagger}-\mathbf{I})(\mathbf{g}_{\rm
G}-g_{0}\mathbf{1})\big{)}^{\top}\mathbf{1}\\\ &+\big{(}(\mathbf{\Phi}_{\rm
C}\mathbf{\Phi}_{\rm C}^{\dagger}-\mathbf{I})(\mathbf{g}_{\rm
C}-g_{0}\mathbf{1})\big{)}^{\top}\mathbf{1},\end{aligned}\\\
\nabla_{\boldsymbol{\alpha}}J=\mathbf{\Phi}_{\rm G}^{\top}(\mathbf{\Phi}_{\rm
G}\mathbf{\Phi}_{\rm G}^{\dagger}-\mathbf{I})(\mathbf{g}_{\rm
G}-g_{0}\mathbf{1}),\\\ \nabla_{\boldsymbol{\beta}}J=\mathbf{\Phi}_{\rm
C}^{\top}(\mathbf{\Phi}_{\rm C}\mathbf{\Phi}_{\rm
C}^{\dagger}-\mathbf{I})(\mathbf{g}_{\rm C}-g_{0}\mathbf{1}).\end{cases}$ (46)

For matrix $\mathbf{A}\in\mathbb{R}^{m\times n}$ with singular values
$\sigma_{i}$, for $i=1,\dots,\text{min}\\{m,n\\}$, we have that
$\lVert\mathbf{A}\lVert_{F}=\big{(}\sum_{i=1}^{\text{min}\\{m,n\\}}\sigma_{i}^{2}\big{)}^{\frac{1}{2}}$.
Thus, for $\lVert\mathbf{\Phi}_{\rm G}\mathbf{\Phi}_{\rm
G}^{\dagger}-\mathbf{I}\lVert_{F}\rightarrow 0$ and $\lVert\mathbf{\Phi}_{\rm
C}\mathbf{\Phi}_{\rm C}^{\dagger}-\mathbf{I}\lVert_{F}\rightarrow 0$, the
number of trivial (zero) singular values of $\mathbf{\Phi}_{\rm
G}\mathbf{\Phi}_{\rm G}^{\dagger}-\mathbf{I}$ and $\mathbf{\Phi}_{\rm
C}\mathbf{\Phi}_{\rm C}^{\dagger}-\mathbf{I}$ increases. Accordingly, the
number of trivial entries in $(\mathbf{\Phi}_{\rm G}\mathbf{\Phi}_{\rm
G}^{\dagger}-\mathbf{I})(\mathbf{g}_{\rm G}-g_{0}\mathbf{1})$ and
$(\mathbf{\Phi}_{\rm C}\mathbf{\Phi}_{\rm
C}^{\dagger}-\mathbf{I})(\mathbf{g}_{\rm C}-g_{0}\mathbf{1})$ increases, which
corresponds to a suboptimal condition of (45), i.e., the gradients
$\nabla_{h_{0}}J(\hat{h}_{0},\hat{\boldsymbol{\alpha}},\hat{\boldsymbol{\beta}})\rightarrow
0$,
$\nabla_{\boldsymbol{\alpha}}J(\hat{h}_{0},\hat{\boldsymbol{\alpha}})\rightarrow\mathbf{0}$
and
$\nabla_{\boldsymbol{\beta}}J(\hat{h}_{0},\hat{\boldsymbol{\beta}})\rightarrow\mathbf{0}$.
The proof completes.

##  Appendix G Proof of Proposition 7

Since the operator $\mathbf{G}$ corresponds to the desired continuous
harmonic, gradient and curl frequency responses, it can be diagonalized by
$\mathbf{U}_{1}$. Therefore, we have that

$\displaystyle\lVert\mathbf{G}-\mathbf{H}_{\rm{c}}\lVert_{2}=\lVert\mathbf{U}_{1}(g(\mathbf{\Lambda})-\tilde{H}_{1}(\mathbf{\Lambda}))\mathbf{U}_{1}^{\top}\lVert_{2}$
(47) $\displaystyle=$ $\displaystyle\lVert
g(\mathbf{\Lambda})-\tilde{H}_{1}(\mathbf{\Lambda})\lVert_{2}=\underset{i=1,\dots,N_{1}}{\text{max}}|g(\lambda_{i})-\tilde{H}_{1}(\lambda_{i})|$

where the diagonal matrix $g(\mathbf{\Lambda})$ has entries
$g(\lambda_{i})=g_{0}$ for $\lambda_{i}\in\mathcal{Q}_{\rm{H}}$,
$g(\lambda_{i})=g_{\rm{G}}(\lambda_{i})$ for
$\lambda_{i}\in\mathcal{Q}_{\rm{G}}$ and
$g(\lambda_{i})=g_{\rm{C}}(\lambda_{i})$ for
$\lambda_{i}\in\mathcal{Q}_{\rm{C}}$. The frequency response
$\tilde{H}_{1}(\lambda_{i})$ for $\lambda_{i}\in\mathcal{Q}$ is given in (38).
Moreover, based on the definition of $B_{1}(L_{1})$ and $B_{2}(L_{2})$ we have
that

$\underset{i=1,\dots,N_{1}}{\text{max}}|g(\lambda_{i})-\tilde{H}_{1}(\lambda_{i})|\leq\text{max}\big{\\{}B_{1}(L_{1}),B_{2}(L_{2})\big{\\}}=B.$
(48)

The proof completes.

##  Appendix H Proof of Lemma 1

We first show the equivalence between the two projection operator forms. From
the Hodge decomposition, the gradient, the curl and the harmonic components
are in the subspaces $\text{im}(\mathbf{B}_{1}^{\top})$,
$\text{im}(\mathbf{B}_{2})$ and $\text{ker}(\mathbf{L}_{1})$, respectively.
Furthermore, from Proposition 4, we have that
$\text{im}(\mathbf{B}_{1}^{\top})=\text{im}(\mathbf{U}_{\rm{G}})$,
$\text{im}(\mathbf{B}_{2})=\text{im}(\mathbf{U}_{\rm{C}})$ and
$\text{ker}(\mathbf{L}_{1})=\text{im}(\mathbf{U}_{\rm{H}})$. Thus, each
subcomponent can be obtained as the orthogonal projection of $\mathbf{f}$ onto
the subspace spanned by the eigenbasis, i.e., the LS estimate. The gradient
projection is
$\mathbf{P}_{\rm{G}}:=\mathbf{U}_{\rm{G}}\mathbf{U}_{\rm{G}}^{\top}$, the curl
one $\mathbf{P}_{\rm{C}}:=\mathbf{U}_{\rm{C}}\mathbf{U}_{\rm{C}}^{\top}$ and
the harmonic one
$\mathbf{P}_{\rm{H}}:=\mathbf{U}_{\rm{H}}\mathbf{U}_{\rm{H}}^{\top}$. This can
be shown via the SFT as well, i.e.,
$\mathbf{f}_{\rm{G}}=\mathbf{U}_{\rm{G}}\tilde{\mathbf{f}}_{\rm{G}}=\mathbf{U}_{\rm{G}}\mathbf{U}_{\rm{G}}^{\top}\mathbf{f}$,
likewise for the other two.

Second, the simplicial filter $\mathbf{H}_{1}$ can implement the gradient
projector $\mathbf{P}_{\rm{G}}=\mathbf{U}_{\rm{G}}\mathbf{U}_{\rm{G}}^{\top}$,
iff we have that

$\mathbf{H}_{1}=\mathbf{U}_{\rm{G}}\mathbf{U}_{\rm{G}}^{\top}=[\mathbf{U}_{\rm{G}}^{\perp}\,\,\mathbf{U}_{\rm{G}}]\textstyle\begin{bmatrix}\mathbf{0}&\\\
&\mathbf{I}_{N_{\rm{G}}}\end{bmatrix}\textstyle\begin{bmatrix}(\mathbf{U}_{\rm{G}}^{\perp})^{\top}\\\
\mathbf{U}_{\rm{G}}^{\top}\end{bmatrix},$ (49)

with
$\mathbf{U}_{\rm{G}}^{\perp}=[\mathbf{U}_{\rm{H}}\,\,\mathbf{U}_{\rm{C}}]$. We
have that
$\mathbf{H}_{1}=\mathbf{U}_{1}\tilde{\mathbf{H}}_{1}\mathbf{U}_{1}^{\top}$
from (23). Thus, (49) is equivalent to problem (27) with $g_{0}=0$,
$\mathbf{g}_{\rm{C}}=\mathbf{0}$ and $\mathbf{g}_{\rm{G}}=\mathbf{1}$. With
$L_{1}=D_{\rm{G}}$ and $L_{2}=D_{\rm{C}}$, there admits a unique solution
$\\{h_{0},\boldsymbol{\alpha},\boldsymbol{\beta}\\}$ to system (27). Similar
procedure can be followed for the implementation of the curl and harmonic
projectors. The proof completes.

##  Appendix I Proof of Corollary 1

To implement the projector $\mathbf{P}_{\rm{G}}$ via $\mathbf{H}_{1}$ with
$L_{2}=0$ ($\boldsymbol{\beta}=\mathbf{0}$), from (49), it is equivalent to
set $g_{0}=0$ for $\lambda_{i}\in\mathcal{Q}_{\rm{H}}\cup\mathcal{Q}_{\rm{C}}$
and $g(\lambda_{i})=1$ for $\lambda_{i}\in\mathcal{Q}_{\rm{G}}$ in (24), i.e.,
$\mathbf{g}=[0\,\,\mathbf{1}_{D_{\rm{G}}}^{\top}]^{\top}$. This returns
problem (27) without $\mathbf{\Phi}_{\rm{C}}$ and $\boldsymbol{\beta}$, i.e.,

$\underset{h_{0},\boldsymbol{\alpha}}{\text{min}}\left\|\begin{bmatrix}{\bf
1}\ \vline&\begin{matrix}{\bf 0}\\\
\mathbf{\Phi}_{\rm{G}}\end{matrix}\end{bmatrix}\begin{bmatrix}h_{0}\\\
\boldsymbol{\alpha}\end{bmatrix}-\mathbf{g}\right\|^{2}_{2}.$ (50)

If $L_{1}=D_{\rm{G}}$, the system matrix is square and any two rows are
linearly independent, there admits a unique solution of $h_{0}=0$ and
$\boldsymbol{\alpha}=\mathbf{\Phi}_{\rm{}_{G}}^{-1}\mathbf{1}$. Similar
procedure can be followed for the curl projector $\mathbf{P}_{\rm{C}}$. The
proof completes.