Let us consider two sets of points $\{x_i\}_{i=0}^N$ and $\{y_i\}_{i=0}^M\in\mathbb{R}^2$. I am interested in a subset of each of those sets (depicted in blue and red, respectively). These two subsets have the same cardinality, and a 1-to-1 correspondence to the other set. We also consider a set $\{\delta_k\}_{k=1}^K$ of distances between corresponding members across the two subsets, where $K$ is the cardinality of each subset. That is, for each pair of points in the two subsets $(x_k,y_k)$ we would like the distance between them to be as close to $\delta_k$ as possible (see figure below).
My objective is to find an affine transformation $A\in\mathbb{R}^{2\times2}$ such that when it is applied to all the points in the set on the right, it makes the distance between each $x_k$ and $y_k$ close to $\delta_k$. Again, note how the transformation is applied only to the points in the set $\{x_k\}_{k=1}^K$. One way to formulate this is to minimize the sum of (absolute) differences between the squared distances between each pair $||Ax_k-y_k||_2^2$ and $\delta_k^2$:
$$ \begin{align} \min_{A\in\mathbb{R}^{2\times 2}}\quad \sum_{k=1}^{K} \Biggr|||Ax_k-y_k||_2^2 - \delta_k^2\Biggr| \end{align} $$
However, this formulation as it stands has two issues:
- It is not convex. In particular, were it not for the absolute value in the sum, this problem would be an easy sum of squares.
- It doesn't take into account the fact that the affine transformation can be a combination of scaling, translation, and rotation. This can be addressed by considering all the points in homogeneous coordinates, but I don't know what the implications would be in terms of constraints on the optimization problem.
My question then, is: given the goal described above, can I formulate a convex problem to (even approximately) achieve it?