4

Let me introduce what I need by giving an example which is not working:

n-sphere with radius 1 and respective hypercube with edges of length 2. The ratio reaches already in 10th dimension a level of less than 1%.

My question essentially is whether a geometric object G with following features exists:

  1. The hyper-cube containing G is canonically defined for all dimensions with edges of length L and center is the 0.

  2. G is contained in above hyper-cube for all dimensions.

  3. The ratio of the G's volume and the hyper-cubes volume is constant over all dimensions.

  4. Calculating whether a point chosen from the hyper-cube uniformly at random is contained in G is canonical. (in other words: the calculation can be written down as a single formula depending on the number of dimensions and of course L and the point)

  5. Any path along the surface of G is differentiable.

  6. The volume ratio should be either adjustable or between .2 and .8.

(point 5 is maybe not correctly formulated. I want to make sure that G is not "edgy"/"weird" (sorry for these terms). Maybe it is the same as when I request G to be Riemann integrable)

I need such an object to generate a sample data set from an arbitrary dimensional space to benchmark performance of SVMs (and other ML algorithms) over dimensionality of input space.

Raffael
  • 145
  • Wow, interesting question! – Newb Jan 31 '14 at 10:05
  • 1
    I'd go along this: inflate a sphere inside a hypercube. At some point you'll obtain a figure that is flat and touching the cube inside the square surfaces, locally a "hyper"cylinder near edges and something like a "hyper"sphere near vertices. Then you'll need to adjust all parameters to obtain the desired volume and derivability. – TZakrevskiy Jan 31 '14 at 10:35
  • What is the purpose of condition number 5? – ZKe Jan 31 '14 at 10:40
  • @Zackkenyon: to assure the object is shaped "pleasently" :) – Raffael Jan 31 '14 at 10:42
  • so like, a cube would qualify? – ZKe Jan 31 '14 at 10:45
  • @TZakrevskiy: you're welcome to put it into a formula. I get your idea, but I fear "adjust all parameters" dooms it non-canonical, plus I think it is quite unclear what those parameters actually are. – Raffael Jan 31 '14 at 10:45
  • @Zackkenyon: a cube is not pleasent in this case because it is too simple - it likely won't suit the ultimate purpose. In that sense, (5) not just assures a pleasent shape but also prevents a too trival shape. – Raffael Jan 31 '14 at 10:49

2 Answers2

2

The following is the idea put forward by TZakrevskiy in his comment: Fix $n\geq2$, let $C:=\{x\in{\mathbb R}^n\>|\>\|x\|_\infty\leq1$ be the hypercube of side length $2$, and let $B$ be the unit ball in ${\mathbb R}^n$. For $0<\epsilon<1$ the Minkowski sum $$G:=(1-\epsilon) C +\epsilon B$$ is a "rounded cube" with $C^1$-surface. There exists a famous formula for ${\rm vol}(G)$, but it is obvious that $${{\rm vol}(G)\over {\rm vol}(C)}>(1-\epsilon)^n\ ,$$ which can be made $>1-\delta$ for any given $\delta>0$.

There can be no question of "any path along the surface of $G$ being differentiable", for any $G$ proposed whatsoever. However one can say the following: Since the $G$ above has a $C^1$-surface it makes sense to consider differentiable curves on $\partial G$.

PS: I don't understand why you didn't like Will Jagy's answer, so that it was subsequently deleted.

TZakrevskiy
  • 22,980
Christian Blatter
  • 226,825
  • I don't know why Mr Jagy decided to delete his answer. My approach to the problem I try to solve behind the question is intuitive. Hence, and I am sorry for that, the answer has to get the idea of what I try to accomplish. And Mr Jagy's solution led to boxes taking up full axes within the cube. This solution might be the answer to the mathematical aspects I try my best to describe - but it doesn't serve the purpose of a useful sample space – Raffael Jan 31 '14 at 11:15
  • Q1: Is it possible to decide (effort no more than O(n)) whether for a vector g in G (eps given) there are two vectors c in C and b in B such that g = (1 - eps) * c + eps * b? In other words: is it easy to decide whether g in deed lies within G? How is it done? – Raffael Jan 31 '14 at 12:01
  • Q2: What is the formula to calculate the volume of G = (1-eps) * C + eps * B? – Raffael Jan 31 '14 at 12:02
  • @Яaffael $x\in G$ $\iff$ ($x\in (1-\epsilon)C$ or $dist (x,\partial (1-\epsilon)C)\le \epsilon$). The first term is calculated by at most $O(n)$, the second one can be made $O(n)$, too. – TZakrevskiy Jan 31 '14 at 12:19
1

The space defined by the solutions of the following inequality seems to do the trick (d being the dimensions of the space):

$$1-(\sum_{i=1}^{d}x_i^{2d})^{1/d} \geq \frac{1}{d}$$

The space for d=2 and d=3 looks "pleasant":

enter image description here enter image description here

The ratio of the solution space volume and the cube also seems to be quite consistent at 0.5:

enter image description here

library(rgl)

vol <- function(d) {    
    p <- function(x) 1 - sum(x^(2*d))^(1/d)
    g <- matrix(runif(d*100000, -1, 1), ncol=d)
    s <- apply(g, 1, p)
    v <- ifelse(s >= 1/d, 1, -1)

    if(d==2) plot(g[v==1,], xlim=c(-1,1), ylim=c(-1,1))
    if(d==3) plot3d(g[v==1,], xlim=c(-1,1), ylim=c(-1,1), zlim=c(-1,1))

    sum(v == 1) / nrow(g)
}

ratios <- sapply(1:100,vol)

plot(ratios, xlab="dimension")
Raffael
  • 145