bandlimited convergent graph signals converge in the fourier domain

[[concept]]

Theorem

Let $(W, X)$ be $c$ -bandlimited and $(G_{n}, X_{n})$ a sequence converging to $(W, X)$ . Then the GFT $({\hat{x}}_{n})_{i}$ converges to the WFT ${\hat{x}}_{i}$

Proof

Let $C$ be the set of eigenvalues in the $c$ -bandlimited set. Then for all $i \in C$ , we have

\begin{aligned} | ({\hat{x}}_{n})_{i} - {\hat{x}}_{i} | & = | ⟨ X_{n}, φ_{i}^{(n)} ⟩ - ⟨ X, φ_{i} ⟩ | \\ = | ⟨ X_{n}, φ_{i}^{(n)} ⟩ + ⟨ X, φ_{i}^{(n)} ⟩ - ⟨ X, φ_{i}^{n} ⟩ - ⟨ X, φ_{i} ⟩ | \\ \leq | | X - X_{n} | | \cdot | | φ_{i}^{(n)} | | + | | X | | \cdot | | φ_{i}^{(n)} - φ_{i} | | \end{aligned}

By convergence of $X_{n}$ , for all $ϵ > 0$ , there exists some $n_{1}$ such that $| | X_{n} - X | | \leq \frac{ϵ}{2}$ for all $n > n_{1}$ .

And for $| | φ_{i}^{(n)} - φ_{i} | |$ , we have

| | φ_{i}^{(n)} - φ_{i} | | \leq \frac{π}{2} \frac{| | T_{W} - T_{W_{n}} | |}{d (λ_{i}, λ_{i}^{(n)})} \leq \frac{π}{2} \frac{| | T_{W} - T_{W_{n}} | |}{min_{i \in C} d (λ_{i}, λ_{i}^{(n)})}

And from $T_{W_{n}} \to T_{W}$ , for all $ϵ > 0$ , there is some $n_{2}$ such that $| | φ_{i}^{(n)} - φ_{i} | | \leq \frac{ϵ}{2}$ for all $n > n_{2}$

Thus, for any $ϵ$ and each $n > max {n_{1}, n_{2}}$ and for all $i \in C$ , we have

| ({\hat{x}}_{n})_{i} - {\hat{x}}_{i} | \leq | | X_{n} - X | | \cdot {| | φ_{i}^{(n)} | |}^{1} + | | X | | \cdot | | φ_{i}^{(n)} - φ_{i} | | \leq \frac{ϵ}{2} + | | X | | \frac{ϵ}{2 | | X | |} = ϵ

And for $i \notin C$ ,

⟨ φ_{i} (T_{W_{n}}), X_{n} ⟩ \to ⟨ Ψ, X ⟩ = 0

Where $Ψ \in⊥ span {φ_{i} : i \in C}$ (orthogonal complement) $◼$

Mentions

File
2025-04-02 lecture 17
2025-04-07 lecture 18
graph convolutions of bandlimited signals converge to the graphon convolution
lipschitz graph convolutions of graph signals converge to lipschitz graphon filters

const { dateTime } = await cJS()

return function View() {
	const file = dc.useCurrentFile();
	return <p class="dv-modified">Created {dateTime.getCreated(file)}     ֍     Last Modified {dateTime.getLastMod(file)}</p>
}