[math-fun] Spikey Spheres
http://www.penzba.co.uk/cgi-bin/PvsNP.py?SpikeySpheres " ... I've recently been working on an optimisation problem, and I've come to realise that I can consider it as wandering around on a smooth landscape in 1800 dimensions. Strange number, I know, but that's the way it's worked out. The problem is that the usual visualisation of hill-climbing, or hill-descending, is that you're on a gently undulating vista, and that some directions are up, some are down, and it's easy to decide which is which. You write the code, set off, and somehow the system never finds a good solution. Part of the problem is that there is simply a lot of space to explore. If you discretise space and have 1000 places to be in each dimension, 2 dimensions gives you a million places to be. That's not so bad. 1800 dimensions gives you 10^5400 places to be. That's not good. You definitely need to move in moderately large strides, and then hone your solution by using binary chop or similar techniques. But it's worse than that. The problem is that the error function may be "smooth," but your intuition of what this means is wrong. ... " --- co-chair http://ocjug.org/
They're not exactly spiky in any way that spheres shouldn't be. They're only spiky when viewed along one of the orthogonal axes. Our intuition about spheres from low dimensions (like 3 dimensions) is pretty much useless beyond about 5 or 6 dimensions. This visualization paradox comes up a lot in the sphere packing problem, related to communication codes (in which the goal is to find a set of unit-length vectors that are as nearly equidistant as possible, to be used as an error-correcting code; the vectors are more or less distant according to how close they are along each of the N dimensions. These vectors are typically encoded or modulated and the coordinates end up being transmitted serially. If a vector differs along at least 3 dimensions, then a single error can be "corrected" by finding the closest standard vector to the received nonstandard vector.). Anyway, you might want to look into the published work on the sphere packing and kissing number problems. These are less specific than the lattice packing problem, but related. Some use numerical techniques, most exploit any known symmetries of the problem, and most are working in pretty high numbers of dimensions. On Sat, Oct 30, 2010 at 05:33, Ray Tayek <rtayek@ca.rr.com> wrote:
http://www.penzba.co.uk/cgi-bin/PvsNP.py?SpikeySpheres
" ... I've recently been working on an optimisation problem, and I've come to realise that I can consider it as wandering around on a smooth landscape in 1800 dimensions. Strange number, I know, but that's the way it's worked out. [...] Part of the problem is that there is simply a lot of space to explore. [...] 1800 dimensions gives you 10^5400 places to be. [...] But it's worse than that. The problem is that the error function may be "smooth," but your intuition of what this means is wrong. ... "
-- Robert Munafo -- mrob.com Follow me at: mrob27.wordpress.com - twitter.com/mrob_27 - youtube.com/user/mrob143 - rilybot.blogspot.com
participants (2)
-
Ray Tayek -
Robert Munafo