In an applied research problem I am currently working on, I am using non-commutative semiring convolution to formulate some interesting types of calculations on images and solid objects. For discrete groups, this is pretty easy to set up. Given a semiring, $(S, oplus, odot)$, and a discrete group $G$, define the semialgebra $S[G]$ as the collection of maps $S^G$ equipped with the bilinear operator $star : S[G] times S[G] to S[G]$ such that for all $f, h in S[G]$:
$(f star h)(x) = bigoplus limits_{y in G} f(y) odot h(y^{-1}x)$
This works well, and is consistent with the usual definition of a group algebra when $S$ is a ring. However, in almost all of the interesting situations I can think of, I would like to take $G$ to be a Lie group. To make this happen, it seems that the right thing to do should be to define some kind of 'semiring valued Haar measure', $mu : 2^G to S$ which would allow one to compute $S$-valued integrals over $G$. Assuming this works just like it ought to in fields of characteristic 0, then convolution becomes some $S$-valued integral over $G$ like the following thing:
$(f star h)(x) = bigoplus limits_{y in G} f(y) odot g(y^{-1}x) odot d mu(y)$
Where the symbol $bigoplus$ means something like a 'semiring' Lebesgue integral over $G$. Unfortunately this definition is not very robust. One can easily pick plausible values of $S, G, mu$ which catastrophically fail. For instance, if $S = mathbb{Z} / n mathbb{Z}$, then it seems to me that the convolution integral is divergent for any function with measurable support!
However, all is not lost. I can think of a few easy cases where one can construct a measure which is convergent and gives 'reasonable' results (and by reasonable, I mean that they are intuitively similar to the results one would get in the case of a discrete group). Consider, for example, the case where $S$ is the idempotent boolean semifield, $B = ( mathbf{2}, OR, AND )$. Then take:
$mu(emptyset) = 0$
$mu(S neq emptyset) = 1$
Now the elements $f, g in B^G$ can be identified with subsets $X_f, X_g subseteq G$, and moreover the convolution on $G$ over $B$ gives rise to a so-called generalized Minkowski product:
$f star g cong X_f oplus X_g = bigcup limits_{x in X_f} x X_g$
Which is indeed a useful calculation! Similarly, one can define a measure like this over the $(max, +)$ semiring via another ad-hoc construction. This begs the question: when does this convolution actually work? More specifically, what are the conditions on $S, G, mu$ such that we can guarantee that convolution is convergent?
(Note: I am probably not being as careful as I should be with definitions. It is probably a good idea to restrict the elements of $S[G]$ to 'Haar-like' measurable functions, but I really don't have a good grasp of what this should mean until I know what the proper conditions on $mu$ should be...)
No comments:
Post a Comment