Align noisy point clouds I have a point cloud $X$ that, I suspect, is a translate of a Gaussian-corrupted version of a subset of a larger cloud $Y$, both high-dimensional ($d$ is at least 100 and ideally 10,000). What is the best way of recovering the translate here? I tried a naive EM algorithm based on a Gaussian mixture model but it's almost a non-starter, since the correspondence probabilities are so low.
Edit: I am analyzing RNA-seq data and have two datasets of cell archetypes - these are just vectors in high-dimensional space. These sets were constructed on different machines, and I think that the technical difference between the two datasets is a component-wise (positive) multiplier, or after a log transform, a translate. I'd like to recover the translate to see which archetypes are present across datasets. I tried the EM algorithm for this (a modified version of what appears in Myronenko and Song's "Non-rigid point set registration: Coherent Point Drift") but because the dimensionaliy is so high every point has almost zero probability of belonging to every class in the other dataset, even when guessing initial translates. Is there a different way to go about solving this problem?
 A: Since you are only looking for a translate and the number of points is not too large a more pedestrian approach might be feasible. There is no guarantee that the following ideas will work but it seems plausible to me and is easy to implement. It relies on first identifying matching pairs of points and then taking those to estimate the translate.
1. Identify matching pairs
Denote by $Y=\{y_1,\ldots,y_N\}$ the larger set and with $X=\{x_1,\ldots,x_M\}$ the smaller set containing the translated points with noise. There is an unknown inclusion $\tau:\{1,\ldots,M\}\rightarrow\{1,\ldots,N\}$ mapping the points from $X$ to their matching counterparts in the larger set $Y$. For matching points with $k=\tau(i)$ you have the equation:
$$ x_i = y_k + a + \epsilon_i$$ where $a$ is the unknown translate and $\epsilon_i\sim\mathcal{N}(0,\Sigma)$ the Gaussian error. For matching pairs of points $(k,l) = (\tau(i),\tau(j))$ you find:
$$ x_{ij}=x_i - x_j = y_k-y_l + \epsilon_i - \epsilon_j.$$ 
Writing $y_{kl}=y_k-y_l$ and $\epsilon_{ij}=\epsilon_i-\epsilon_j$ the length of the difference between the connecting vectors is:
$$ \lVert x_{ij} - y_{kl}\rVert^2 = \lVert \epsilon_{ij}\rVert^2.$$
Since the distribution of $\epsilon_{ij}$ is normal, the distribution of $\lVert \epsilon_{ij}\rVert^2$ is $\chi^2$ and you can find lower and upper bounds $l_\alpha, u_\alpha$ around the expectation such that:
$$ P(l_\alpha < \lVert \epsilon_{ij}\rVert^2 < u_\alpha)=\alpha.$$
Now call any two pairs $(i,j)$, $(k,l)$ a (potential) match if $l_\alpha < \lVert x_{ij} - y_{kl}\rVert^2< u_\alpha$.
Of course there is no guarantee that this criterion will give you all actual matches and only those. But the idea is that for true matches the noise shouldn't change the distance too much while non-matches should produce large differences because $y_k-y_l$ is pointing in a direction very different from $x_i-x_j$. Even if you have the occasional false match not all hope is lost, you can correct for this in the second step.
2. Estimating the translate
Every match produces two estimates for $a$:
$$ \tilde{a}_i=x_i-y_k\text{ and } \tilde{a}_j=x_j-y_l.$$
For correct matches you know that $\tilde{a}=a+\epsilon$. Hence you can recognise and eliminate outliers stemming from false matches. Finally your estimate for $a$ is just the mean of the outlier-corrected $\tilde{a}.$
For $M=30$, $N=80$ you will have $\frac{30*29}{2}=435$ connecting lines $x_{ij}$ in $X$ and $80*79=6320$ (order matters!) $y_{kl}$ in $Y$. So the calculations should be easily doable. 
