Eric Forgy Colimit as a Linear Regression of Multisets

Warning: This page is highly speculative and the title could very well be complete nonsense. Feedback is more than welcome.

Given a set $X$ and a finite collection of sets $X_i$ , we are interested in finding “the best possible” multiset expression

X = \sum_{i=1}^N w_i X_i + \mathcal{E}

such that the inner product satisfies

\langle X^*_i,\mathcal{E}\rangle = 0,

where $X^*_i$ is a dual multiset satisfying

\langle X^*_i,X_j\rangle = \delta_{i,j}

so that

\langle X^*_i,X\rangle = w_i.

As a step toward this goal, define a matrix whose elements are given by

Z_{i,j} = \langle X_i,X_j\rangle = |X_i\cap X_j|.

Case 1: $det(Z)\ne 0$

If the inverse matrix exists, we can define

X^*_i = \sum_{j=1}^N Z^{-1}_{i,j} X_j.

Note that although the elements $Z_{i,j}$ are integers greater than or equal to zero, the elements are $Z^{-1}_{i,j}$ are rational numbers that can be negative. Therefore, although multisets form a rig, dual multisets form a $\mathbb{Q}$ -algebra.

The weights are then given explicitly by

w_i = \sum_j Z^{-1}_{i,j} \langle X_j,X\rangle = \sum_j Z^{-1}_{i,j} |X_j\cap X|.

Case 2: $det(Z)\ne 0$ and $X_i\cap X_j = \emptyset$

When the sets $X_i$ are disjoint, $Z$ is a diagonal matrix whose entries are given by

Z_{i,i} = |X_i|.

The inverse matrix is obviously also diagonal with entries given by

Z^{-1}_{i,i} = \frac{1}{|X_i|}.

In this case, weights reduce to

w_i = \frac{|X_i\cap X|}{|X_i|}

and we have

X = \sum_{i=1}^N \frac{|X_i\cap X|}{|X_i|} X_i + \mathcal{E}.

References

Limits and Colimits by Example
Why “Weight”? (n-Cafe)

Created on October 28, 2009 at 06:20:17 by Eric Forgy

Eric Forgy Colimit as a Linear Regression of Multisets

Case 1: det(Z)≠0det(Z)\ne 0

Case 2: det(Z)≠0det(Z)\ne 0 and X i∩X j=∅X_i\cap X_j = \emptyset

References

Case 1: $det(Z)\ne 0$

Case 2: $det(Z)\ne 0$ and $X_i\cap X_j = \emptyset$