圖形信號處理領域之圖形分析與濾波器組設計

Graph Analysis and Filter Bank Designs in Graph Signal Processing

盧文揚(Wen-Yang Lu)

指導教授 ： 貝蘇章

國立臺灣大學/電機資訊學院/電信工程學研究所/碩士(2018年)

https://doi.org/10.6342/NTU201800910

摘要

圖形信號處理是一塊新興領域。近年來，此領域吸引了越來越多的學者關注，因為它能夠用來分析真實世界中不規則架構上的資料。圖形信號處理技術能應用至多項領域，例如社群、運輸、神經網路。有了圖形傅立葉轉換的定義後，圖形信號的頻譜分析得以被實現。許多的研究致力於將傳統信號處理的觀念應用至這塊新興領域。
在本篇論文，我們首先會介紹圖形信號處理的基本觀念。接著，我們將依序展現目前在這塊領域的研究成果。我們分析了圖形結構與圖形特徵值之間的關聯。我們研究了圖形信號的頻譜混疊現象，並提出了一個發生在節點域上的類似現象，稱作節點混疊。我們還提出了一些圖形轉換以及圖形拆解的技術。此外，我們介紹了圖形濾波器的觀念，並提出了一個新的圖形濾波器組設計。對於原本的圖形和圖形信號，我們所提出的設計能夠提供精簡版本的圖形以及圖形信號。我們也提出了一個概念:所有的IIR圖形濾波器，皆能夠在一個給定的圖形上，找到等價的FIR圖形濾波器。我們提出了兩個方法來找出此等價FIR濾波器。最後，我們介紹了三個疊代式演算法，用於重建有限頻寬圖形信號。我們提出了將這些疊代式演算法轉換成非疊代式，並且用多項式圖形濾波器來實現。

關鍵字

圖形信號處理 ； 精簡化 ； 重建 ； 圖形轉換與拆解 ； 濾波器組 ； 混疊現象 ； 多項式濾波器

並列摘要

Signal processing on graphs is an emerging field that has attracted more and more attention. It is capable of analyzing many kinds of real-world data defined on an irregular structure. The techniques of graph signal processing are applicable to many fields, such as social community, transportation, neural network, etc. With the definition of the graph Fourier transform, the spectral analysis of graph signals is available. A lot of work has been devoted to apply the concepts of classical signal processing to this emerging field.
In this thesis, we will start from introducing the basic concepts of graph signal processing. Then, our current work in the field of graph signal processing is presented. We analyze the relation between graph topologies and graph eigenvalues. We investigate the spectral folding (aliasing) phenomenon for graph signals, and propose a similar phenomenon in the vertex-domain, called vertex folding phenomenon. We propose several graph transformations as well as decompositions. Besides, we introduce the concepts of graph filters, and propose a new design of graph filter banks that can provide a coarse version of original graphs and signals. We also propose the concept that all IIR graph filters can find their equivalent FIR graph filters on a given graph. Two methods are proposed to find the equivalent FIR graph filters. Lastly, three iterative reconstruction algorithms for bandlimited graph signals are introduced, and we propose to convert these iterative algorithms to non-iterative algorithms, which are implemented by polynomial graph filters.

並列關鍵字

Graph signal processing ； coarsening ； reconstruction ； graph transformations and decompositions ； filter banks ； aliasing phenomenon ； polynomial graph filters

參考文獻

[1] 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 Process. Mag., vol. 30, no. 3, pp. 83–98, May 2013.

[2] S. K. Narang and A. Ortega, “Perfect reconstruction two-channel wavelet filter banks for graph structured data,” IEEE Trans. Signal Process., vol. 60, no. 6, pp. 2786–2799, June 2012.

[3] O. Teke and P. P. Vaidyanathan, “Fundamentals of multirate graph signal processing,” in Proc. 49th Asilomar Conf. Signals, Syst. Comput., Pacific Grove, CA, USA, Nov. 2015, pp. 1791–1795.

[4] O. Teke and P. P. Vaidyanathan, “Graph filter banks with M-channels, maximal decimation, and perfect reconstruction,” in Proc. IEEE Int. Conf. Acoust., Speech Signal Process., Shanghai, China, Mar. 2016, pp. 4089–4093.

[5] O. Teke and P. P. Vaidyanathan, “Extending classical multirate signal processing theory to graphs—Part I: Fundamentals,” IEEE Trans. Signal Process., vol. 65, no. 2, pp. 409–422, Jan. 2017.