1
$\begingroup$

I have function values at each of the vertices of the hyper cube. What would be a natural interpolation of the function to each point on and inside the cube that can be written as a positive linear combination of polynomial (in the number of dimensions) number of vertices ? This is in context of lovasz extension of submodular functions.

Edit :

The vertices of the hypercube do not exhibit hyper-cubical symmetry. Instead the vertices correspond to the subsets of a set. For example the vertices (0,0,...0) and (1,1,1...1) are the null set and complete set respectively over a ground set $V$. What i want to understand is how to interpret the following proposed extension :

Let $c = (c(1), c(2), ... c(n))$ in $[0,1]^n$ and let $p_1> p_2 > ... > p_k$ be the distinct values in $\{c(1), c(2), ... c(n)\}$. Define $q_k = p_k$ and $q_j = p_j - p_{j+1}$ for $j = 1, 2, ... k-1$.
For $1 \le j \le k$ we let $U_j = \{ i | c(i) \ge p_j \}$. Define $f'$ as follows :

$$ f'(c) = (1- p_1)f(\phi) + \sum_{j=1}^{k} q_jf(U_j)$$

Think of each vertex of the hyper cube as being an indicator vector of a subset $U \subseteq V$, where $\left|{V}\right| = n$

The interpolation is as explained here

  • 0
    Divide the hypercube into simplices and perform barycentric interpolation within each simplex?2011-06-22
  • 0
    @Rahul: There is no natural division of the hypercube into simplices. This division would necessarily break the symmetry of the hypercube.2011-06-22
  • 0
    Your edit isn't self-contained; the notation $f(U_j)$ is explained in the link you provided in the comment under my answer but not in the question. The full context or at least the link should be in the question. Concerning the function itself: I wouldn't call this a "natural interpolation" -- for instance, the function values along the line from $(0,\dotsc,0)$ to $(1,\dotsc,1)$ are interpolated linearly using only those two values, which breaks the hypercubical symmetry, at least as far as the centre is concerned.2011-06-22
  • 1
    However, in the context that you took this from, there isn't really hypercubical symmetry, since the corners of the hypercube are identified with subsets of a set, so the corners $(0,\dotsc,0)$ and $(1,\dotsc,1)$ are distinguished as associated with the empty set and the full set. If this is the context you're interested, you should have provided it from the beginning; your original formulation only mentioned "the hypercube" without any distinction between the vertices.2011-06-22
  • 0
    @joriki I have edited the question to reflect the context. I am simply unable to interpret the significance of this interpolation.2011-06-22

1 Answers 1

1

There can be no such interpolation. Any interpolation that could reasonably claim to be "natural" would have to give the average of all vertices at the centre, and the number of all vertices is obviously more than polynomial in the dimension.

  • 0
    joriki please see the edit i have made to the question. I have added the proposed interpolation as explained here : http://www.google.co.in/url?sa=t&source=web&cd=1&ved=0CB0QFjAA&url=http%3A%2F%2Fwww.cs.illinois.edu%2Fclass%2Fsp10%2Fcs598csc%2FLectures%2FLecture21-22.pdf&ei=53oBToD7O8LqrAeBqpSGAw&usg=AFQjCNGCIYzA3oxbzgt911wv5BkhCYnCSg&sig2=l41qjtR6T_A9GQGdTV8QyA2011-06-22