0
$\begingroup$

Consider two sets of points $P = (P_1, ...,P_n), \ Q = (Q_1, ..., Q_m) $ included in $\mathbb{R}^3$.

I'm looking to compute an optimal affine transformation that "maps" $Q$ to $P$, although the sets don't have the same number of elements.

A trivial case is one where $m=n$ and $Q = (R \cdot P_1 + T, R\cdot P_2 + T, ..., R\cdot P_n+T)$

The issue is that I'm not sure how to describe this optimization problem.

edit :

As pointed out in comments, I should have been more specific. In my application, both sets of points represent different closed curves in space. I'm trying to best position one curve against the other one (in the least squares sense, for example).

$\endgroup$
  • 1
    $\begingroup$ How would such a transformation always exist? Imagine the $P$s to be the corners of a simplex (so they span a volume) but the $Q$s to lie in a plane (so their volume is zero). Any affine transformation will map a planar set of points into a planar set of points. In other words, you will have describe in more detail what it is you want -- i.e., what your objective function for is to find an affine mapping that comes as close as possible to your goal. $\endgroup$ – Wolfgang Bangerth Oct 26 '18 at 19:16
  • $\begingroup$ You're right, I edited my question in order to be more specifc. $\endgroup$ – Dooggy Oct 27 '18 at 7:30
  • $\begingroup$ Well, but there are also infinitely many curves going through the $P_i$ whose image might go through the $Q_i$ or be optimal in some sense. Your question is basically about high dimensional data analysis, machine learning, separators, etc. Have you looked at a book on machine learning? $\endgroup$ – Wolfgang Bangerth Oct 28 '18 at 12:44
1
$\begingroup$

Based on the problem description, and under the assumption you do not know which point in $Q$ some point in $P$ should be best matched up with when computing errors, I am tempted to say you might be able to pose your optimization problem in a general sense as something along the lines of

\begin{align} \min_{R, T} \sum_{p \in P} \min_{q \in Q} \left \lVert R p + T - q\right \rVert^2 \end{align}

The idea is to minimize the sum of nearest neighbor distances between each affine mapped vector $p$ and the points within the set $Q$. This looks a bit nasty at first glance due to the minimum in the sum, but from here, we might approximate this objective function by

\begin{align} \min_{R, T} \; \;-\sum_{p \in P} \epsilon \log\left( \sum_{q \in Q} \exp \left(\frac{-\left \lVert R p + T - q\right \rVert^2 }{\epsilon}\right) \right) \end{align}

for some $\epsilon > 0$ that is close to $0$. Note that this approximation is based on the fact that $\lim_{\epsilon \rightarrow 0} \epsilon \log\left(\sum_{i=1}^n \exp\left(x_i/\epsilon\right)\right) = \max_{i} x_i$. Assuming you choose some value for $\epsilon$, like say $\epsilon = 10^{-3}$, you should be able to compute the gradients with respect to $R$ and $T$ of this objective function above and solve it in an unconstrained manner. The benefit to the construction above is it makes no assumption on the size of either set of points.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.