Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer
joriki please see the edit i have made to the question. I have added the proposed interpolation as explained here :… – AnkurVijay Jun 22 '11 at 5:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.