3

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.

Ivan
  • 133
  • 4
  • 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? – Fabian Werner Mar 01 '18 at 16:31
  • Yes, but in $n=8$ dimensions in my case – Ivan Mar 01 '18 at 16:33
  • 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$... – Fabian Werner Mar 01 '18 at 16:34
  • 1
    The solution for the two-sphere given at https://stats.stackexchange.com/questions/7977/how-to-generate-uniformly-distributed-points-on-the-surface-of-the-3-d-unit-sphe/7984#7984 generalizes in the obvious way to any number of dimensions. – whuber Mar 01 '18 at 16:34
  • 1
    Fabian, then points on the sphere are not uniform anymore https://corysimon.github.io/articles/uniformdistn-on-sphere/ – Ivan Mar 01 '18 at 16:37
  • @Ivan oh yes, you are right... it depends on the measure and the pushed measure is not the 'natural one' one needs in this case... – Fabian Werner Mar 01 '18 at 16:38
  • whuber, do you mean normalization? but then I map $n$-dim points into $n$-dim points which is in my case is exactly same in terms of cost function evaluation, since normalization does not change anything. – Ivan Mar 01 '18 at 16:41
  • @Xi'an, I looked at you suggestion 2 days ago and I look now, and I still can not make sense out of it. Can you maybe send me a link which may provide some theoretical background behind this method, so I could hopefully understand it? – Ivan Mar 05 '18 at 13:20
  • @Ivan, did my answer make sense? As you can see, there is no theory involved. Your question remains somewhat unclear as to which type of sampling you would consider acceptable. – Xi'an Mar 07 '18 at 17:43

1 Answers1

5

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

Yves
  • 4,313
  • 1
  • 13
  • 34
Xi'an
  • 90,397
  • 9
  • 157
  • 575
  • 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. – Ivan Mar 08 '18 at 10:57