3
$\begingroup$

So my question is same as this and this which were not answered.

I will explain why do I need this. Perhaps, there could also be a different solution. I use a black box gradient-free optimizer (Bayesian Optimization for clarity) of some cost function $f(x)$, where $x \in R^n$. A special property of the function is that $f(x) = f(ax)$ for any scalar $ a>0$, so the relative scale of $x$ does not matter. Therefore, I add a constraint $||x||_2=1$ which well-poses the search problem.

Possible options are:

1) Black box optimizers usually avoid such constraints. But it is possible to add a regularizer like $(||x||_2-1)^2$ to the cost function. However, I think it is possible to avoid it using the third option.

2) Normalize all elements of $x$ as $x \gets x / ||x||_2$. The inverse mapping is one-to-many, which means that BO will waste time sampling $ax, a>0$ vectors, if for some $a$ we already know $f(ax)$. For the same reason, this is not applicable in my case.

3) Reduce BO sampling dimension by 1, that is to sample $(n-1)$-dimensional variables, which on a unit (n-1)-sphere map into $n$-dimensional Cartesian vector. I am trying to figure out how to do it, but cannot find any way of doing it.

$\endgroup$
  • $\begingroup$ Do you mean this map in $n$ dimensions? $[0, 2\pi) \mapsto \text{unit circle in $\mathbb{R}^2$}, f(\phi) = (\cos(\phi), \sin(\phi))$? I.e. sample in $[0, 2\pi)$ uniformly and then transfer this onto the unit circle? $\endgroup$ – Fabian Werner Mar 1 '18 at 16:31
  • $\begingroup$ Yes, but in $n=8$ dimensions in my case $\endgroup$ – Ivan Mar 1 '18 at 16:33
  • $\begingroup$ Well, then the first link provides an answer: Sample $\phi_1, ..., \phi_{n-1}$ independently and uniformly in $[0, 2\pi)$ and then transfer them to the sphere using the map given in the first link with $r=1$... $\endgroup$ – Fabian Werner Mar 1 '18 at 16:34
  • 1
    $\begingroup$ The solution for the two-sphere given at stats.stackexchange.com/questions/7977/… generalizes in the obvious way to any number of dimensions. $\endgroup$ – whuber Mar 1 '18 at 16:34
  • 1
    $\begingroup$ Fabian, then points on the sphere are not uniform anymore corysimon.github.io/articles/uniformdistn-on-sphere $\endgroup$ – Ivan Mar 1 '18 at 16:37
5
$\begingroup$

Using spherical coordinates, \begin{align*} x_1 &= \cos(\phi_1)\,,\\ x_2 &= \sin(\phi_1)\cos(\phi_2)\,,\\ &\quad\quad\vdots\\ x_{n-1} &= \sin(\phi_1)\cdots\sin(\phi_{n-2})\cos(\phi_{n-1})\,,\\ x_n&=\sin(\phi_1)\cdots\sin(\phi_{n-2})\sin(\phi_{n-1})\,,\\ \end{align*} the $n$-dimensional unit sphere is parameterised by $(n-1)$ angles, $\phi_1,\ldots,\phi_{n-2}\in(0,\pi)$ and $\phi_{n-1}\in(0,2\pi)$. The uniform distribution on that sphere is associated with the joint density $$\sin(\phi_1)^{n-2}\sin(\phi_2)^{n-3}\cdots\sin(\phi_{n-2})$$ which means that the $\phi_i$'s are independent with respective densities $$\sin(\phi_1)^{n-2}\,,\ \sin(\phi_2)^{n-3}\,,\ldots,\ \sin(\phi_{n-2})$$and the Uniform $U(0,2\pi)$ on $\phi_{n-1}$. Simulating directly the $\phi_i$'s according to these densities thus returns the proper distribution of the angles for a uniform on the sphere, from which the Euclidean coordinates can be derived.

enter image description here

Simulating the $\phi_i$'s can be done (rather inefficiently) by accept-reject when using $\pi_1(\phi)\propto\sin(\phi)$ as a proposal since $$\sin(\phi)^d \le \sin(\phi)\qquad d\ge 1\qquad \phi\in(0,\pi)$$as illustrated by the following picture (representing $\sin^d$ for $d=1,2,\cdots,5$ and simulations from $\pi_1$ accepted or rejected depending on the target:

enter image description here

There exists however a more efficient way to simulate from the densities $\sin(\phi)^d$. Indeed, if$$\phi\sim\pi_d(\phi)\propto\sin(\phi)^d$$then, by a change of variable$$X=\cos(\phi)\sim f_d(x)\propto (1-x^2)^{(d-1)/2}\mathbb{I}_{(-1,1)}(x)$$and$$Y=X^2\sim g_d(y)\propto (1-y)^{(d-1)/2}y^{-1/2}\mathbb{I}_{(0,1)}(x)$$meaning$$Y\sim\mathcal{B}e(1/2,(d+1)/2)$$Therefore simulating $\phi$ from $\pi_d$ amounts to

  1. generate $Y\sim\mathcal{B}e(1/2,(d+1)/2)$ and $S=1-2\mathbb{I}_{U<1/2}$ for $U\sim\mathcal{U}(0,1)$
  2. take $\phi=\cos^{-1}(S*\sqrt{Y})$

As shown by the picture below for $d=3$, the fit on $10^5$ simulations is correct, as expected:

enter image description here

$\endgroup$
  • $\begingroup$ Thank you very much for detailed explanation. Now I see how you derived it. It answers the question nicely! However, I was not clear enough about the question, and now I see that the title is wrong, as well as point 3) in my question. Maybe I should make another question for this. But in short: Bayesian Optimization gives me a $n-1$-dimensional point $x \in [a,b]^{n-1}$ which I want to map to a $n$-point which lies on a unit sphere. $\endgroup$ – Ivan Mar 8 '18 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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