|
|
基于傅里叶相似变换的图距离矩阵分解研究
|
Abstract:
本文考虑图距离矩阵的分解问题。给定一个图，根据其顶点集的划分，我们定义了图距离矩阵的傅里叶相似变换。该变换由用于执行离散傅里叶变换的矩阵乘以图距离矩阵实现。我们证明了图距离矩阵在傅里叶相似变换下能够分解成多个较小矩阵的直和，当且仅当该图的顶点划分是距离公平划分。
This paper considers the problem of decomposition of graph distance matrix. Given a graph, we define a Fourier similarity transform of its graph distance matrix based on the vertex partition, which is implemented by multiplying the matrices used to perform the Discrete Fourier transformation. We show that graph distance matrices can be decomposed into many smaller matrices under Fourier similarity transformation, if and only if the vertex partition of the graph is a distance equitable partition.
| [1] | Petrou, M. and Petrou, C. (2010). Image Processing: The Fundamentals. John Wiley & Sons. https://doi.org/10.1002/9781119994398 |
| [2] | Wedeen, V.J., Hagmann, P., Tseng, W.I., Reese, T.G. and Weisskoff, R.M. (2005) Mapping Complex Tissue Architecture with Diffusion Spectrum Magnetic Resonance Imaging. Magnetic Resonance in Medicine, 54, 1377-1386. https://doi.org/10.1002/mrm.20642 |
| [3] | Cooley, J.W. and Tukey, J.W. (1965) An Algorithm for the Machine Calculation of Complex Fourier Series. Mathematics of Computation, 19, 297-301. https://doi.org/10.1090/s0025-5718-1965-0178586-1 |
| [4] | Winograd, S. (1976) On Computing the Discrete Fourier Transform. Proceedings of the National Academy of Sciences, 73, 1005-1006. https://doi.org/10.1073/pnas.73.4.1005 |
| [5] | Ortega, A., Frossard, P., Kovačević, J., Moura, J.M.F. and Vandergheynst, P. (2018) Graph Signal Processing: Overview, Challenges, and Applications. Proceedings of the IEEE, 106, 808-828. https://doi.org/10.1109/jproc.2018.2820126 |
| [6] | Haemers, W.H. (1995) Interlacing Eigenvalues and Graphs. Linear Algebra and Its Applications, 226, 593-616. https://doi.org/10.1016/0024-3795(95)00199-2 |
| [7] | Lund, D., Drapeau, J. and Webb, B. (2021) Fourier Decompositions of Graphs with Symmetries and Equitable Partiti. Linear Algebra and Its Applications, 627, 199-226. https://doi.org/10.1016/j.laa.2021.05.019 |
