ADTDA, lecture 5

\(\def\Real{\mathbb{R}}
\def\Int{\mathbb{Z}}
\def\ph{\mathtt{PH}}
\def\dim{\mathrm{dim}}
\def\CF{\mathtt{CF}}
\def\one{\mathbb{1}}
\)

Euler calculus and sensor fusion

Euler characteristics’ additivity (apply with care! if used with vanilla singular homologies, work with compact sets only; if going beyond that, use some o-minimal structure) makes possible a version of integration, where the values are added weighted not by Lebesgue measure (as in the common integrals), but with Euler characteristic:
\[
\int h d\chi=\sum_{r} r\chi(\{h=r\}).
\]

For this definition to make sense, we need, of course, the function to have a finite range (in some commutative ring, like \(\Int\)), and all the preimages reside in the o-minimal structure we work with. We will be referring to such functions as constructible.

Then, thus defined integral is additive and Fubini theorem works.

One has an immediate application to data fusion: if one has a very dense field of sensors, each measuring the number of objects they can sense. Assuming that the footprint of each object has the same (nonzero) measure, one can just integrate the sensor readings and divide by the measure, – whether the measure is Lebesgue or with respect to Euler characteristic.

Of course, if the measure vanishes, the counts become indefinite…

One can use this approach even for moving objects, with appropriate modifications.

This view can be generalized to a version of integral calculus wrt \(\chi\). For a constructible kernel \(K:X\times Y\to\Int\), one can define the integral operator \(\CF_Y\to\CF_X\) by
\[
(Kh)(x)=\int K(x,y)h(y)d\chi(y).
\]

For example, when \(X=Y=\Real^d\), and \(K=g(x-y)\), the transform defines convolution \(h\star g\) (wrt \(\chi\)).

Classically, the convolution of indicator functions of convex compact sets gives the Minkovski sum:
\[
\one_A\star\one_B=\one_{A+B}.
\]
Inegral calculus allows one to rigorously deconvolve Minkovsky sum:
\[
\one_A\star\one_{-A^o}=\delta_0;
\]
here \(A^o\) is the interior of \(A=\overline{A^o}\).

A general class of problems admitting inversion was introduced by Schapira: often one can find a pair of kernels \(R,S\) such that
\[
\chi(R^{-1}(x)\cap S^{-1}(x))=\mu, \chi(R^{-1}(x)\cap S^{-1}(x’))=\lambda
\]
for any \(x\neq x’\in X\). In this case, if \(g(y)=\int S(y,x)h(x)d\chi(x)\), then
\[
\int R(x,y)g(y)d\chi(x)=(\mu-\lambda)h(x)+\lambda\int h d\chi.
\]

Examples include projective duality and integrals over circles.

Aggregation

Important aspect of data analysis is aggregation: collapsing a flock of points into a single point (finding “averaging”, or “median” or other representative point).

It is a nontrivial task: in some situations, can be done in principled way: say, in case of \(\mathtt{CAT}(0)\) spaces.

But in many situations this task is seen as difficult. If one requests that the aggregation operation
\[
f:X\times\cdots\times X\to X
\]
respects a) unanimity (\(f\circ\Delta_X=\mathtt{id}_X\)) and b) anonymity (\(f(x_{1},\ldots,x_{k})=f(x_{\sigma_1},\ldots,x_{\sigma_k})\) for any permutation \(\sigma\)), then a theorem by B. Eckmann says that any reasonable topological space admitting aggregation over any \(k\geq 2\) points is contractible.

One important applications of this impossibility to aggregate is in social choice theory: one cannot create a democratic procedure if the space of preferences is topologically complicated…

No comments yet.

Leave a Reply