Erzeugen Sie ein gleichmäßiges Rauschen aus einer p-Norm-Kugel (

10

Ich versuche eine Funktion zu schreiben, die gleichmäßig verteiltes Rauschen erzeugt, das von einem p-Norm-Ball mit n Dimensionen stammt:

||x||pr

Ich habe mögliche Lösungen für Kreise gefunden ( p=2 ) ( http://mathworld.wolfram.com/DiskPointPicking.html ), aber ich habe Probleme, diese für verschiedene Werte von p .

Ich habe versucht, dies zu tun, indem ich nur eine Zufallsstichprobe aus einer gleichmäßigen Verteilung gezogen und neu gezeichnet habe, wenn sie die angegebene Einschränkung nicht erfüllt. Abgesehen davon, dass es eine hässliche Lösung ist, wird es auch für hohe Dimensionen rechnerisch unmöglich.

Taeke de Haan
quelle
1
Die Antwort finden Sie hier für eine Kugel mit n Dimensionen unter Verwendung des euklidischen Abstands (p = 2) math.stackexchange.com/questions/87230/…. Ich bin mir jedoch immer noch nicht sicher, wie ich dies für verschiedene p-Normen verwenden soll einfach den verwendeten euklidischen Abstand in einem anderen Verhältnis für den Abstand ändern?
Taeke de Haan
2
Es gibt viele Papiere, aber die meisten stehen hinter Paywall: link.springer.com/article/10.1007/s00184-011-0360-x oder siehe google.com/…
kjetil b halvorsen
3
"Uniform" in Bezug auf welche Volumenmetrik? Wenn Sie einen Ball verwenden, warum sollte dann das euklidische Volumen von Interesse sein? p
whuber
@whuber Ich bin mir ehrlich gesagt nicht sicher, da dies in der Zuordnung nicht klar angegeben ist, aber ich würde in p-Norm erwarten, da jede andere Metrik in diesem Fall willkürlich zu sein scheint.
Taeke de Haan
1
Das Problem ergibt sich aus einer maschinellen Lernaufgabe. "Das Problem ist ein Zwei-Klassen-Klassifizierungsproblem in 204 Dimensionen. Der kleine beschriftete Trainingssatz hat eine Größe von 50 Stichproben pro Klasse. Die unbeschrifteten Daten liefern 20.000 zusätzliche Stichproben. Diese Stichproben haben jedoch eine Art Beschädigung erfahren Die einzige zusätzliche Information, die wir bezüglich dieser Verfälschung haben, ist, dass es sich um ein additives gleichmäßiges Rauschen handelt und dass das Rauschen von einer festen p-Norm-Kugel , bei der sowohl p als auch der Radius r unbekannt sind. " Ich muss die niedrigste Fehlerrate für die unbeschrifteten Daten erhalten. ||x||prpr
Taeke de Haan

Antworten:

5

Ich fand die vollständige Lösung in einem Artikel, wie von kjetil b halvorsen ( https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=758215 ) vorgeschlagen. Ich habe ehrlich gesagt Probleme, die Mathematik dahinter zu verstehen, aber der letztendliche Algorithmus ist ziemlich einfach. Wenn wir Dimensionen haben, einen Radius r und eine Norm p als:nrp

nεi=G¯(1/p,p)G¯(μ,σ2)e|x|pp=2

xsiεisi

z=w1/nw

y=rzx||x||p

Taeke de Haan
quelle
2
G
Es wurde aktualisiert
Taeke de Haan
2
e|x|pp=2xxi
f(x)e|x|pp
@MartijnWeterings Vielen Dank, es wurde aktualisiert.
Taeke de Haan
Vielen Dank. Zur Information gibt es einen Sampler dieser Distribution im R-Paket pgnorm .
Stéphane Laurent
3

Verwendung homogen verteilter multivariater Variablen

Taeke bietet einen Link zu einem Artikel, den der folgende Text intuitiver macht, indem er speziell 2-Norm- und 1-Norm-Fälle erklärt.

x2r

Probenrichtung

Sie können dieses Ergebnis http://mathworld.wolfram.com/HyperspherePointPicking.html verwenden

Eine multivariate verteilte Gaußsche Variable (mit Identitätskovarianzmatrix) hängt nur von der Entfernung oder der Summe der Quadrate ab.X

f(X1,X2,...,Xn)=1in12πe12xi2=12πe121inxi2

Somit ist gleichmäßig auf der Oberfläche der n-dimensionalen Hypersphäre verteilt.XX2


Probenabstand

Um dies zu vervollständigen, müssen Sie nur den Abstand abtasten, um die homogene Verteilung auf der Kugel in eine homogene Verteilung in einer Kugel zu ändern. (Dies ist mehr oder weniger ähnlich wie Ihr verknüpftes Beispiel für die Auswahl von Plattenpunkten.)

Wenn Sie einfach als gleichmäßige Verteilung abtasten würden, hätten Sie eine relativ höhere Dichte in der Nähe des Zentrums (das Volumen skaliert als sodass ein Bruchteil der Punkte in einem Volumen enden würde , das dichter ist in der Nähe des Zentrums und würde keine gleichmäßige Verteilung bedeuten)rrnrrn

Wenn Sie stattdessen die te Wurzel einer Variablen verwenden, die aus einer gleichmäßigen Verteilung entnommen wurde, erhalten Sie eine gleichmäßige Verteilung.n

1-Normx1r

Richtung

In diesem Fall nehmen Sie aus der Laplace-Verteilung anstelle der Gaußschen Verteilung und dividieren durch die 1-Norm. Das ist gleichmäßig auf der n-dimensionalen 1-Norm-Kugel verteilt.XX|X|1

Ich habe keinen formalen Beweis, nur Intuition

(Da das PDF unabhängig von der Position ist, erwarten Sie, dass jeder infinitesimale Bereich / Volumen mit derselben 1-Norm dieselbe Wahrscheinlichkeit und wenn Sie dies auf die Einheitsoberfläche reduzieren, dasselbe )f(x)dVf(x)dA

Aber das Testen mit Simulationen sieht gut aus.

Simulation, die 20000 Werte gleichmäßig verteilt auswählt

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)

Entfernung

Der Abstand verläuft ähnlich wie im Fall der 2-Norm (das Volumen skaliert immer noch als ).rn

p-Normxpr

In diesem Fall müssten Sie, wenn Sie dem gleichen Prinzip folgen möchten, aus Verteilungen mit (ich nehme an) eine Stichprobe . Dies sind verallgemeinerte Normalverteilungen und beziehen sich wahrscheinlich auf die von Taeke erwähnte Verteilung .f(x)e|x|pG()

Sextus Empiricus
quelle
1
Könnten Sie näher erläutern, wie Sie zu dem Schluss kommen, dass die Einheitsvektoren gleichmäßig verteilt sind? Übrigens, ich glaube, Sie wollen die te Wurzel schlagen. p
whuber
1
Vielen Dank für Ihre Hilfe. Die vollständige Lösung habe ich hier gefunden: ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=758215 ). Ich habe ehrlich gesagt Probleme, die Mathematik dahinter zu verstehen, aber der letztendliche Algorithmus ist ziemlich einfach. Wenn wir Dimensionen haben, erzeugen ein Radius und eine Norm als: 1) n unabhängige unabhängige reelle Skalare E_i = G (1 / p, p) 2) konstruieren den Vektor x der Komponenten s_i * E_i, wobei E_i unabhängige Zufallszeichen sind 3) Erzeugen Sie , wobei eine Zufallsvariable ist, die gleichmäßig im Intervall [0, 1] verteilt ist. 4) returnr p z = w 1 / n w y = r z xnrpz=w1/nwy=rzx||x||p
Taeke de Haan