## 6 Application II: Fast Filtering of Time-Vertex Signals
### Time-Vertex Filtering  
Fixing a point in time, each column of \(\mathbf{X}\) is a graph signal defined on \(G\). Let \(\mathbf{x}_{t_{j}}\in\mathbb{R}^{N\times 1}\) denote the \(j\)th column of \(\mathbf{X}\), \(j=1,\cdots,T\). Based on the graph structure of \(G\), we can perform high-dimensional graph signal processing tasks on \(\mathbf{x}_{t_{j}}\), such as filtering, denoising, inpainting, and compression [4]. In particular, for a filter \(g:\sigma(\mathbf{L}_{G})\to\mathbb{C}\) defined on the eigenvalues of \(\mathbf{L}_{G}\), the graph spectral filtering of \(\mathbf{x}_{t_{j}}\) can be computed as \(g(\mathbf{L}_{G})\mathbf{x}_{t_{j}}=\mathbf{U}_{G}\mathcal{G}(\Lambda_{G}) \mathbf{U}_{G}^{*}\mathbf{x}_{t_{j}}\), where \(\mathbf{U}_{G}^{*}\) is the conjugate transpose of \(\mathbf{U}_{G}\), and \(\mathbf{L}_{G}=\mathbf{U}_{G}\Lambda_{G}\mathbf{U}_{G}^{*}\) is the spectral decomposition of \(\mathbf{L}_{G}\). Conversely, focusing on one vertex of \(G\), the \(i\)th row of \(\mathbf{X}\) is a discrete time signal \(\mathbf{x}_{v_{i}}^{\top}\in\mathbb{R}^{1\times T}\), which indicates how the signal value changes over time on the \(i\)th vertex. We can compute the one-dimensional discrete Fourier transform (DFT) of \(\mathbf{x}_{v_{i}}^{\top}\) by \(\bar{\mathbf{x}}_{v_{i}}^{\top}=\mathbf{x}_{v_{i}}^{\top}\overline{\mathbf{U}} _{R}\), where \(\mathbf{U}_{R}\) is the normalized DFT matrix of size \(T\), and \(\overline{\mathbf{U}}_{R}\) is its complex conjugate. The DFT converts a signal from the time domain to the frequency domain, and allows for the amplification or attenuation of different frequency components of the signal. This process is referred to as frequency filtering in classical signal processing [4]. Frequency filtering of classical one-dimensional signals is equivalent to graph spectral filtering of graph signals on a ring graph [66] (Theorem 5.1). Let \(\mathbf{L}_{R}\) denote the graph Laplacian of a ring graph with \(T\) vertices. Its spectral decomposition gives \(\mathbf{L}_{R}=\mathbf{U}_{R}\Lambda_{R}\mathbf{U}_{R}^{*}\), where \(\mathbf{U}_{R}\) comprises the DFT basis vectors (normalized to have length 1), and the \(kth\) eigenvalue is given by \(\Lambda_{R}(k,k)=2-2\cos\frac{2\pi(k-1)}{k}\), for \(k=1,\cdots,T\). Figure 8: A time-vertex signal defined on a sensor graph \(G\) with \(N=64\) vertices and \(T=4\) observations, visualized on a multilayer graph structure. Each layer is a copy of \(G\) observed at one time point. The joint time-vertex Fourier transform of a time-varying graph signal \(\mathbf{X}\) is defined as the combination of a graph Fourier transform and a DFT [50]:  
\[\hat{\mathbf{X}}:=\mathbf{U}_{G}^{*}\mathbf{X}\overline{\mathbf{U}}_{R}.\]  
A joint time-vertex filter \(h:\sigma(\mathbf{L}_{G})\times\sigma(\mathbf{L}_{R})\rightarrow\mathbb{C}\) is defined for all combinations of \((\lambda_{G},\lambda_{R})\) where \(\lambda_{G}\) is an eigenvalue of \(\mathbf{L}_{G}\) and \(\lambda_{R}\) is an eigenvalue of \(\mathbf{L}_{R}\). The joint time-vertex filtering is defined accordingly as  
\[h(\mathbf{L}_{G},\mathbf{L}_{R})\mathbf{X}:=\mathbf{U}_{G}(\mathbf{H}\circ( \mathbf{U}_{G}^{*}\mathbf{X}\overline{\mathbf{U}}_{R}))\mathbf{U}_{R}^{\top}, \tag{11}\]  
where \(\mathbf{H}\in\mathbb{R}^{N\times T}\) has entries \(\mathbf{H}_{i,j}=h(\lambda_{G},\lambda_{R})\), and \(\circ\) denotes the entry-wise product of two matrices. Figure 9 shows two examples of time-vertex filters: an ideal lowpass filter  
\[h(\lambda_{G},\lambda_{R})=\leavevmode\hbox{\small 1 \kern-3.8 pt\
ormalsize 1}_{(\lambda_{G}<\frac{1}{2}\lambda_{G\max}\lambda_{R}<2)}, \tag{12}\]  
and a wave filter  
\[h(\lambda_{G},\lambda_{R})=5e^{-100\left|\arccos\left(\frac{2- \lambda_{R}}{2}\right)-\arccos\left(1-\frac{\lambda_{G}}{2\lambda_{G\max}} \right)\right|^{2}}, \tag{13}\]  
where \(\lambda_{G\max}\) is the largest eigenvalue of \(\mathbf{L}_{G}\). The eigenvalues of \(\mathbf{L}_{R}\) range from 0 to 4 regardless of the size of \(T\), so \(\frac{1}{2}\lambda_{R\max}=2\).