5 ms·
A note about the rejection method: in high dimensions, this becomes very expensive. This is because the volume of a ball inscribed in a unit cube goes to zero (
by woopwoop 8y ago
A note about the rejection method: in high dimensions, this becomes very expensive. This is because the volume of a ball inscribed in a unit cube goes to zero (very quickly) as the dimension goes to infinity, so you start rejecting points with high probability.
- Pxtl 8y agoI think that might be premature optimization to worry about finding random points in an n-dimensional hypersphere where n is a huge number.
- woopwoop 8y agoSure, but if you can't prematurely optimize in HN comments, when can you?
- tantalor 8y agoNo, n does not need to be huge, n=8 is high enough.
- Retric 8y agoIn this context 8 is a huge number.
- cultus 8y agoNot at all. There are plenty of circumstances in all kinds of numerics where one would want points on the sphere in high dimensions. It's not just a geometric object that has limited practical value for d>3. It is the set of points where the norm is unity, which is a pretty fundamental concept in all sorts of places.
- Retric 8y agoNot as part of a graphic's library. You might want to do 4d or 5d. But past that is very unlikely. In terms of actually solving to proble you just want a vector random distance and a function that to map random distance to actual distance. But if you never deal in 6+ dimensions that's a waste of time.
- cultus 8y agoWell, not in graphics libraries obviously, but it comes up quite a bit in other areas. Vectors with a norm of unity are just a fundamentally important set.
- tantalor 8y agoWho said anything about graphics?
- Retric 8y ago> While working through Peter Shirley’s Ray Tracing in One Weekend (http://in1weekend.blogspot.com/2016/01/ray-tracing-in-one-weekend.html http://in1weekend.blogspot.com/2016/01/ray-tracing-in-one-we...) Which is where that method was used.
- CamTin 8y agoOptimizing for anything more (or less) than three dimensions is premature.
- talltimtom 8y agoHi boss, we didn’t move those boxes, because the crane only carries up to 8 tons, and the boxes weigh 3, so we’ve started building a new crane system instead that will scale to lift arbitrarily large weights. I’ll probably be a couple of years before we get to actually moving the boxes. When your problem is n=3, anything larger than 3 is “huge”.
- charmides 8y agoIt is definitely an interesting problem how to sample uniformly from the set of n-dimensional vectors with an L2-norm smaller or equal to 1. I am sure that it has practical applications, too. Also, nobody said that n has to be huge.
- goodside 8y agoThis is not true! Nearly all of the hypervolume of a high-dimensional n-ball is located near its surface. A popular way of stating this is "If you peel a high-dimensional orange, there will be almost nothing left." The ratio of "rind" to "pulp" increases very, very quickly. A good intuition for why this happens is that the distance from the center of an n-dimensional hypercube to any of its corners is `r * sqrt(n)`, but the distance from the center of a ball to its surface is always just `r`. So if `r` is fixed, and `n` keeps increasing, the corners get "spikier" and farther from the center. Very quickly, almost all of the hypervolume of a hypercube is located in these remote corners, and almost none of it is in the ball at the center. See https://en.wikipedia.org/wiki/Curse_of_dimensionality https://en.wikipedia.org/wiki/Curse_of_dimensionality
- drb91 8y agoSeems to me it’s still premature optimization if you expect to use this primarily for low values of n (eg three).
- goodside 8y agoThe comment I was replying to stated that n was a "huge number", presumably bigger than 3.
- Dylan16807 8y agoI'm pretty sure you're reading it wrong. I interpret the comment as saying "it's premature to worry about (finding points in n dimensions where n is large)". This interpretation implies n is not large. Not "it's (premature to worry about finding points in n dimensions) where n is large". This interpretation implies n is large, but that you don't care.
- acjohnson55 8y agoSee also https://en.m.wikipedia.org/wiki/Curse_of_dimensionality https://en.m.wikipedia.org/wiki/Curse_of_dimensionality
- deleted 8y ago[deleted]
- kovek 8y agoIs there a shape that resembles a sphere (not a cube and not a point) but in higher dimensions will take the same relative volume as in lower dimensions such that this rejection probability stays the same?
- deleted 8y ago[deleted]
- dexen 8y agoI guess there's a new generation of cryptographic primitives implied by your assertion - given a parametric high-dimensional unit sphere, ...