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

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.

• The answer can be found here for a sphere with n dimensions using Euclidean distance (p = 2) math.stackexchange.com/questions/87230/… I'm however still not sure how to use this for different p-norms, can I simply change the used Euclidean distance in a different relation for the distance? – Taeke de Haan Jun 22 '18 at 11:47
• There are lots of papers, but most are behind paywall: link.springer.com/article/10.1007/s00184-011-0360-x or see google.com/… – kjetil b halvorsen Jun 22 '18 at 11:55
• "Uniform" with respect to what volume metric? After all, if you are using a $p$-ball, why would Euclidean volume be of interest? – whuber Jun 22 '18 at 13:27
• @whuber I am honestly not sure sure since this is not clearly stated in the assignment, but I would expect in p-norm since any other metric seems to be arbitrary in this case. – Taeke de Haan Jun 22 '18 at 14:51
• The problem comes from a Machine Learning assignment; "The problem is a two-class classification problem in 204 dimensions. The small labeled training set has a size of 50 samples per class. The unlabeled data provides 20,000 additional samples. These samples have, however, undergone a corruption of some sort. The only additional information we have regarding this corruption, is that it is additive uniform noise and that the noise comes from a fixed p-norm ball, $||x||_p \leq r$, where both $p$ and the radius $r$ are unknown." I need to get the lowest error rate on the unlabeled data. – Taeke de Haan Jun 22 '18 at 16:30

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}$

• For completeness, could you tell what is $G$ in your answer? – Stéphane Laurent Jun 23 '18 at 9:46
• It has been updated – Taeke de Haan Jun 23 '18 at 12:22
• G is the generalized Gaussian distribution (with a different power in the exponent $e^{-|x|^p}$ instead of just $p=2$). This will make the distribution for the vector $\mathbf{x}$, composed of multiple independent generalized gaussian distributed variables $x_i$, which is the product of the single pdfs, dependent on the p-norm. $$f(\mathbf{x}) \propto e^{-\vert \mathbf{x} \vert_p^p}$$ – Martijn Weterings Jun 23 '18 at 12:40
• @MartijnWeterings Thanks a lot, it has been updated. – Taeke de Haan Jun 26 '18 at 21:10
• Thanks. For info, there is a sampler of this distribution in the R package pgnorm. – Stéphane Laurent Jul 20 '18 at 9:31

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.

• Could you elaborate on how you conclude the unit vectors are uniformly distributed? BTW, I believe you want to take the $p$th root. – whuber Jun 22 '18 at 13:29
• Thanks for your help, I found the full solution here: 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 indipendent random real scalars E_i = G(1/p, p) 2) construct the vector x of components s_i * E_i, where E_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}$ – Taeke de Haan Jun 22 '18 at 14:43