TOPOLOGICAL SLEPIANS MAXIMALLY LOCALIZED REPRESENTATIONS OF SIGNALS OVER SIMPLICIAL COMPLEXES Claudio Battiloro Paolo Di Lorenzo and Sergio Barbarossa

2025-05-06 0 0 486.18KB 6 页 10玖币

侵权投诉

TOPOLOGICAL SLEPIANS: MAXIMALLY LOCALIZED REPRESENTATIONS

OF SIGNALS OVER SIMPLICIAL COMPLEXES

Claudio Battiloro, Paolo Di Lorenzo, and Sergio Barbarossa

DIET Department, Sapienza University of Rome, Via Eudossiana 18, 00184, Rome, Italy

E-mail: {claudio.battiloro, paolo.dilorenzo, sergio.barbarossa}@uniroma1.it

ABSTRACT

This paper introduces topological Slepians, i.e., a novel class of sig-

nals deﬁned over topological spaces (e.g., simplicial complexes) that

are maximally concentrated on the topological domain (e.g., over a

set of nodes, edges, triangles, etc.) and perfectly localized on the

dual domain (e.g., a set of frequencies). These signals are obtained

as the principal eigenvectors of a matrix built from proper localiza-

tion operators acting over topology and frequency domains. Then,

we suggest a principled procedure to build dictionaries of topolog-

ical Slepians, which theoretically provide non-degenerate frames.

Finally, we evaluate the effectiveness of the proposed topological

Slepian dictionary in two applications, i.e., sparse signal representa-

tion and denoising of edge ﬂows.

Index Terms—Topological signal processing, simplicial com-

plexes, localized representation, sparse signal recovery, frames.

1. INTRODUCTION

In the last few years, there was a surge of interest in developing pro-

cessing techniques for signals deﬁned over irregular domains, which

are not necessarily metric spaces. In particular, the ﬁeld of graph

signal processing (GSP) studies methodologies to analyze and pro-

cess signals deﬁned over the vertices of a graph [1], [2]. To this aim,

several graph operators (e.g. adjacency, Laplacian, etc.) have been

introduced, thus leading to alternative designs of ﬁlters on graphs

and graph Fourier transforms. The main feature of these processing

tools is that they come to depend on the connectivity of the graph,

which is encoded into the structure of the adopted graph operator.

However, despite their overwhelming popularity, graph representa-

tions can only take into account pairwise relationships among data.

In complex interconnected systems, the interactions often can-

not be reduced to simple pairwise relationships, and graph represen-

tations might result incomplete and inefﬁcient [3–9]. For instance,

in biological networks, multi-way interactions among complex sub-

stances (such as genes, proteins, or metabolites) cannot be evoked

using simply pairwise relationships [4]; also, in the brain, groups of

neurons typically activate at the same time [6]. These applications

have sparked a renewed interest in extending GSP tools to incorpo-

rate multi-way relationships among data, thus leading to the emer-

gent ﬁeld of topological signal processing (TSP) [10,11]. In this con-

text, the seminal works [10, 11] illustrated the beneﬁts obtained by

processing signals deﬁned over simplicial complexes, which are spe-

ciﬁc examples of hyper-graphs with a rich algebraic description that

can easily encode multi-way data. Then, several papers have given

important contributions to TSP. For instance, the work in [12] pro-

posed FIR ﬁlters for signals deﬁned over simplicial complexes, hing-

ing on the Hodge decomposition, where the Fourier modes are eigen-

vectors of higher order combinatorial Laplacians [13]. The work

in [14] introduced generalized Laplacian for embedding simplicial

complexes into traditional graphs. In [15] the authors proposed self-

driven graph Volterra models that can capture higher-order interac-

tions among nodal observables available in networked data. Very re-

cently, some works focused on processing signals deﬁned over cell

complexes, i.e., topological spaces not constrained to respect any in-

clusion property [16, 17]. Finally, deep neural architectures able to

learn from data deﬁned over topological spaces (e.g., simplicial or

cell complexes) have been recently developed in [18–23].

One of the fundamental problems in signal processing is to ob-

tain a sparse representation of the signals of interest. Typically, the

sparser is the representation, the better is the performance of several

processing tasks such as, e.g., compression, denoising, sampling and

recovery [24]. In the context of TSP, a natural basis for signal rep-

resentation is given by the topological Fourier modes [13]. How-

ever, often the signal of interest is highly localized over a portion of

the topological domain, i.e., it is mostly concentrated over a set of

nodes, edges, or triangles, while being at the same time highly (if

not perfectly) localized over a speciﬁc set of frequencies. In such

a case, Fourier modes might not lead to an efﬁcient and sparse rep-

resentation of localized topological signals, since they are usually

non-sparse, i.e., not localized on sub-regions of the complex. To

