The n-Category Café

Interesting stuff.

Could you elaborate on your example; I was never that sharp and the fact it’s a Friday means you’ll have to spell things out. In particular, I’m not sure if attempting to you’re rate the “class compatibility” of two documents or two sets of documents?

Regarding your question about kernels, if you consider the discretised version of the fourier transform the DFT and its various similar transforms like wavelets, then the full discretised function (ie $g(1)$, $g(2)$, …, $g(N)$) is related to the transform discretised function ($Tg(1)$, …, $Tg(N)$) by a matrix mulitplication (as is obvious when you realise each “output” function value is a weighted linear combination of the original function values.) From this viewpoint the various “fast” algorithms correspond to “factorisations” of this matrix. However, I suspect that’s probably not the kind of matrix view of a kernel you’re looking for.

Final question: my only real knowledge of the span of groupoid stuff if the TWFs (in particular week 248 for the spans of groupoid stuff. Is there any online paper that deals with this stuff (in particular how relations transform into numeric valuations)? John is hinting that this will be explained about in coming TWFs.

David wrote:

We’ve had a slight whiff of the idea that groupoids and groupoidication might have something to do with the kernel methods we discussed last time.

Sounds right!

You just explained how integral kernels arise naturally from ‘witnessed relations’ — that is, spans of sets. Each ‘witness’ to some relation between $x \in X$ and $y \in Y$ contributes a term to the integral kernel $K(x,y)$.

But, if you were studying machine learning in the presence of symmetry, you might want invariant witnessed relations. For example: if seeing some scene makes you infer something about the location of some object, seeing a translated version of that scene should cause you to make the same sort of inference, only translated!

Now, in week248 and subsequent Weeks, I explained how invariant witnessed relations are spans of groupoids. And, decategorifying these gives matrices — or in more highbrow contexts, ‘integral kernels’!

In fact, in a half-written This Week’s Finds I’m already starting to talk about some famous integral kernels that come from invariant witnessed relations.

For example, the Radon transform comes from a span involving the space $X$ of points in $\mathbb{R}^n$ and the space $Y$ of hyperplanes in $\mathbb{R}^n$. The Euclidean group $G$ acts on both these spaces, and there’s an obvious span of $G$-spaces describing the invariant relation

the point $x$ lies on the hyperplane $y$.

Namely:

                     S
                    / \
                   /   \
                  /     \
                 /       \
                v         v 
               X           Y

where $S$ is the set of pairs $(x,y)$ consisting of a point $x$ lying on a hyperplane $y$.

(In this particular case, there’s either 0 or 1 witnesses to the fact that $x$ lies on $y$, so our ‘invariant witnessed relation’ is really nothing but an invariant relation. It’s a sort of degenerate example.)

Given this span of $G$-spaces, and using the fact that $X$, $Y$ and $S$ are equipped with $G$-invariant measures having some nice properties, we instantly get the integral kernel for the Radon transform! I’ll explain how in the actual article.

But, the cool part is that this process of getting the kernel is nothing but a slightly souped-up version of decategorifying a span of groupoids to get a matrix of numbers.

‘Slightly souped-up’, because an integral kernel is really a matrix where the indices take continuous rather than discrete values, so the usual sums involved in matrix multiplication get replaced by integrals. That’s why our spaces $X$, $Y$ and $S$ must have measures for the game to work.

I hope this is clear. I think there really is something to what you’re saying.

By the way, I have no idea why the word “kernel” is used both to mean two completely different things: “function of two variables defining an integral transform” and “subspace on which a linear operator vanishes”. It’s unfortunate, since it makes phrases like “the kernel of the operator” hopelessly ambiguous in certain contexts.

Is “kernel” a translation of German “Kern”? Does this ambiguity also occur in German?

A very interesting on-line book by Sigurdur Helgason, The Radon transform:

Given two homogeneous spaces $G/K$ and $G/K$ of the same group $G$, the Radon transform $u \to \hat {u}$ maps functions $u$ on the first space to functions $\hat {u}$ on the second space. For $\xi \in G/H, \hat{u}(\xi)$ is defined as the (natural) integral of $u$ over the set of points $x \in G/K$ which are incident to $\xi$ in the sense of Chern. (p. 5)

Page 63 shows you the relevant span of $G$-sets.