1
$\begingroup$

We are given a set $X$ of $n$ points $\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\in\mathbb{R}^d$, where $d\ll n$. Given any point $\mathbf{p}$ on the unit $(d-1)$-sphere $\mathcal{S}$, we define $\Delta(X,\mathbf{p}):=\max_{\mathbf{x},\mathbf{x}'\in X}|\langle\mathbf{p},\mathbf{x}\rangle-\langle\mathbf{p},\mathbf{x}'\rangle|$. Finally, we define $D(X)$ as the distribution with sample space $\mathcal{S}$ for selecting a point on $\mathbf{p}\in\mathcal{S}$, such that the probability of selecting $\mathbf{p}$ is proportional to $\Delta(X,\mathbf{p})$.

Question: How can we efficiently sample a point $\mathbf{p}\sim D(X,\mathbf{p})$?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Can't you just sample a point $p$ uniformly on $\mathcal{S}$. Then draw a independent $u$ variable uniformly on $[0,2]$. If $u\leq\Delta(X,p)$ keep $p$ and you are done. If $u>\Delta(X,p)$ then forget about $p$ and redo the sampling. Repeat the process until you get some $u\leq\Delta(X,p)$

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your answer @RaphaelB4. My "departure point" in my research was exactly this rejection method. The issue is that the minimum over $X$ of the acceptance probability decreases as $d$ grows, and it is equal to $\Theta\left(\frac{1}{\sqrt{d}}\right)$. I am looking for a fastest method. In my problem formulation, in fact, my goal is to avoid wasting time with rejection sampling techniques. $\endgroup$
    – Penelope Benenati
    Commented Jan 20, 2021 at 15:48
1
$\begingroup$

As answered by RaphaelB4 it seems best first to simulate a random point on $\mathcal{S}$ and then to apply the rejection method, see f.i. L. Devroye, Non Uniform Random Variate Generation (1986). For the second step you need the maximum $m$ of $x \to \Delta(X,p)$ and then you have to generate random $U \in [0,m]$. (I have not investigated if $m \leq 2$.) For high dimension $d$ the simulation of a random point $y \in \mathcal{S}$ is not trivial. One possibility is to generate $d$ $N(0,1)$-distributed independent values $(y_1,\ldots,y_d)$. Then $\frac{1}{\sqrt{\sum_{i=1}^d y_i^2}}(y_1,\ldots,y_d)$ is a random point on $\mathcal{S}$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for the reference @DieterKadelka and your answer. My "departure point" in my research was exactly this rejection method. The issue is that the minimum over $X$ of the acceptance probability decreases as $d$ grows, and it is equal to $\Theta\left(\frac{1}{\sqrt{d}}\right)$. I am looking for a fastest method. In my problem formulation, in fact, my goal is to avoid wasting time with rejection sampling techniques. $\endgroup$
    – Penelope Benenati
    Commented Jan 20, 2021 at 15:50
  • $\begingroup$ @PenelopeBenenati: The speed of the rejection method depends on $m$. If $m$ is not high, which depends on $X$, I think this method is acceptable, since only $m$ replications are to be expected. $\endgroup$
    – Dieter Kadelka
    Commented Jan 20, 2021 at 18:39
  • 1
    $\begingroup$ I think that the time complexity heavily depends also on the ratio number_of_accepted/number_of_rejected, which can be in the worst case $\approx 1/\sqrt{d}$. If $d\gg 1$, as for the problem I am trying to solve, this is an issue. That's why I posted this question. I was curious to see if there was any other strategy to accelerate methods based on rejection sampling (consider, for instance, that we know that all points lie on a line segment $L$ with a very small perturbation in any direction and $L$ is embedded within $\mathbb{R}^d$). $\endgroup$
    – Penelope Benenati
    Commented Jan 20, 2021 at 18:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .