# Decomposition of any point in the unit hypercube as a positive linear combination of polynomial number of vertices

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

-
Divide the hypercube into simplices and perform barycentric interpolation within each simplex? – Rahul Jun 22 '11 at 4:49
@Rahul: There is no natural division of the hypercube into simplices. This division would necessarily break the symmetry of the hypercube. – joriki Jun 22 '11 at 4:55
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. – joriki Jun 22 '11 at 7:31
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. – joriki Jun 22 '11 at 7:34
@joriki I have edited the question to reflect the context. I am simply unable to interpret the significance of this interpolation. – AnkurVijay Jun 22 '11 at 7:52