# Using Expectation Maximization for Optimal Weighted Matching

I have the following problem: Given point sets $A$ and $B$, I want a labelling of the points in $A$ with points in $B$, i.e. $L:A\rightarrow B$.

The points $a\in A$ and $b\in B$ have associated (vector) descriptors, $h(a)$ and $h(b)$, so that a "distance" can be defined between the points in the set as $$d_h(a,b) = ||h(a)-h(b)||_2$$ Average error could then be: $$d_H(L) = \frac{1}{|A|} \sum_{a\in A} d_h(a,L(a))$$ But this is not good enough, because I need $L$ to preserve closeness. I.e. neighbourhoods in $A$ should also be roughly neighbourhoods after mapping. E.g. I could say I also want to minimize: $$d_N(L) = \frac{1}{|A|} \sum_{a\in A} \sum_{s_i\in L_a} \sum_{s_j\in L_a} || s_i - s_j ||_2$$ where $N(a)\subset A$ is a set of nearby points of $a$ and $L_a = L(N(a))=\{L(a_i)|a_i\in N(a)\}$.

This can be viewed as a kind of weighted approximate undirected graph matching. In other words the nodes of $A$ need to be mapped to nodes of $B$. Each graph has weights between each node in the graph, and weights between each of the nodes in $A$ and $B$. I need $L$ to be such that if $a_i$ is close to $a_j$, then $L(a_i)$ should be close to $L(a_j)$.

I can't really see an elegant way to solve this, except maybe by an optimization program minimizing some combination of $d_H(L)$ and $d_N(L)$ (which are not on the same scale).

But it seems like I should be able to apply expectation-maximization to it somehow. I.e. I could choose a starting labelling with $d_H$, estimate the error and a probability distribution per $a\in A$, compute a better labelling, and so on. Does someone know how that could work?