Convergence in the cut norm implies convergence in L2

[[concept]]

Theorem

Let $W : [0, 1]^{2} \to [- 1, 1]$ . Then

| | W | |_{2, 2} \overset{(1)}{\leq} \sqrt{4 \cdot | | W | |_{\infty \to 1}} \overset{(2)}{\leq} \sqrt{16 \cdot | | W | |_{◻}}

ie, cut norm convergence implies convergence in $L_{2}$

Proof of (2)

We first show inequality (2). Using the definition of the cut norm, we have

\begin{aligned} | | W | |_{◻} & = sup_{S, T \subseteq [0, 1]} | \int \int_{S \times T} W (u, v) d u d v | \\ = sup_{f, g : [0, 1] \to [0, 1]} | \int_{0}^{1} \int_{0}^{1} W (u, v) f (u) g (v) d u d v | \\ (*) & = sup_{f, g : [0, 1] \to [0, 1]} | ⟨ T_{W} f, g ⟩ | \end{aligned}

Since we are taking the supremum, it is equivalent to taking the supremum over all $L_{\infty}$ functions $f$ and $g$ .

To get $(*)$ , we notice that $\int_{0}^{1} W (u, v) f (u) d u$ is an integral linear operator with kernel $W$ . We denote this with $T_{W}$ so that

T_{W} f (v) = \int_{0}^{1} W (u, v) f (u) d u

or equivalently that $T_{W} f = \int_{0}^{1} W (u, \cdot) f (u) d u$
We can then see that the definition becomes the absolute value of the inner product of two $L_{\infty}$ functions.

Note that $| | W | |_{\infty \to 1}$ is an induced operator norm of the graphon mapping functions from $L_{\infty}$ to $L_{1}$ .

\begin{aligned} | | W | |_{\infty \to 1} & = sup_{- 1 \leq g \leq 1} | | T_{W} g | |_{1} \\ = sup_{- 1 \leq g \leq 1} \int | T_{W} g (x) | d x \\ = sup_{- 1 \leq f, g \leq 1} ⟨ T_{W} g, f ⟩ \end{aligned}

we omit the denominator in our usual definition of the operator norm since $g$ is bounded by $- 1$ and $1$ and $g \in L_{\infty}$
We can rewrite this using $f$ to match in the definition of the $L_{1}$ norm since we are taking the supremum
For more about $L_{p}$ spaces see wikipedia (hand wavy/cursory for this class on functional analysis details)

We can then rewrite this as

\begin{aligned} | | W | |_{\infty \to 1} & = sup_{- 1 \leq f, f^{'} \leq 1, - 1 \leq g, g^{'} \leq 1} ⟨ T_{W} (g - g^{'}), f - f^{'} ⟩ \\ (* *) & \leq sup_{- 1 \leq g, f \leq 1} ⟨ T_{W} g, f ⟩ - sup_{- 1 \leq g, f^{'} \leq 1} ⟨ T_{W} g, f^{'} ⟩ + sup_{- 1 \leq g^{'}, f \leq 1} ⟨ T_{W} g^{'}, f ⟩ - sup_{- 1 \leq g^{'}, f^{'} \leq 1} ⟨ T_{W} g^{'}, f^{'} ⟩ \\ (†) & \leq 4 | | W | |_{◻} \end{aligned}

Where we get $(* *)$ by the triangle inequality and $(†)$ from the definition of $| | \cdot | |_{◻}$ .

Note that this is a loose bound!

And this gives us the desired result for (2).
^proof-2

Proof of (1)

Proving (1) is more involved and uses more functional analysis.

Use the Riesz-Thorin interpolation theorem for complex $L_{p}$ spaces:

| | W | |_{p \to q} \leq | | W | |_{p_{1} \to q_{0}}^{1 - θ} | | W | |_{p_{1} \to q_{1}}^{θ}

Where

$θ = min (1 - \frac{1}{p}, \frac{1}{q})$ and
$p_{0}, q_{0} \in [1, \infty)$
with $\frac{1}{p} = \frac{1 - θ}{p_{0}}$ and
$1 - \frac{1}{q} = (1 - θ) (1 - \frac{1}{q_{0}})$ and
$p_{1} = \infty, q_{1} = 1$ .

Define operator norm$$\lvert \lvert W \rvert \rvert_{\square, \mathbb{C}} = \sup_{\begin{aligned}
f,g:[0,1] &\to \mathbb{C} \\lvert \lvert f \rvert \rvert_{\infty}, \lvert \lvert g \rvert \rvert_{\infty} &≤1 \end{aligned}} \left\lvert \int {0}^1 \int^1 W(u,v) f(u) g(v) , du , dv \right\rvert $$
So for complex functions, we can see that

\begin{aligned} for complex functions | | W | |_{\infty \to 1} & = | | W | |_{◻, C} \\ \leq 2 | | W | |_{\infty \to 1} for real functions \end{aligned}

We then have

| | W | |_{p_{0} \to q_{0}} \leq | | W | |_{1 \to \infty} \leq | | W | |_{\infty} \leq 1

Since $W \leq 1$ , and this gives the desired result.

Mentions

File
Davis-Kahan Theorem
convergent sequence of graph signals
graph shift operators converge to graphon shift operators
2025-03-26 lecture 15
2025-04-02 lecture 17

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>
}