ﬁnd localized spectral representations, the work in [25] proposed a

family of wavelets for simplicial signals, respecting the Hodge de-

composition and extending the graph wavelets from [26].

In this work, moved by the necessity of ﬁnding efﬁcient sparse

representations of localized signals lying over simplicial complexes,

we introduce topological Slepians, i.e., a class of signals that are

maximally concentrated on the simplicial domain (e.g., over a set

of nodes, edges, triangles, etc.) and perfectly localized on the dual

domain (e.g., a set of frequencies). Due to their joint localization

properties, they represent the simplicial counterpart of the prolate

spheroidal wave functions introduced by Slepian and Pollack for

continuous-time signals [27], and of the graph Slepians introduced

in [28,29] for graph signals. These signals are obtained as the princi-

pal eigenvectors of a matrix built from localization operators deﬁned

over the topological space and its dual (frequency) domain. Then,

we propose a principled way to build a dictionary having topologi-

cal Slepians as atoms, identifying the theoretical conditions neces-

sary to build a non-degenerate frame. Finally, we apply the proposed

methodology to two cases of interest, namely, sparse signal repre-

sentation and denoising of edge ﬂows, illustrating how topological

Slepians compare favourably with state-of-the-art techniques.

2. BACKGROUND

In this section, we review basics of topological signal processing

over simplical complexes that will be useful along the paper.

Simplicial complex and signals. Given a ﬁnite set of vertices V, a

k-simplex Hkis a subset of Vwith cardinality k+ 1, e.g., edges

are 1-simplices, and triangles are 2-simplices. A face of Hkis a

subset with cardinality k, and thus a k-simplex has k+ 1 faces. A

arXiv:2210.14758v1 [eess.SP] 26 Oct 2022

coface of Hkis a (k+ 1)-simplex that includes Hk[10, 30]. If

two simplices share a common face, then they are lower neighbours;

if they share a common coface, they are upper neighbours [31]. A

simplicial complex Xkof order K, is a collection of k-simplices

Hk,k= 0,...,K such that, for any Hk∈ Xk,Hk−1∈ Xkif

Hk−1⊂ Hk(inclusivity property). We denote the set of k-simplices

in Xkas Dk:= {Hk:Hk∈ Xk}, with |Dk|=Nkand Dk⊆ Xk.

We are interested in processing signals deﬁned over a simplicial

complex. A k-simplicial signal is deﬁned as a mapping from the set

of all k-simplices contained in the complex to real numbers:

xk:Dk→R, k = 0,1, . . . K. (1)

The order of the signal is one less the cardinality of the elements of

Dk. In most of the cases the focus is on complex X2of order up to

two, thus a set of vertices Vwith |V| =V, a set of edges Ewith

|E| =Eand a set of triangles Twith |T | =Tare considered,

resulting in D0=V(simplices of order 0), D1=E(simplices of

order 1) and D2=T(simplices of order 2).

Algebraic representations. The structure of a simplicial complex

Xkis fully described by the set of its incidence matrices Bk,k=

1,...,K, given a reference orientation. The entries of the incidence

matrix Bkestablish which k-simplices are incident to which (k−1)-

simplices. Denoting the fact that two simplex have the same orien-

tation with Hk−1,i ∼Hk,j and viceversa with Hk−1,i 6∼ Hk,j ,the

entries of Bkare deﬁned as:

Bki,j =





0,if Hk−1,i 6⊂ Hk,j

1,if Hk−1,i ⊂ Hk,j and Hk−1,i ∼ Hk,j

−1,if Hk−1,i ⊂ Hk,j and Hk−1,i 6∼ Hk,j

(2)

From the incidence information, we can build the high order combi-

natorial Laplacian matrices [32] of order k= 0,...,K as:

L0=B1BT

1,(3)

Lk=BT

kBk

|{z }

+Bk+1BT

k+1

| {z }

, k = 1,...,K −1,(4)

LK=BT

KBK.(5)

All Laplacian matrices of intermediate order, i.e. k= 1,...,K−1,

contain two terms: The ﬁrst term Ld

k, also known as lower Lapla-

cian, encodes the lower connectivity among k-order simplices; the

second term Lu

k, also known as upper Laplacian, encodes the upper

connectivity among k-order simplices. For example, two edges are

lower adjacent if they share a common vertex, whereas they are up-

per adjacent if they are faces of a common triangle.

Hodge decomposition: High order Laplacians admit a Hodge de-

composition [30], such that the k-simplicial signal space can be de-

composed as:

RNk=imBT

kMimBk+1MkerLk,(6)

where Lis the direct sum of vector spaces, and ker(·) and im(·)

are the kernel and image spaces of a matrix, respectively. Thus, any

signal xkof order kadmits the following orthogonal decomposition:

