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

Abstract

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