<p>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.</p>

CC BY-SA 3.0
2014-03-14T05:52:06.333Z
2014-03-14T05:52:06.333Z
mjqxxxx
<p>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 <a href="https://orion.math.iastate.edu/reu/2001/voronoi_paper/voronoi.pdf" rel="nofollow">centroidal Voronoi tessellation</a> (CVT).</p>

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

CC BY-SA 3.0
2014-03-13T14:23:02.620Z
2014-03-13T14:23:02.620Z
Chad Brewbaker
<p>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.</p>

<p>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.</p>

<p>What is the optimal way to proceed?</p>

<p>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 (<a href="http://en.wikipedia.org/wiki/RANSAC" rel="nofollow">http://en.wikipedia.org/wiki/RANSAC</a>) to find a geometric transform to align the $P^*$ and $P_2$.  This, however, seems to be a bit wasteful?</p>

<p>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?</p>

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

CC BY-SA 3.0
2014-03-13T08:34:49.483Z
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.
R B
CC BY-SA 3.0
2014-03-13T11:32:50.617Z
@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.
O1155
CC BY-SA 3.0
2014-03-13T11:35:15.470Z
@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?
O1155
CC BY-SA 3.0
2014-03-13T17:15:18.623Z
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"
Suresh Venkat
<ds.algorithms><cg.comp-geom>
Overlaying a point cloud on a two-dimensional probability distribution such that the local point density corresponds to the local probability density
O1155
# Overlaying a point cloud on a two-dimensional probability distribution such that the local point density corresponds to the local probability density

(Asked by: username_0 on 2014-03-13)

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.

**Tags:** ds.algorithms, cg.comp-geom
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_0**: @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?  
> **username_2**: 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"  

---

## 2 answers

### Answer by username_3 on 2014-03-14. Score: 0 | Accepted answer

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.


---

### Answer by username_4 on 2014-03-13. Score: 1

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](https://orion.math.iastate.edu/reu/2001/voronoi_paper/voronoi.pdf) (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.


---

