Communications of the ACM

Research highlights

Technical Perspective: A High-Dimensional Surprise

By Rocco A. Servedio
Communications of the ACM, October 2012, Vol. 55 No. 10, Page 89
10.1145/2347736.2347756
Comments

High-dimensional space is a counterintuitive place, where natural geometric intuitions from the familiar three-dimensional world may lead us badly astray. As a simple example consider the Earth, which has a radius of about 3,950 miles (let's pretend it is a perfect sphere). What fraction of the Earth's surface lies within 1/100 of its radius, that is, within 39.5 miles, from the equator? A reasonable guess would be "about 1/100," and that is almost exactly correct. Now let's think high-dimensionally: what fraction of the surface of a d-dimensional sphere lies within 1/100 of its radius from its equator? Again one might guess "about 1/100," but this is wildly incorrect: all but an exponentially small (in terms of d) fraction of the d-dimensional sphere's surface lies within 1/100 of its radius from the equator. Strange as it seems, virtually all the real estate on d-dimensional Earth is in the tropics!

The challenges of dealing with high-dimensional space are familiar to researchers in fields like machine learning and combinatorial optimization, where the "curse of dimensionality" arises often. Tasks that are easy in few dimensions—finding a simple curve to fit data points, computing the volume of a region—can become frustratingly difficult or even provably intractable (assuming P!=NP) in high-dimensional space. Yet sometimes the tables are turned, and things that seem difficult or impossible based on our low-dimensional intuition can, near-magically, become possible in high dimension. The following paper describes such a situation, where a clever construction inspired by ideas from computational complexity theory proves the existence of what seems like a too-good-to-be-true high-dimensional object.

The authors reveal an unexpected connection between spheres and cubes and construct a new geometric object that has some of the most fundamental properties of both shapes. Turning first to cubes, they are the canonical shape that can be used to "tile space" according to a regular grid-like lattice leaving no holes or unfilled space (think of slicing a block of cheese into cubes). Of course a simple cube is not the only shape that can do this—for example, adding bumps to the top and carving matching divots into the bottom of a cube yields a different, Lego-like shape that also fits perfectly with itself to fill space with no holes under a grid-like tiling. Any shape that can do this is called a "cubical tile."

A sphere is certainly not a cubical tile, since a grid-like pattern of 3D spheres leaves a lot of empty space unfilled. In higher dimensions spheres do even worse: the fraction of unfilled space becomes exponentially larger (as a function of d) than the fraction actually filled by the spheres. But spheres reign supreme for a different property: they have the smallest surface-area-to-volume ratio of any shape, in three or any number of dimensions. (This is one reason why water towers have their familiar round shape—small surface area means less building material and more uniform water temperature.) In fact, while a d-dimensional cube of volume 1 has surface area 2d, a d-dimensional sphere of volume 1 has surface area only about 4.13, which is much smaller in high dimensions.

So cubes can tile space perfectly but have high surface-area-to-volume ratio, while spheres have the lowest possible surface-area-to-volume ratio but cannot tile space. The authors show that in high-dimensional space it is possible to get the best of both worlds, by proving that there exists a d-dimensional "spherical cube." This counterintuitive object is a cubical tile (that is, a shape that tiles space perfectly like the cube), but has surface-area-to-volume ratio very nearly as small as that of the sphere: roughly 12.6, that is, the same as the sphere up to a small constant factor!

Why should we care? There are at least three reasons. First, as described in the paper, their geometric construction yields a highly noise-resistant randomized procedure for rounding high-dimensional data points to integer values; such a procedure could be useful in many scenarios. Second, the authors also obtain the best surface-area-to-volume ratio of any 3D cubical tile, improving on a construction of Choe¹ from 1989; this could have practical consequences in material science, fabrication, or related areas. Third, their work is based on a surprising connection to recent deep results on hardness amplification in computational complexity theory;² their article provides a fascinating perspective on this area, and a great illustration of how ideas from one branch of mathematics can have unexpected yet tremendous utility in a completely different area. Finally, there is the sheer "wow, I wouldn't have thought that's possible!" factor—it is just plain neat that you can have a "spherical cube" in high dimensions.

Many important questions remain unanswered, both in the complexity-theoretic foundations of Kindler et al.'s result and in the specifics of their geometric construction. A randomized algorithm, not a particularly efficient one, constructs their cubical tile; natural goals are to come up with a more efficient randomized construction, or ideally even an explicit construction that does not use randomness. We can reasonably hope that future work—perhaps again informed by perspectives and ideas from complexity theory—will provide more insights into the mysteries and surprises of high-dimensional geometry.

Back to Top

Back to Top

The Digital Library is published by the Association for Computing Machinery. Copyright © 2012 ACM, Inc.

---

No entries found