請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/20081完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 貝蘇章(Soo-Chang Pei) | |
| dc.contributor.author | Wen-Yang Lu | en |
| dc.contributor.author | 盧文揚 | zh_TW |
| dc.date.accessioned | 2021-06-08T02:39:46Z | - |
| dc.date.copyright | 2018-06-21 | |
| dc.date.issued | 2018 | |
| dc.date.submitted | 2018-06-11 | |
| dc.identifier.citation | [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. [6] O. Teke and P. P. Vaidyanathan, “Extending classical multirate signal processing theory to graphs—Part II: M-channel filter banks,” IEEE Trans. Signal Process., vol. 65, no. 2, pp. 423–437, Jan. 2017. [7] G. E. Trapp, “Inverses of circulant matrices and block circulant matrices,” Kyungpook Math J., vol. 13, no. 1, pp. 11–20, June 1973. [8] A. Sandryhaila and J. M. F. Moura, “Discrete signal processing on graphs: Graph filters,” in Proc. IEEE Int. Conf. Acoust., Speech Signal Process., Vancouver, BC, Canada, May 2013, pp. 6163–6166. [9] A. Sandryhaila and J. M. F. Moura, “Discrete signal processing on graphs,” IEEE Trans. Signal Process., vol. 61, no. 7, pp. 1644–1656, Apr. 2013. [10] A. Sandryhaila and J. M. F. Moura, “Discrete signal processing on graphs: Graph Fourier transform,” in Proc. IEEE Int. Conf. Acoust., Speech Signal Process., Vancouver, BC, Canada, May. 2013, pp. 6167–6170. [11] A. Sandryhaila and J. M. F. Moura, “Discrete signal processing on graphs: frequency analysis,” IEEE Trans. Signal Process., vol. 62, no. 12, pp. 3042–3054, June 2014. [12] D. I. Shuman, P. Vandergheynst, and P. Frossard, “Chebyshev polynomial approximation for distributed signal processing,” in Proc. Int. Conf. Distributed Computing in Sensor Systems and Workshops, Barcelona, Spain, June 2011, pp. 1–8. [13] S. K. Narang and A. Ortega, “Compact support biorthogonal wavelet filter banks for arbitrary undirected graphs,” IEEE Trans. Signal Process., vol. 61, no. 19, pp. 4673–2799, Oct. 2013. [14] A. Saikiyama and Y. Tanaka, “Oversampled graph laplacian matrix for graph signals,” in Proc. 22nd Eur. Signal Process. Conf., Lisbon, Portugal, Sep. 2014, pp. 2225–2229. [15] Y. Tanaka and A. Sakiyama, “M-channel oversampled perfect reconstruction filter banks for graph signals,” in Proc. IEEE Int. Conf. Acoust., Speech Signal Process., Florence, Italy, May 2014, pp. 2604–2608. [16] V. N. Ekambaram, G. Fanti, B. Ayazifar, and K. Ramchandran, “Splinelike wavelet filterbanks for multiresolution analysis of graph-structured data,” IEEE Trans. Signal Inf. Process. Netw., vol. 1, no. 4, pp. 268–278, Dec. 2015. [17] H. Q. Nguyen and M. N. Do, “Downsampling of signals on graphs via maximum spanning trees,” IEEE Trans. Signal Process., vol. 63, no. 1, pp. 182–191, Jan. 2015. [18] N. Tremblay and P. Borgnat, “Joint filtering of graph and graph signals,” in Proc. 49th Asilomar Conf. Signals, Syst. Comput., Pacific Grove, CA, USA, Nov. 2015, pp. 1824–1828. [19] N. Tremblay and P. Borgnat, “Subgraph-based filterbanks for graph signals,” IEEE Trans. Signal Process., vol. 64, no. 15, pp. 3827–3840, Aug. 2016. [20] D. I. Shuman, C. Wiesmeyr, N. Holighaus, and P. Vandergheynst, “Spectrum-adapted tight graph wavelet and vertex-frequency frames,” IEEE Trans. Signal Process., vol. 63, no. 16, pp. 4223–4235, Aug. 2015. [21] H. Behjat, U. Richter, D. Van De Ville, and L. Sornmo, “Signal-adapted tight frames on graphs,” IEEE Trans. Signal Process., vol. 64, no. 22, pp. 6017–6029, Nov. 2016. [22] S. Chen, A. Sandryhaila, and J. Kovačević, “Sampling theory for graph signals,” in Proc. IEEE Int. Conf. Acoust., Speech Signal Process., South Brisbane, Australia, Apr. 2015, pp. 3392–3396. [23] S. Chen, R. Varma, A. Sandryhaila, and J. Kovačević, “Discrete signal processing on graphs: Sampling theory,” IEEE Trans. Signal Process., vol. 63, no. 24, pp. 6510–6523, Dec. 2015. [24] Y. Jin and D. I. Shuman, “An M-channel critically sampled filter bank for graph signals,” in Proc. IEEE Int. Conf. Acoust., Speech Signal Process., Jan. 2017, pp. 3909–3913. [25] D. I. Shuman, M. J. Faraji, and P. Vandergheynst, “A multiscale pyramid transform for graph signals,” IEEE Trans. Signal Process., vol. 64, no. 8, pp. 2119–2134, Apr. 2016. [26] A. G. Marques, S. Segarra, G. Leus, and A. Ribeiro, “Sampling of graph signals with successive local aggregations,” IEEE Trans. Signal Process., vol. 64, no. 7, pp. 1832–1843, Apr. 2016. [27] P. Liu, X. Wang, and Y. Gu, “Coarsening graph signal with spectral invariance,” in Proc. IEEE Int. Conf. Acoust. Speech Signal Process., Florence, Italy, May 2014, pp. 1070–1074. [28] G. Karypis and V. Kumar, “A fast and high quality multilevel scheme for partitioning irregular graphs,” SIAM J. Sci. Comput., vol. 20, no. 1, pp. 359–392, Aug. 1998. [29] I. Safro, P. Sanders, and C. Schulz, “Advanced coarsening schemes for graph partitioning,” J. Exp. Algorithmics, vol. 19, 2014, Art. no. 2.2. [30] S. Lafon and A. B. Lee, “Diffusion maps and coarse-graining: a unified framework for dimensionality reduction, graph partitioning, and data set parameterization,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 28, no. 9, pp. 1393–1403, Sep. 2006. [31] D. Ron, I. Safro, and A. Brandt, “Relaxation-based coarsening and multiscale graph organization,” SIAM Multiscale Model. Simul., vol. 9, no. 1, pp. 407–423, Mar. 2011. [32] D. Gfeller and P. De Los Rios, “Spectral coarse graining of complex networks,” APS Phys. Rev. Lett., vol. 99, no. 3, Jul. 2007, Art. no. 038701. [33] P. Erdös and A. Rényi, “On random graphs I,” Publ. Math. (Debrecen), vol. 6, pp. 290–297, 1959. [34] P. Nathanaël et al., “GSPBOX: A toolbox for signal processing on graphs,” arXiv:1408.5781v2, Mar. 2016. [35] S. K. Narang and A. Ortega, “Local two-channel critically sampled filter-banks on graphs,” in Proc. IEEE 17th Int. Conf. Image Processing, Hong Kong, Sept. 2010, pp. 333–336. [36] D. B. H. Tay and Z. Lin, “Design of near orthogonal graph filter banks,” IEEE Signal Process. Lett., vol. 22, no. 6, pp. 701–704, June 2015. [37] D. B. H. Tay and Z. Lin, “Techniques for constructing biorthogonal bipartite graph filter banks,” IEEE Trans. Signal Process., vol. 63, no. 21, pp. 5772–5783, Nov. 2015. [38] V. N. Ekambaram, G. Fanti, B. Ayazifar, and K. Ramchandran, “Critically-sampled perfect-reconstruction spline-wavelet filterbanks for graph signals,” in IEEE Global Conf. Signal Inform. Process., Dec. 2013, pp. 475–478. [39] F. Harary, D. Hsu, and Z. Miller, “The biparticity of a graph,” Journal of Graph Theory, vol. 1, no. 2, pp. 131–133, 1977. [40] J. Zeng, G. Cheung and A. Ortega “Bipartite subgraph decomposition for critically sampled wavelet filterbanks on arbitrary graphs,” in Proc. IEEE Int. Conf. Acoust. Speech Signal Process., Shanghai, Mar. 2016, pp. 6210–6214. [41] S. C. Pei, W. Y. Lu, and B. Y. Guo, “M-channel perfect recovery of coarsened graphs and graph signals with spectral invariance and topological preservation,” IEEE Trans. Signal Process., vol. 65, no. 19, pp. 5164–5178, Oct. 2017. [42] A. Sandryhaila, S. Kar, and J. M. F. Moura, “Finite-time distributed consensus through graph filters,” in Proc. IEEE Int. Conf. Acoust., Speech Signal Process., Florence, Italy, May 2014, pp. 1080–1084. [43] S. Safavi and U. A. Khan, “Revisiting finite-time distributed algorithms via successive nulling of eigenvalues,” IEEE Signal Process. Lett., vol. 22, no. 1, pp. 54–57, Jan. 2015. [44] S. Segarra, A. G. Marques, and A. Ribeiro, “Distributed implementation of linear network operators using graph filters,” in Proc. 53rd Annu. Allerton Conf. Communication, Control and Computing, Sept. 2015, pp. 1406–1413. [45] A. Loukas, A. Simonetto, and G. Leus, “Distributed autoregressive moving average graph filters,” IEEE Signal Process. Lett., vol. 22, no. 11, pp. 1931–1935, Nov. 2015. [46] E. Isufi, A. Loukas, A. Simonetto, and G. Leus, “Autoregressive moving average graph filtering,” IEEE Trans. Signal Process., vol. 65, no. 2, pp. 274–288, Jan. 2017. [47] E. Isufi, A. Loukas, and G. Leus, “Autoregressive moving average graph filters a stable distributed implementation,” in Proc. IEEE Int. Conf. Acoust., Speech Signal Process., New Orleans, LA, USA, Mar. 2017, pp. 4119–4123. [48] X. Shi, H. Feng, M. Zhai, T. Yang and B. Hu, “Infinite impulse response graph filters in wireless sensor networks,” IEEE Signal Process. Lett., vol. 22, no. 8, pp. 1113–1117, Aug. 2015. [49] H. P. Decell, “An application of the Cayley–Hamilton theorem to generalized matrix inversion,” SIAM Rev., vol. 7, no. 4, pp. 526–528, Oct. 1965. [50] P. A. Regalia, S. K. Mitra, and P. P. Vaidyanathan, “The digital all-pass filter: A versatile signal processing building block,” Proc. IEEE, vol. 76, no. 1, pp. 19–37, Jan. 1988. [51] S. C. Pei, W. Y. Lu, and B. Y. Guo, “Pole–zero assignment of all-pass-based notch filters,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 64, no. 4, pp. 477–481, Apr. 2017. [52] M. Tsitsvero, S. Barbarossa, P. Di Lorenzo, “Signals on graphs: Uncertainty principle and sampling,” IEEE Trans. Signal Process., vol. 64, no. 18, pp. 4845–4860, Sept. 2016. [53] S. Segarra, A. G. Marques, G. Leus, and A. Ribeiro, “Reconstruction of graph signals through percolation from seeding nodes,” IEEE Trans. Signal Process., vol. 64, no. 16, pp. 4363–4378, Aug. 2016. [54] S. K. Narang, A. Gadde, and A. Ortega, “Signal processing techniques for interpolation in graph structured data,” in Proc. IEEE Int. Conf. Acoust., Speech Signal Process., Vancouver, May 2013, pp. 5445–5449. [55] X. Wang, P. Liu, and Y. Gu, “Local-set-based graph signal reconstruction,” IEEE Trans. Signal Process., vol. 63, no. 9, pp. 2432–2444, Mar. 2015. [56] M. Sabri, W. Steenaart, “An approach to band-limited signal extrapolation: The extrapolation matrix,” IEEE Trans. Circuits Syst., vol. 25, no. 2, pp. 74–78, Feb. 1978. [57] A. Papoulis, “A new algorithm in spectral analysis and band-limited extrapolation,” IEEE Trans. Circuits Syst., vol. 22, no. 9, pp. 735–742, Sept. 1975. [58] C. Lanczos, “An iteration method for the solution of the eigenvalue problem of linear differential and integral operators,” J. Res. Nat’l Bur. Std., vol. 45, no. 4, pp. 255–282, Oct. 1950. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/20081 | - |
| dc.description.abstract | 圖形信號處理是一塊新興領域。近年來，此領域吸引了越來越多的學者關注，因為它能夠用來分析真實世界中不規則架構上的資料。圖形信號處理技術能應用至多項領域，例如社群、運輸、神經網路。有了圖形傅立葉轉換的定義後，圖形信號的頻譜分析得以被實現。許多的研究致力於將傳統信號處理的觀念應用至這塊新興領域。
在本篇論文，我們首先會介紹圖形信號處理的基本觀念。接著，我們將依序展現目前在這塊領域的研究成果。我們分析了圖形結構與圖形特徵值之間的關聯。我們研究了圖形信號的頻譜混疊現象，並提出了一個發生在節點域上的類似現象，稱作節點混疊。我們還提出了一些圖形轉換以及圖形拆解的技術。此外，我們介紹了圖形濾波器的觀念，並提出了一個新的圖形濾波器組設計。對於原本的圖形和圖形信號，我們所提出的設計能夠提供精簡版本的圖形以及圖形信號。我們也提出了一個概念:所有的IIR圖形濾波器，皆能夠在一個給定的圖形上，找到等價的FIR圖形濾波器。我們提出了兩個方法來找出此等價FIR濾波器。最後，我們介紹了三個疊代式演算法，用於重建有限頻寬圖形信號。我們提出了將這些疊代式演算法轉換成非疊代式，並且用多項式圖形濾波器來實現。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-08T02:39:46Z (GMT). No. of bitstreams: 1 ntu-107-R05942053-1.pdf: 4558328 bytes, checksum: ec137d5c5adfe4a053f3b5a58c9f6a73 (MD5) Previous issue date: 2018 | en |
| dc.description.tableofcontents | 口試委員審定書 i
誌謝 ii 摘要 iii Abstract iv Contents v List of Figures x List of Tables ....xvi Chapter 1 Introduction 1 1.1 Graph Signal Processing 1 1.1.1 Laplacian Matrix 1 1.1.2 Eigenvalue Decomposition of Laplacian Matrix 2 1.1.3 Graph Signal and Graph Fourier Transform 3 1.1.4 Bandlimited Signals 3 1.2 The Goal of the Study 4 Chapter 2 Graph Analysis 6 2.1 Relation Between the Maximum Eigenvalue and Graphs 6 2.2 Eigenvalues of Path Graphs 35 Chapter 5 Generalized Operators for Graph Signals 36 3.1 Convolution of Graph Signals 36 3.2 Translation of Graph Signals 36 3.3 Our Proposed Definition of Translation 37 Chapter 6 Spectral Folding Phenomenon and Vertex Folding Phenomenon 41 4.1 Spectral Folding Phenomenon for Block Cyclic Graphs 42 4.2 Vertex Folding Phenomenon for Block Circulant Graphs 45 Chapter 7 Graph Transformation and Decomposition 49 5.1 Graph Transformation 49 5.1.1 Topology Transformation with Same Dimension 49 5.1.2 Topology Transformation with Different Dimension 50 5.1.3 Similarity transformation of M-Block Cyclic Graphs 51 5.2 Decomposition into Two Hermitian Graphs 52 5.3 Decomposition into a Pair of Even and Odd Graphs 54 5.4 Decomposition of Complement Graphs 58 5.5 Phase Rotation between the Pair of Even and Odd Graphs 60 Chapter 8 Design of Graph Filters 62 6.1 Notion of Graph Filters 62 6.2 Eigenvalue Mapping 63 6.3 Design of Linear Phase Filters on Graphs 65 Chapter 9 M-Channel Perfect Recovery of Coarsened Graphs and Graph Signals with Spectral Invariance and Topological Preservation 66 7.1 Introduction 67 7.2 Coarsening of Graph and Graph Signals 69 7.3 M-channel Perfect Recovery Filter Bank 73 7.3.1 Partitioning Spectral Information into the M Channels 74 7.3.2 Constructing M-channel Coarsened Graphs and Coarsened Signals 78 7.3.3 Perfect Signal Reconstruction 80 7.3.4 Perfect Graph Reconstruction 83 7.3.5 Influence of Eliminating Coarsened Graphs’ Negative Weight Edges 85 7.3.6 Toy Graph Example 87 7.4 Relation to the Existing Recovery Method Based on Sampling Theory 93 7.4.1 Downsampling and Recovering the Signals 93 7.4.2 Downsampling and Recovering the Graphs 95 7.4.3 Comparison 97 7.5 Experiments 99 7.5.1 ER Random Graphs 100 7.5.2 Minnesota Traffic Graphs 102 Chapter 10 Two-channel Perfect Reconstruction Filter Banks with Arbitrary Sampling Set for General Graph Using Spectral Invariant Similarity Transform 106 8.1 Introduction 107 8.2 Bipartite Graph 109 8.3 Spectral Invariant Similarity Transform 111 8.4 Two-channel Wavelet Filter Banks for Bipartite Graph 112 8.5 Two-channel Wavelet Filter Banks for General Graph 118 8.5.1 Trick of Similarity Transform 118 8.5.2 Construction of Bipartite Graphs According to Sampling Sets 119 8.5.3 Proposed Construction of Path-like Bipartite Graphs 121 8.6 Experiment 125 8.6.1 Graph Filter Bank Designs with Equal Size of Sampling Sets 126 8.6.2 Graph Filter Bank Designs with Unequal Size of Sampling Sets 129 8.6.3 Application on Real Images 130 Chapter 11 Non-recursive FIR Implementation of IIR Graph Filters Using Extended Euclidean and Polynomial Regression 132 9.1 Introduction 132 9.2 Polynomial Graph Filters 135 9.3 Existing Implementation Algorithms of IIR Graph Filters 137 9.4 Convert IIR Graph Filters to FIR Graph Filters 140 9.4.1 Polynomial Regression Method 140 9.4.2 Extended Euclidean Method 144 9.5 Experiment 147 9.5.1 Polynomial Regression Method for All-pole Graph Filter 147 9.5.2 Polynomial Regression Method for Graph Notch Filter 150 9.5.3 Extended Euclidean Method for IIR Low-pass Graph Filter 153 Chapter 12 Non-iterative Graph Signal Reconstruction Using Polynomial Graph Filters 155 10.1 Introduction 155 10.2 Band-limiting Operator and Vertex-limiting Operator 156 10.3 Existing Iterative Reconstruction Algorithms 158 10.3.1 Iterative Least Square Reconstruction (ILSR) 158 10.3.2 Iterative Weighting Reconstruction (IWR) 158 10.3.3 Iterative Propagating Reconstruction (IPR) 159 10.4 Conversion from Iterative to Non-iterative Schemes 160 10.5 Non-iterative Reconstruction Algorithms 162 10.5.1 Non-iterative Least Square Reconstruction (NLSR) 162 10.5.2 Non-iterative Weighting Reconstruction (NWR) 163 10.5.3 Non-iterative Propagating Reconstruction (NPR) 164 10.5.4 Reconstruction via Polynomial Graph Filters 164 10.6 Condition for Perfect Reconstruction 165 10.7 Experiment 166 10.7.1 Minnesota Traffic Graph 166 10.7.2 GSP Logo Graph 167 Reference 169 | |
| dc.language.iso | zh-TW | |
| dc.title | 圖形信號處理領域之圖形分析與濾波器組設計 | zh_TW |
| dc.title | Graph Analysis and Filter Bank Designs in Graph Signal Processing | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 106-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 曾建誠,丁建均 | |
| dc.subject.keyword | 圖形信號處理,精簡化,重建,圖形轉換與拆解,濾波器組,混疊現象,多項式濾波器, | zh_TW |
| dc.subject.keyword | Graph signal processing,coarsening,reconstruction,graph transformations and decompositions,filter banks,aliasing phenomenon,polynomial graph filters, | en |
| dc.relation.page | 176 | |
| dc.identifier.doi | 10.6342/NTU201800910 | |
| dc.rights.note | 未授權 | |
| dc.date.accepted | 2018-06-12 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電信工程學研究所 | zh_TW |
| 顯示於系所單位： | 電信工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-107-1.pdf 目前未授權公開取用 | 4.45 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。