Genera ruido uniforme a partir de una bola de norma p ($||x||_p \leq r$)

Question

Estoy tratando de escribir una función que genera uniformemente distribuida, el ruido que viene de un p-norma bola de $n$ dimensiones:

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

He encontrado las soluciones posibles para los círculos ($p = 2$) (http://mathworld.wolfram.com/DiskPointPicking.html), sin embargo tengo el problema se extiende la presente para diferentes valores de $p$.

He intentado hacerlo por sólo dibujar una muestra aleatoria de una distribución uniforme, y volver a dibujar cuando no cumple con el dado de restricción. Sin embargo, además de ser un feo solución también se vuelve computacionalmente imposible de altas dimensiones.

Answer 1

He encontrado la solución completa en un papel como se sugiere por kjetil b halvorsen (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=758215). Honestamente tengo problemas para entender las matemáticas detrás de ella, pero la eventual algoritmo es bastante simple. si tenemos $n$ dimensiones, un radio de $r$ y norma $p$ que:

1) generar $n$ independiente aleatoria real escalares $\varepsilon_i = \bar{G}(1/p, p)$ donde $\bar{G}(\mu, \sigma^2)$ es la generalización de la distribución de Gauss (con un poder diferente en el exponente $e^{−|x|^p}$, en lugar de sólo $p=2$)

2) construir el vector $x$ de los componentes de la $s_i * \varepsilon_i$ donde $s_i$ son independientes al azar signos

3) Generar $z = w^{1/n}$ donde $w$ es una variable aleatoria uniformemente distribuida en el intervalo [0, 1].

4) devolución de $y = r z \frac{x}{||x||_p}$

Answer 2

El uso de homogéneamente distribuido multivariante de las variables

Taeke proporciona un enlace a un artículo que el texto a continuación se hace más intuitiva explicando específicamente 2-norma y 1-norma de los casos.

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

ejemplo de dirección

Usted puede utilizar este resultado http://mathworld.wolfram.com/HyperspherePointPicking.html

Un multivariante Gaussiano distribuido variable $X$ (con la identidad de la matriz de covarianza) sólo depende de la distancia, o la suma de los cuadrados.

$$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()$ mencionado por Taeke.