10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Taeke de Haan Jun 22 '18 at 11:47
  • 2
    $\begingroup$ There are lots of papers, but most are behind paywall: link.springer.com/article/10.1007/s00184-011-0360-x or see google.com/… $\endgroup$ – kjetil b halvorsen Jun 22 '18 at 11:55
  • 3
    $\begingroup$ "Uniform" with respect to what volume metric? After all, if you are using a $p$-ball, why would Euclidean volume be of interest? $\endgroup$ – whuber Jun 22 '18 at 13:27
  • $\begingroup$ @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. $\endgroup$ – Taeke de Haan Jun 22 '18 at 14:51
  • 1
    $\begingroup$ 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. $\endgroup$ – Taeke de Haan Jun 22 '18 at 16:30
5
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ For completeness, could you tell what is $G$ in your answer? $\endgroup$ – Stéphane Laurent Jun 23 '18 at 9:46
  • $\begingroup$ It has been updated $\endgroup$ – Taeke de Haan Jun 23 '18 at 12:22
  • 2
    $\begingroup$ 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}$$ $\endgroup$ – Martijn Weterings Jun 23 '18 at 12:40
  • $\begingroup$ @MartijnWeterings Thanks a lot, it has been updated. $\endgroup$ – Taeke de Haan Jun 26 '18 at 21:10
  • $\begingroup$ Thanks. For info, there is a sampler of this distribution in the R package pgnorm. $\endgroup$ – Stéphane Laurent Jul 20 '18 at 9:31
3
$\begingroup$

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.

simulation picking 20000 values uniformly distributed

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.

$\endgroup$
  • 1
    $\begingroup$ Could you elaborate on how you conclude the unit vectors are uniformly distributed? BTW, I believe you want to take the $p$th root. $\endgroup$ – whuber Jun 22 '18 at 13:29
  • 1
    $\begingroup$ 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}$ $\endgroup$ – Taeke de Haan Jun 22 '18 at 14:43

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.