xk=BT

kxk−1

| {z }

(a)

+Bk+1 xk+1

| {z }

(b)

|{z}

(c)

.(7)

To give an interpretation of (7), let us consider the decomposition of

edge ﬂow signals x1, i.e., k= 1. Then, the following holds [10,33]:

(a) Applying matrix B1to an edge ﬂow x1computes its net ﬂow

(i.e. the difference between inﬂow and outﬂow) at each node,

while applying its adjoint BT

1to a node signal x0computes the

gradients along the edges. We call BT

1x0the irrotational com-

ponent of x1and im(BT

1)the gradient space.

(b) The matrix BT

2is a curl operator and applying it to an edge ﬂow

x1computes the circulation over each triangle. Its adjoint B2

induces an edge ﬂow x1from a triangle signal x2. We call B2x2

the solenoidal component of x1and im(B2)the curl space.

x1is called the harmonic component

and ker(L1)is called the harmonic space. Any edge ﬂow e

has zero divergence and zero curl.

Simplicial Fourier transform. Simplicial signals of various order

can be represented over the bases of the eigenvectors of the corre-

sponding high order Laplacian matrices. Hence, using the eigen-

decomposition Lk=UkΛkUT

k, the Simplicial Fourier Transform

(SFT) of order kis deﬁned as the projection of a k-order signal onto

the eigenvectors of Lk[10, 31]:

xk,UT

kxk.(8)

We refer to the eigenvalue domain of the SFT as the frequency do-

main. An interesting consequence of the Hodge decomposition in

(7) is that the eigenvectors belonging to im(Ld

k)are orthogonal to

those belonging to im(Lu

k), for all k= 1,...,K −1. Therefore,

the eigenvectors of Lkare given by the union of the eigenvectors of

k(spanning the curl sub-space), the eigenvectors of Ld

k(spanning

the gradient sub-space), and the kernel of Lk(spanning the harmonic

sub-space) [31]. For the sake of simplicity, but without loss of gen-

erality, in the sequel we will focus on the processing of edge ﬂow

signals. Thus, we will denote x1with x,Ukwith U,L1with L,Ld

with Ldand Lu

1with Lu, such that L=Ld+Lu.

3. TOPOLOGICAL SLEPIANS

The eigenvectors of higher order Laplacians composing the simpli-

cial Fourier basis are generally non-sparse, meaning that exploiting

them for sparse representation of localized signals usually leads to

poor performance [25]. Thus, in this section we introduce topolog-

ical Slepians, i.e., a novel class of simplicial signals that are max-

imally concentrated over a sub-set of edges, while being perfectly

localized over the dual domain, i.e. a set of frequencies. Following

the approach of [28], we introduce two localization operators acting

onto an edge concentration set, say S, and onto a frequency concen-

tration set, say F, respectively. The edge-limiting operator onto the

edge set Sis deﬁned as the matrix CS∈RE×Egiven by:

CS= diag(1S),(9)

where 1S∈REis a vector having ones in the index positions speci-

ﬁed in S, and zero otherwise; and diag(z)denotes a diagonal matrix

having zon the diagonal. Clearly, from (9), an edge signal xis per-

fectly localized onto the set Sif CSx=x. Similarly, the frequency

limiting operator can be deﬁned as:

BF=Udiag(1F)UT,(10)

which represents an ideal band-pass ﬁlter over the frequency set F.

Clearly, an edge signal is perfectly localized over the bandwidth F

if BFx=x. The matrices in (9) and (10) are projection operators,

having maximum spectral radius equal to one.

We deﬁne topological Slepians as the set of orthonormal vectors

that are maximally concentrated over the edge set S, and perfectly

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

TOPOLOGICALSLEPIANS:MAXIMALLYLOCALIZEDREPRESENTATIONSOFSIGNALSOVERSIMPLICIALCOMPLEXESClaudioBattiloro,PaoloDiLorenzo,andSergioBarbarossaDIETDepartment,SapienzaUniversityofRome,ViaEudossiana18,00184,Rome,ItalyE-mail:fclaudio.battiloro,paolo.dilorenzo,sergio.barbarossag@uniroma1.itABSTRACTThispaperint...

展开>> 收起<<

TOPOLOGICAL SLEPIANS MAXIMALLY LOCALIZED REPRESENTATIONS OF SIGNALS OVER SIMPLICIAL COMPLEXES Claudio Battiloro Paolo Di Lorenzo and Sergio Barbarossa.pdf

共6页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

TOPOLOGICAL SLEPIANS MAXIMALLY LOCALIZED REPRESENTATIONS OF SIGNALS OVER SIMPLICIAL COMPLEXES Claudio Battiloro Paolo Di Lorenzo and Sergio Barbarossa

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: