Perfect Reconstruction Two-Channel Filter Banks on Arbitrary Graphs Junxia You and Lihua Yang

2025-05-02 0 0 1.4MB 33 页 10玖币

侵权投诉

Perfect Reconstruction Two-Channel Filter Banks on

Arbitrary Graphs∗

Junxia You and Lihua Yang†

School of Mathematics, Sun Yat-sen University, Guangzhou, China

Guangdong Province Key Laboratory of Computational Science

March 1, 2025

Abstract

This paper extends the existing theory of perfect reconstruction two-channel ﬁlter

banks from bipartite graphs to non-bipartite graphs. By generalizing the concept

of downsampling/upsampling we establish the frame of two-channel ﬁlter bank on

arbitrary connected, undirected and weighted graphs. Then the equations for perfect

reconstruction of the ﬁlter banks are presented and solved under proper conditions.

Algorithms for designing orthogonal and biorthogonal banks are given and two typical

orthogonal two-channel ﬁlter banks are calculated. The locality and approximation

properties of such ﬁlter banks are discussed theoretically and experimentally.

Keywords: Graph signal processing, wavelets, two-channel ﬁlter banks, perfect

reconstruction

1 Introduction

Graph signal processing (GSP) is an emerging ﬁeld that studies signals deﬁned on the

vertices of a weighted graph: i.e. vertices connected by edges associated with non-negative

weights [33, 23]. Weighted graphs provide a natural representation for data domain in

many applications, such as the social networks, web information analysis, sensor networks

and machine learning. The collections of samples on these graphs are termed as graph

signals. For example, a social network can be modeled as a weighted graph by viewing

the individual accounts as vertices, and the relationships between them as weighted edges.

Then one can analyze the information of all the accounts in this network by using GSP

tools. Similarly, in a sensor network, the sensors and the distances between each of them

∗Supported by National Natural Science Foundation of China (Nos. 12171488, 11771458) and Guang-

dong Province Key Laboratory of Computational Science at the Sun Yat-sen University (2020B1212060032).

†Corresponding author

arXiv:2210.02024v2 [cs.IT] 3 Apr 2023

constitute a graph and the recorded data on the sensors deﬁnes a signal on the graph.

In recent years, graph signal processing technology has been widely used [23, 13, 41, 15].

Graph signal processing aims at extending the well-developed theory and methods for

analysis of signals deﬁned in regular domains to those deﬁned in irregular graph domains.

There has been a lot of research in this ﬁeld, including the Fourier transform of graph

functions [30, 5, 40], graph sampling and reconstruction [19, 11, 38], approximation theory

of graph functions [25, 12], graph wavelets and multiscale analysis [21, 2, 10, 6, 17, 9], and

so on.

In many applications, a certain type of transform is applied to the original signal

if it brings beneﬁts in analysis in the transformed domain than in the original signal

domain. And then the processing and analysis is performed on the coeﬃcients of the

transformed data. For processing of signals deﬁned in the regular domains, transforms

such as Fourier transform, windowed Fourier transform and wavelet transform have been

developed. Among them, wavelet transform is particularly widely used for processing

nonstationary signals because it catches the local information of the signal in both time and

frequency domains. Naturally, people want to extend the theory and methods of wavelet

analysis to the graph signal processing. However, due to the irregularity of graph structure,

some traditional operations such as translation and dilation are diﬃcult to establish in the

graph settings. But people are still actively seeking ways to develop wavelet transforms on

graphs.

In [3], Crovella and Kolaczyk constructed a series of simple functions on each neigh-

bourhood of every vertex so that they are compactly supported and have zero integral over

the entire vertex set. They refer to these functions as graph wavelet functions. Coifman

and Maggioni proposed the concept of diﬀusion wavelets and use diﬀusion as a smoothing

and scaling tool to enable coarse graining and multiscale analysis in [2]. Gavish et al.

[9] ﬁrst constructed multiscale wavelet-like orthonormal bases on hierarchical trees. They

proved that function smoothness with respect to a metric induced by the tree is equiva-

lent to approximate sparsity. Hammond et al. [10] constructed wavelet transforms in the

graph domain based on the spectral graph theory, and they presented a fast Chebyshev

polynomial approximation algorithm to improve eﬃciency. In follow-up work, they also

built an almost tight wavelet frame based on the polynomial ﬁlters [35]. In [34], Shuman et

al. proposed ﬁlters adapted to the distribution of graph Laplacian eigenvalues, leading to

atoms with better discriminatory power. Inspired by the ﬁrst-order spline ﬁlters in classical

