operator distance modulo permutations

[[concept]]

The operator distance modulo permutations for an operator $ψ : x \mapsto y$ is given by

\begin{aligned} | | ψ - ψ^{'} | |_{p} & = min_{P \in P} max_{x : | | x | | = 1} | | P^{T} ψ (x) - ψ^{'} (P^{T} x) | | \\ = sup_{x : | | x | | = 1} | | P^{T} ψ (x) - ψ^{'} (P^{T} x) | | \end{aligned}

This can be defined for any norm on the LHS, but typically is the operator norm induced by the 2 norm.

We can think of this as a relative measure of how "far" $ψ^{'}$ is from being a permutation of $ψ$ .

Note

For graphs, we can consider $ψ$ to be some graph and $x$ the nodes. This looks for the permutation that makes these graphs closest to one another, then computes a distance.

operator distance modulo

G

Let $G$ be a group and $F : x \mapsto y$ an operator. Then the operator distance modulo $G$ is given by

| | F - F^{'} | |_{G} = min_{g \in G} max_{x : | | x | | = 1} | | g \circ F (x) - F^{'} (g \circ x) | |

(where, presumably, $F^{'} = g_{0} \circ F$ for some fixed $g_{0} \in G$ )

Mentions

File
additive perturbations
filter permutation invariance
quasi-symmetry
relative perturbations
2025-03-05 graphs lecture 12
2025-03-10 graphs lecture 13