# Efficiently Sampling of Multivariate Distributions in the Vicinity of a Manifold

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

• 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? Apr 14, 2017 at 11:12
• @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? Apr 14, 2017 at 12:26
• 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? Apr 14, 2017 at 12:35
• @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. Apr 14, 2017 at 13:34
• 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. Apr 14, 2017 at 15:23

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}$.