signal processing, Ekambaram et al. designed a class of critically sampled and perfect re-

contruction spline wavelets, and was later extended to higher-order and exponential spline

ﬁlters by Kotzagiannidis and Dragotti [8, 14]. In [21], Narang and Ortega designed perfect

reconstruction two-channel ﬁlter banks on bipartite graphs based on the spectral folding

phenomenon. For non-bipartite graphs, they proposed an algorithm that can decompose

any graph into a series of bipartite subgraphs, thereby extending the design to arbitrary

graphs. In the follow-up work [18], they constructed a class of biorthogonal wavelet ﬁlter

banks on bipartite graphs, where all ﬁlters are polynomials in the Laplacian matrix.

When a non-bipartite graph is decomposed into several bipartite subgraphs, the signal

processing on the original graph comes down to the signal processing on every bipartite

subgraph. A challenging topic is: can we construct perfect reconstruction two-channel

ﬁlter banks on non-bipartite graphs directly? Inspired by [21], by generalizing the con-

cepts of downsampling and upsampling operations, we extend the construction of perfect

reconstruction two-channel ﬁlter banks proposed in [21] to arbitrary connected, undirected,

and weighted graphs in this paper. The locality and approximation property of such ﬁlter

banks are discussed theoretically and experimentally.

The rest of the paper is organized as follows: Section 2 introduces some basic concepts

including the graph Fourier transform, ﬁlters, downsampling and upsampling, and the

two-channel ﬁlter banks. The related work [21] is also introduced brieﬂy in this section to

motivate our work, and the contribution of this paper is summarized at the end of this

section. In section 3, the main theorem for constructing perfect reconstruction two-channel

ﬁlter banks on arbitrary graphs is established. The generalized downsamplers/upsamplers

are constructed and the perfect reconstruction equations for a two-channel ﬁlter bank are

presented. Algorithms for designing orthogonal and biorthogonal ﬁlter banks are given and

two typical orthogonal ﬁlter banks are designed. Finally, the locality and approximation

property of the proposed ﬁlter banks are discussed theoretically and experimentally in

Section 4.

2 Preliminary

2.1 Notations

We start by introducing the notations used throughout this paper. Vectors are denoted by

lowercase boldfaced letters and matrices are denoted by uppercase boldfaced letters. The

set of real numbers and the set of natural numbers are denoted as Rand Nrespectively.

For any N, M ∈N, the linear spaces of all the N-dimensional column vectors and all the

matrices of order N×Mare respectively denoted by RNand RN×M.RN

+is the set of

vectors in RNwhose components are all non-negative. The ith component of a vector xis

denoted by xior x(i). The (i, j)-entry of matrix Ais denoted by A(i, j) or aij. Let 1N

and 0Nrepresent the vectors in RNwhose components are all 1 and 0 respectively. IN

stands for the identity matrix of order N. For 1 ≤i≤N, let eibe the ith column of IN.

For any x∈R, [x] represents the largest integer not exceeding x.

Let G= (V,E,W) be a connected, undirected and weighted graph with neither loops

nor multiple edges, where V={v1, ..., vN}is the set of vertices, Eis the set of edges, and

W∈RN×Nis the adjacency matrix with its entry wij the nonnegative weight of the edge

between the vertices viand vj. A graph signal f:V → Ris a function deﬁned on the

vertices of the graph. Once the vertex order is ﬁxed, the graph signal can be written as a

vector f:= (f(v1), ..., f(vN))>∈RN, where the ith component equals the value of fon vi.

In this paper, we will not distinguish the diﬀerence between fand fif no confusion arises.

The superscript >indicates the transpose operation. Function diag(·) maps a vertor to

a diagonal matrix, or a matrix to its diagonal. We denote by hv,uithe inner product of

the vectors uand vin the Euclidean space RN. The induced norm is called 2-norm and

denoted by kuk2. We adopt the following Dirichlet form to measure the oscillation of a

graph signal fon G[33]:

S2(f) := 1

i=1

j=1

wij|f(vi)−f(vj)|2.(2.1)

It is easy to see that the larger the value of S2(f), the stronger the signal oscillates and

vice versa.

2.2 Fourier Transform and Filters

The Laplacian matrix of a graph G= (V,E,W) is deﬁned as L:= D−W, where Dis the

diagonal degree matrix diag(d1, ..., dN) with elements di=PN

j=1 wij [1]. As the matrix L

is real symmetric and positive semi-deﬁnite, there exists a set of orthonormal eigenvectors

{ul}N

l=1 and real eigenvalues 0 = λ1< λ2≤ ··· ≤ λNsuch that L=UΛU>, where

