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
    @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.$g$oogle.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