Analyzing the Approximation Error of the Fast Graph Fourier Transform

被引：0

作者：

Le Magoarou, Luc ^{[1
]}

Tremblay, Nicolas ^{[2
]}

Gribonval, Remi ^{[3
]}

机构：

[1] B Com, Rennes, France

[2] Univ Grenoble Alpes, CNRS, GIPSA Lab, Grenoble, France

[3] INRIA Rennes Bretagne Atlantique, Rennes, France

来源：

2017 FIFTY-FIRST ASILOMAR CONFERENCE ON SIGNALS, SYSTEMS, AND COMPUTERS | 2017年

关键词：

COMPUTATION;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The graph Fourier transform (GFT) is in general dense and requires O(n(2)) time to compute and O(n(2)) memory space to store. In this paper, we pursue our previous work on the approximate fast graph Fourier transform (FGFT). The FGFT is computed via a truncated Jacobi algorithm, and is defined as the product of J Givens rotations (very sparse orthogonal matrices). The truncation parameter, J, represents a trade-off between precision of the transform and time of computation (and storage space). We explore further this trade-off and study, on different types of graphs, how is the approximation error distributed along the spectrum.

引用

页码：45 / 49

页数：5

共 50 条

[21] 2D fast Fourier transform analytical solutions in all space for all gravity and magnetic components
Boulanger, Olivier
[J]. GEOPHYSICAL PROSPECTING, 2024, 72 (02) : 809 - 832
[22] Modeling solution X-ray scattering of biomacromolecules using an explicit solvent model and the fast Fourier transform
Tong, Dudu
Yang, Jianbin
Lu, Lanyuan
[J]. JOURNAL OF APPLIED CRYSTALLOGRAPHY, 2015, 48 : 1834 - 1842
[23] A Graph Repository for Learning Error-Tolerant Graph Matching
Francisco Moreno-Garcia, Carlos
Cortes, Xavier
Serratosa, Francesc
[J]. STRUCTURAL, SYNTACTIC, AND STATISTICAL PATTERN RECOGNITION, S+SSPR 2016, 2016, 10029 : 519 - 529
[24] An Approximation Method for Large Graph Similarity
Zhao, Danfeng
Huang, Zhou
Zhou, Feng
Liotta, Antonio
Huang, Dongmei
[J]. 2020 IEEE INTERNATIONAL CONFERENCE ON BIG DATA (BIG DATA), 2020, : 4828 - 4835
[25] Fast and effective implementation of discrete quantum Fourier transform via virtual-photon-induced process in separate cavities
Wang, Hong-Fu
Zhang, Shou
Zhu, Ai-Dong
Yeon, Kyu-Hwang
[J]. JOURNAL OF THE OPTICAL SOCIETY OF AMERICA B-OPTICAL PHYSICS, 2012, 29 (05) : 1078 - 1084
[26] Explicit solution for Nonuniform Discrete Fourier Transform
Shen, Yi
Zhu, Chunhui
Liu, Lijun
Wang, Qiang
Jin, Jing
Lin, Yurong
[J]. 2010 IEEE INTERNATIONAL INSTRUMENTATION AND MEASUREMENT TECHNOLOGY CONFERENCE I2MTC 2010, PROCEEDINGS, 2010,
[27] SPARSE FOURIER TRANSFORM VIA BUTTERFLY ALGORITHM
Ying, Lexing
[J]. SIAM JOURNAL ON SCIENTIFIC COMPUTING, 2009, 31 (03) : 1678 - 1694
[28] Sampling Theorem and Discrete Fourier Transform on the Hyperboloid
Calixto, M.
Guerrero, J.
Sanchez-Monreal, J. C.
[J]. JOURNAL OF FOURIER ANALYSIS AND APPLICATIONS, 2011, 17 (02) : 240 - 264
[29] Error bounds for approximation in Chebyshev points
Xiang, Shuhuang
Chen, Xiaojun
Wang, Haiyong
[J]. NUMERISCHE MATHEMATIK, 2010, 116 (03) : 463 - 491
[30] MULTISCALE DISCRETE APPROXIMATION OF FOURIER INTEGRAL OPERATORS
Andersson, Fredrik
de Hoop, Maarten V.
Wendt, Herwig
[J]. MULTISCALE MODELING & SIMULATION, 2012, 10 (01) : 111 - 145

← 1 2 3 4 5 →