2
$\begingroup$

Say I sample a set of points $(p_1,p_2,...) \in P$ from a probability distribution $f(x,y)$, e.g. a bivariate normal distribution, such that my sampling process chooses a point in the distribution with a probability proportional to the value $f(x,y)$ at that point. In particular, let's say we use the Metropolitan-Hastings algorithm to sample the set of points $P$ via a biased random walk.

Now, I take $P$, and I apply some arbitrary geometric rotational and translational geometric transform that acts uniformly on all points $p_i \in P$. I provide this transformed set of points $P^*$ to you, and your job is to reverse the geometric transform and map the coordinates back to their original positions to the best of your ability.

What is the optimal way to proceed?

A thought is that we can sample a new set of points $P_2$ from the distribution $f(x,y)$, and then use something like the RANSAC algorithm (http://en.wikipedia.org/wiki/RANSAC) to find a geometric transform to align the $P^*$ and $P_2$. This, however, seems to be a bit wasteful?

Motivation - Say we know that the maxima of the distribution $f(x,y)$ occurs at some $(x_k,y_k)$. What is $(x_k,y_k)^*$, i.e. where is this point after applying the geometric transform that mapped $P$ to $P^*$? We could also ask about other "distinct" points of interest in $f(x,y)$ so that it isn't simply a matter of computing something like a geometric mean (or perhaps geometric median) of the point set $P^*$ to calculate $(x_k,y_k)^*$. Can we figure this out without the kind of silly solution I propose the employs the RANSAC algorithm?

(In response to R. B.'s comments): I mean "up to symmetry" here - apologies for the confusion.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Suppose $f(x,y)$ is indeed the bivariate normal distribution. Now I take $P$ and rotate it. The result still is a bivariate normal distribution. How do you expect to find the original points? I don't see anything that could help you figure the rotation, even if $f$ is known to you. $\endgroup$
    – R B
    Mar 13, 2014 at 8:34
  • $\begingroup$ @RB I don't need to recover the exact original transformation, just one that properly overlays the set of points $P^*$ on the original distribution in a manner that best approximates sampling $||P||$ points from this distribution. Also, the bivariate normal distribution has a lot of symmetry, but I'd like this to work for less symmetric probability distributions as well. $\endgroup$
    – O1155
    Mar 13, 2014 at 11:32
  • $\begingroup$ @RB I'm wondering if this can be done in a smarter manner than simply resampling from $f(x,y)$ and then aligning these resampled points with $P^*$ using something like RANSAC? $\endgroup$
    – O1155
    Mar 13, 2014 at 11:35
  • 2
    $\begingroup$ I think @RB's point is that the two distributions (the original and the rotated one) are identical. There's no way to tell them apart. You have to add some proviso to your question of the form "upto symmetries". So the bivariate normal is a particularly bad case. And in fact any radially symmetric distribution would be impossible to recover except "upto symmetries" $\endgroup$
    – Suresh Venkat
    Mar 13, 2014 at 17:15

2 Answers 2

Reset to default
0
$\begingroup$

This seems to depend heavily on the form of $f$. If $f$ has a small number of distinct features (say, a handful of well-separated sharp peaks), then you can attempt to identify those features in the point cloud and then use SVD to find the Euclidean transformation that best takes the observed features back to their original locations. If $f$ is spread out and has no obvious landmarks (e.g., $f(x,y)\propto e^{-\beta(x^2+y^2)}\left(1+\varepsilon\sin^2(x+y)\right)$, where $\beta$ and $\varepsilon$ are small), then there will be no way to find the maximum-likelihood transformation without trying a large number of possibilities. In general it becomes an optimization problem that could have many, many local optima.

Improve this answer
$\endgroup$
1
$\begingroup$

Overlaying a point cloud on a two-dimensional probability distribution such that the local point density corresponds to the local probability density is a good way to define the cell generators of a centroidal Voronoi tessellation (CVT).

CVTs don't loose their quantization precision by translation or rotation in concert with the underlying probability distribution. Not sure what your question is.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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