Generate uniform noise from a p-norm ball ($||x||_p \leq r$)

Question

I am trying to write a function which generates uniformly distributed noise which comes from a p-norm ball of $n$ dimensions:

\begin{equation} ||x||_p \leq r \end{equation}

I found possible solutions for circles ($p = 2$) (http://mathworld.wolfram.com/DiskPointPicking.html), however I have trouble extending this for different values of $p$.

I have tried doing it by just drawing a random sample from a uniform distribution, and redrawing when it does not meet the given constraint. However besides it being an ugly solution it also becomes computationally infeasible for high dimensions.

Answer 1

I found the full solution in a paper as suggested by kjetil b halvorsen (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=758215). I honestly have trouble understanding the math behind it, but the eventual algorithm is fairly simple. if we have $n$ dimensions, a radius $r$ and norm $p$ than:

1) generate $n$ independent random real scalars $\varepsilon_i = \bar{G}(1/p, p)$, where $\bar{G}(\mu, \sigma^2)$ is the Generalized Gaussian distribution (with a different power in the exponent $e^{−|x|^p}$ instead of just $p=2$)

2) construct the vector $x$ of components $s_i * \varepsilon_i$, where $s_i$ are independent random signs

3) Generate $z = w^{1/n}$, where $w$ is a random variable uniformly distributed in the interval [0, 1].

4) return $y = r z \frac{x}{||x||_p}$

Answer 2

Using homogeneously distributed multivariate variables

Taeke provides a link to an article which the text below makes more intuitive by explaining specifically 2-norm and 1-norm cases.

2-norm $\Vert x \Vert_2 \leq r$

sample direction

You can use this result http://mathworld.wolfram.com/HyperspherePointPicking.html

A multivariate Gaussian distributed variable $X$ (with identity covariance matrix) depends only on the distance, or sum of squares.

$$f(X_1,X_2,...,X_n) = \prod_{1\leq i \leq n} \frac{1}{\sqrt{2\pi}}e^{\frac{1}{2}x_i^2} = \frac{1}{\sqrt{2\pi}}e^{\frac{1}{2}\sum_{1 \leq i \leq n} x_i^2} $$

Thus $\frac{X}{\Vert X \Vert_2}$ is uniformly distributed on the surface of the n-dimensional-hypersphere.

---

sample distance

To complete you only need to sample the distance, to change the homogeneous distribution on the sphere to a homogeneous distribution in a ball. (which is more or less similar as your linked example for disk point picking)

If you would simply sample $r$ as a uniform distribution then you would have a relatively higher density near the center (the volume scales as $r^n$ so a fraction $r$ of the points would end up in a volume $r^n$, which is more dense near the center and would not mean a uniform distribution)

If instead you use the $n$-th root of a variable sampled from a uniform distribution, then you get an even distribution.

1-norm $\Vert x \Vert_1 \leq r$

direction

In this case you sample $X$ from the Laplace distribution instead of the Gaussian distribution and divide by the 1-norm. The $\frac{X}{\vert X \vert_1}$ is uniformly distributed on the n-dimensional 1-norm sphere.

I have no formal proof, just intuition

^{(since the pdf is independent from position, you will expect for any infinitesimal area/volume with the same 1-norm to have the same probability $f(x) dV$ and when you collapse this to the unit surface the same $f(x) dA$)}

but testing with simulations looks good.

library(rmutil)
x <- abs(rlaplace(20000))
y <- abs(rlaplace(20000))
z <- abs(rlaplace(20000))
rn <- abs(x)+abs(y)+abs(z)

xi <- (x/rn)
yi <- (y/rn)
zi <- (z/rn)
plot(sqrt(0.5)*(xi-yi),
     sqrt((0.5-0.5*(xi+yi))^2+zi^2),
     pc=21,bg=rgb(0,0,0,0.02), col=rgb(0,0,0,0),cex=1)

distance

The distance goes similar as with the 2-norm case (the volume still scales as $r^n$).

p-norm $\Vert x \Vert_p \leq r$

In this case, if you wish to follow the same principle, you would need to sample from distributions with $f(x) \propto e^{\vert x \vert^p}$ (I hypothesize). These are generalized normal distributions and probably relate to the distribution $G()$ mentioned by Taeke.