0
$\begingroup$

I am given a multivariate distribution, that maps each point of $\mathbb{R}^n$ to its probability of being drawn as sample and, the convolution $\mathcal{S_r}\times\mathcal{M}$ of a manifold $\mathcal{M}: \mathbb{R}^m\mapsto\mathbb{R}^n$, $m\lt n$, of $\mathbb{R}^n$ with the $n$-dimensional hypersphere $\mathcal{S_r}:\sum_{i=1}^n x_i^2\le\mathcal{r}^2$

Question:

  • what are general and non-trivial methods for sampling an arbitrary multidimensional distribution inside the convolution of a hyper-sphere with a manifold?

(I am especially interested in methods, whose runtime depends on the number of samples generated in the convolution).

Clarification: I consider rejection methods (i.e. drawing a samples from $\mathbb{R}^n$ and only reporting those in the convolution) as trivial. Edit:

The motivation for the question is a possible suggestion of an answer to Finding energy minimizing path.

My idea is to start by generating a sufficiently dense sampling of the $xy$-plane by using e.g. Poisson Disk Sampling (a.k.a. Blue Noise), construct that pointset's Delaunay Triangulation with edge-weights complying to the energy-cost model and then calculate the least cost path.
Then, once the initial path is calculated, iterate by increasing the sampling density in an $\epsilon$-hose around the path, reconstruct the Delauny and recalculate the shortest path.
Whether that algorithm is efficient, depends however crucially on the ability to restrict Poisson Disk Sampling to a path's $\epsilon$-hose. For the special case of an equal distribution I don't see a problem in restricting the sampling to ever finer grid-cells covering the path, but for other distributions I have no idea, how to proceed in an analogous way without introducing sampling bias. That idea is elaborated in my answer to that question

$\endgroup$
5
  • $\begingroup$ It depends on the property of the distribution you have, there are modified versions of MCMC. Can you be more specific on details of OP so I can give it a try? Say, give a toy example? $\endgroup$
    – Henry.L
    Apr 14, 2017 at 11:12
  • $\begingroup$ @Henry.L say I have a $2D$ normal distribution and the manifold is the graph of a function $\left(x,f(x)\right)$ and, to simplify matters, I want to generate samples in the region $0\le x\le 1, f(x)-c\le y\le f(x)+c$; is that example sufficient for suggestions? $\endgroup$ Apr 14, 2017 at 12:26
  • $\begingroup$ Is it just a sampling with finite support over a nbd of a given manifold? In this case why don't you use truncated normal instead? $\endgroup$
    – Henry.L
    Apr 14, 2017 at 12:35
  • $\begingroup$ @Henry.L truncated distributions may indeed be used for sampling the distribution within a box that covers the graph; what still is not clear to me is how to select one of the covering boxes - but I can imagine, that converting the continuous distribution into a discrete one with constant value over a box could be the final answer (the discrete value would correspond to the integral of the densitiy function over the individual boxes). Thanks to your comments I now see, how to proceed. $\endgroup$ Apr 14, 2017 at 13:34
  • $\begingroup$ Anyway I added my answer below and hope it helps.If you are to sample a energy-minimizing path, a variational algorithm may be a better choice. You can use polya tree to construct such boxes/partitions. $\endgroup$
    – Henry.L
    Apr 14, 2017 at 15:23

1 Answer 1

2
$\begingroup$

Question: How to sample when the support of prior(parameter space) is bounded set?

Answer:There are following solutions if the parameter space is bounded instead of the whole parameter space.

  1. Individual sampler. We used another random walk/probability generator like truncated version of normal random walk to replace the sampler. The simulation result showed that if we directly use such a sampler then acceptance rate(decision to keep the sample) is usually oddly low.

  2. Modify the model. We can modify the model, for example, using the transformation $\eta=log\tau^{2}$(half line to the whole space) to sample for variance parameter in a exponential model and the model likelihood becomes $$\begin{array}{c} \underbrace{(e^{\eta})^{-2-1}\cdot exp\left(\frac{2}{e^{\eta}}\right)\left|\frac{\partial e^{\eta}}{\partial\eta}\right|}\\ \tau^{2}=e^{\eta}\:prior \end{array}$$with Jacobian of the transformation, now the parameter $\eta$ is supported on the whole $\mathbb{R}$ and the metropolis step can be conducted using the usual normal random walk because $\eta\in\mathbb{R}$.

  3. Drop the random walk when it goes out of the support of prior. That is to say, when the normal random walk goes out of the support of the prior we simply rejected the proposal value and stay with the old value of the parameter. This is the "trivial" solution you mentioned above.

  4. Extended the model. This is a remark from Gelman, Andrew, et al. Bayesian data analysis., we can sometimes extend the problem to allow a larger parametric space if the support if actually too small to put, say, a normal random walk on it.

$\endgroup$

Your Answer

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

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