U:= (u1, ..., uN),Λ := diag(λ1, ..., λN).

The set of the eigenvectors {ul}N

l=1 are often viewed as the graph Fourier basis and Uis

called the Fourier basis matrix. Using the Fourier basis, the graph Fourier transform and

the inverse Fourier transform are deﬁned respectively as [33]:

f:= U>f,f=Uˆ

f,∀f∈RN.

With the Laplacian matrix L, the Dirichlet form (2.1) can be rewritten as

S2(f) = f>Lf =ˆ

f>Λˆ

k=1

λk|ˆ

f(k)|2.(2.2)

Since S2(ul) = u>

lLul=λl, l = 1, ..., N, we have that S2(u1)≤ ··· ≤ S2(uN), which

shows that the oscillation of the Fourier basis u1, ..., uNbecomes stronger as the index l

increases. In view of the above, the Dirichlet form S2(f) is regarded as the frequency of f.

We call the set σ(L) := {λ1< λ2≤ ··· ≤ λN}the spectra of L.

There are serval ways to deﬁne the Fourier transform of graph signals. In addition to

the above-mentioned deﬁnition of using the eigenvectors of the graph Laplacian matrix L,

it can also be deﬁned as the eigenvectors of the normalized Laplacian L:= D−1/2LD−1/2or

the adjacency matrix W[21, 30, 31]. From the perspective of minimizing the `1oscillation

of signals, we proposed a new deﬁnition of the graph Fourier basis in [40], which is proved

to have better sparsity. In general, a graph Fourier basis {u1, ..., uN}is actually a family

of graph signals, which constitute an orthonormal basis of the signal space RN. As the

index lincreases, the oscillation of ulintensiﬁes, which can also be understood as a gradual

increase in frequency in a sense.

Filtering is the modulation of the Fourier transform of a signal, that is,

fFT

−→ ˆ

−→ 





h1ˆ

hNˆ







IFT

−→ Fhf,

or equivalently Fh=Udiag(h)U>, where FT, IFT and M are the abbreviations of “Fourier

transform”, “Inverse Fourier Transform” and “Modulation”. The vector h:= (h1, ..., hN)>

used for frequency modulation is called the ﬁlter vector.

2.3 Downsampling and Uppersampling

Downsampling (or subsampling) is the process of reducing the sampling rate of a signal.

In the classical signal processing, it is usually done by keeping the ﬁrst sample and then

every other nth sample after the ﬁrst. In the well-known Mallat’s decomposition algorithm

in wavelet analysis, the signal is downsampled by n= 2. In the graph signal processing, a

downsampling operation can be deﬁned by choosing a subset V1⊂ V such that all samples

of signal fwhose indices are not in V1are discarded [21]. That is,

AV1: (f1, ..., fN)>7→ (fi1, ..., fim)>,(2.3)

where V1={vi1, ..., vim}is the downsampled subset and AV1is the corresponding down-

sampler. One can choose diﬀerent subsets to deﬁne downsamplers according to diﬀerent

applications [32, 20, 38, 39].

To reconstruct the signal one needs to upsample the downsampled signal by inserting

zeros to increase the sampling rate. This upsampler can be described as

BV1: (fi1, ..., fim)>7→ (˜

f1, ..., ˜

fN)>,where ˜

fj:= (fjj∈ V1={i1, ..., im},

0 otherwise .(2.4)

Then the overall downsampling then upsampling operation can be illustrated by

f→AV1f→BV1AV1f.

It is easy to verify that

V1=BV1= [ei1,··· ,eim]∈RN×m

and BV1AV1is a diagonal matrix whose ith diagonal entry is 1 if vi∈ V1and 0 otherwise,

i.e.,

BV1AV1=1

2(IN+J),(2.5)

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

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

10 玖币 0人已下载

立即下载

摘要：

PerfectReconstructionTwo-ChannelFilterBanksonArbitraryGraphs*JunxiaYouandLihuaYangSchoolofMathematics,SunYat-senUniversity,Guangzhou,ChinaGuangdongProvinceKeyLaboratoryofComputationalScienceMarch1,2025AbstractThispaperextendstheexistingtheoryofperfectreconstructiontwo-channellterbanksfrombipartite...

展开>> 收起<<

Perfect Reconstruction Two-Channel Filter Banks on Arbitrary Graphs Junxia You and Lihua Yang.pdf

共33页,预览5页

还剩页未读，继续阅读

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

Perfect Reconstruction Two-Channel Filter Banks on Arbitrary Graphs Junxia You and Lihua Yang

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: