>[!info] >The **GFT** $\tilde{\mathbf{x}}$ of the [[Graph Signal|signal]] $\mathbf{x}$ is defined as $\mathbf{x}=\mathbf{U}\tilde{\mathbf{x}}, \quad \tilde{\mathbf{x}}=\mathbf{U}^{-1}\mathbf{x},$where the [[Matrices|matrix]] $\mathbf{U}$ is computed from the [[Eigenvalue Problem|eigenvalue decomposition]] $\mathbf{Z}=\mathbf{U \Lambda U}^{-1}$ of the used [[Graph Operator|graph operator]] $\mathbf{Z}$. This basic definition therefore assumes the operator to be diagonalizable. For defective operators there are two possible choices - **[[Schur Normal Form|Schur Decomposition]]** - The **GFT** $\breve{\mathbf{x}}$ of the [[Graph Signal|signal]] $\mathbf{x}$ is computed via $\mathbf{x}=\mathbf{U}\breve{\mathbf{x}}, \quad \breve{\mathbf{x}}=\mathbf{U}^{H}\mathbf{x},$where $\mathbf{Z}=\mathbf{U T U}^{H}$ ($\mathbf{T}$ is upper triangular matrix). - **Jordan Canonical Form** - The **GFT** $\tilde{\mathbf{x}}$ of the [[Graph Signal|signal]] $\mathbf{x}$ is computed via $\mathbf{x}=\mathbf{V}\tilde{\mathbf{x}}, \quad \tilde{\mathbf{x}}=\mathbf{V}^{-1}\mathbf{x},$where $\mathbf{Z}=\mathbf{V \Lambda V}^{H}$ ($\mathbf{\Lambda}$ is block diagonal matrix). --- #### Remarks - GFT depends on $\mathbf{Z}$ and therefore the [[Graph|graphs]] topology. - Only unique if all eigenvalues have multiplicity 1. - In an [[Graph|undirected graph]], $\mathbf{U}$ is orthogonal ($\mathbf{UU}^T=1$), which means the inversion can be replaced by a transposition. - Computational cost can be reduced by using [[Approximating Graphs - Sparsification and Reduction|graph sparsification techniques]] or by using [[Givens Rotation|givens rotations]] to approximate $\mathbf{U}$.