Lovasz Extension Intuition

Question

I am confused by the definition of Lovasz extension. The problem is I don't get the intuition behind the definition. In addition, Lovasz extension can be defined in different ways I don't see that these definition are indeed equivalent. The following is the definition and few my question with the current level of understanding.

For a function $f:\{0,1\}^N \rightarrow R, f^L : [0,1]^N \rightarrow R$ is defined by

$f^L(x) = \sum_{i=0}^{n} \lambda_if(S_i)$

where $\varnothing =S_0 \subset S_1 \subset S_2 \subset ... \subset S_n$ is a chain such that $\sum_{}^{} \lambda_i 1_{S_i}=x$ and $\sum_{}^{} \lambda_i=1, \lambda_i \geq 0$

An equivalent way to define the Lovasz extension is :$f^L(x) = E[f(\{i:x_i > \lambda\})]$, where $\lambda$ uniformly random in $[0,1]$

Question 1. Intuition. I don't get the intuition. $f$ is some valuation of function defined on all subsets of $N$ elements. $f^L(x)$ is the similar for $f$ but as input $x$ can take fractional values of elements.

Question 2: What the following function means $\sum_{}^{} \lambda_i 1_{S_i}=x$? In particular I don't get what's $1_{S_i}$ means. It looks like a linear combination of $\lambda_i$ and a magic stuff $1_{S_i}$ (please, what does it mean?) such that as result we get the input which is the vector of $N$ elements with fractional values.

Question 3: Equivalent definition is $f^L(x) = E[f(\{i:x_i > \lambda\})]$, it's expected value, does it mean I can rewrite it as follows $f^L(x) = x_if(i), \forall x_i > \lambda$, it this the same $\lambda$ as in the first definition.

Question 4: the requirement $\varnothing =S_0 \subset S_1 \subset S_2 \subset ... \subset S_n$ seems rather strange, what the goal of this requirement.

Answer 1

An input to $f^L$ is a point in the $N$-dimensional unit cube $[0,1]^N$. An input to $f$ is one of the $2^N$ corners of this cube. So $f$ attaches a number $f(s)$ to each corner $s$, and the goal is to "intelligently" or at least "reasonably" extend this to attach a number to every point in the whole cube.

Lovász takes advantage of the fact that this cube can be "reasonably" subdivided into $N!$ simplices. (An $N$-dimensional simplex in Euclidean $N$-dimensional space is, by definition, the convex hull of $N+1$ points that don't all lie in an $(N-1)$-dimensional hyperplane.) I'll describe the subdivision below, and point out that each of the simplices has its $N+1$ corners among the corners of the cube, but first let me get to the main point of the construction. Each point in a simplex is a weighted average of the corners of that simplex. So if you have numbers $f(s)$ attached to the corners $s$, then it is reasonable to attach, to any weighted average $x$ of the corners $s$, the corresponding weighted average of the $f$-values. That is, for any weights $\lambda_i$, you would define $f(\sum_i\lambda_is_i)$ to be $\sum_i\lambda_if(s_i)$. As in any weighted average, the weights $\lambda_i$ should be non-negative real numbers that add up to $1$. (A faster but less explicit way to say the same thing is to define $f$ to be linear on each of the simplices and to agree with the given values at the corners of the simplex.)

I still have to tell you what these simplices are and how they fit together to make the cube. For most points $x$ in the cube $[0,1]^N$, the $N$ coordinates $x_1,\dots, x_N$ are all distinct. Let me temporarily consider only those points. For any such $x$, we can list its $N$ coordinates in decreasing order, say $x_{\sigma(1)}>x_{\sigma(2)}>\dots>x_{\sigma(N)}$ for some permutation $\sigma(1),\sigma(2),\dots,\sigma(N)$ of $\{1,2,\dots,N\}$. For any fixed permutation $\sigma$, all the points $x$ whose coordinates are ordered according to that $\sigma$ constitute (the interior of) one of the desired simplices.

So far, I've ignored the points $x$ that have two or more coordinates equal; these points will be on the boundary of two or more of these simplices.

The corners of the simplex corresponding to the permutation $\sigma$ are the $N+1$ points obtained as follows. Pick some $k$ in the range $0\leq k\leq N$ and let $s\in\{0,1\}$ be the point with $s_{\sigma(i)}=1$ for $0<i\leq k$ and $s_{\sigma(i)}=0$ for $k<i\leq N$. These $N+1$ points $s$ (one for each choice of $k$) are what were called $S_0,\dots,S_N$ in the question. that notation tacitly identifies an $N$-component vector $s$ of $0$'s and $1$'s (i.e., an element of $\{0,1\}^N$) with a subset of $\{1,2,\dots,N\}$, namely the set $\{i:s_i=1\}$. The notation $1_S$ used in the question means the vector that corresponds to the subset $S$ of $\{1,2,\dots,N\}$.