Since the vector representation \(\mathbf {x}=[x_1,...,x_\text{N}]^\text{T}\)  does not account explicitly for the network structure, GSP endows \(\mathcal {G}\)  with the graph-shift operator (GSO) \(\mathbf {S}\)  [1]}, [2]}. The shift \(\mathbf {S}\in \mathbb {R}^{\text{N}\times \text{N}}\)  is a matrix whose entry \(S_{ji}\)  can be non-zero only if \(i=j\)  or if \((i,j)\in \mathcal {E}\) . The sparsity pattern of the matrix \(\mathbf {S}\)  captures the local structure of \(\mathcal {G}\) , with no specific assumptions on the values of its non-zero entries.
The intuition behind \(\mathbf {S}\)  is to represent a linear transformation that can be computed locally at the nodes of the graph. More rigorously, if \(\mathbf {y}\)  is defined as \(\mathbf {y}=\mathbf {S}\mathbf {x}\) , then node \(i\)  can compute \(y_i\)  as linear combination of the signal values \(x_j\)  where \(j\in \mathcal {N}_i\) .
Typical choices for \(\mathbf {S}\)  are the adjacency matrix \(\mathbf {A}\)  [1]} and the graph Laplacian [4]}. We assume henceforth that \(\mathbf {S}\)  is diagonalizable, so that \(\mathbf {S}=\mathbf {V}\Lambda \mathbf {V}^{-1}\)  with \(\Lambda \in \mathbb {C}^{\text{N}\times \text{N}}\)  being diagonal.
In particular, \(\mathbf {S}\)  is guaranteed to be diagonalizable when it is normal, i.e., when it satisfies \(\mathbf {S}\mathbf {S}^\text{H}=\mathbf {S}^\text{H}\mathbf {S}\)  (this is one of the core assumptions in S:Recovery).
In that case, we have that \(\mathbf {V}\)  is unitary, which implies \(\mathbf {V}^{-1}=\mathbf {V}^\text{H}\) , and leads to the decomposition \(\mathbf {S}=\mathbf {V}\Lambda \mathbf {V}^\text{H}\) .
