12
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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\}$.

$\endgroup$
4
  • $\begingroup$ The simplices intersect right? Why is the map well defined then? $\endgroup$ – roi_saumon Aug 2 '20 at 18:35
  • $\begingroup$ @roi_saumon Any point $x$ that's in two or more of these simplices is on the boundary of each of them. At such a point, each of those simplices will produce a value of $f^L(x)$, but all those values will agree. The reason is that the corners that are in one simplex but not in another will have weight $0$ at $x$, so both values of $f^L(x)$ will be weighted averages of the $f(s)$ values at only the vertices of the lower-dimensional face that contains $x$. $\endgroup$ – Andreas Blass Aug 2 '20 at 19:43
  • $\begingroup$ All right. I was confused by drawing a picture for $[0,1]^3$... But actually why is it the same as $f^L(x) = E[f(\{i:x_i \lambda\})]$ though? $\endgroup$ – roi_saumon Aug 2 '20 at 20:53
  • $\begingroup$ The sets obtained from $ \{i: x_i > \lambda \} $ are the corners of the simplex. $x$ is a convex combination of those corners, which means that you can treat the contribution of each corner (its weight in the convex combination) as the probability of that corner. The Lovasz extension is a weighted average of the values at the corners, i.e., the expected value of the distribution over the outcomes (values of $f(x)$) at the corners. $\lambda$ being uniform at $[0,1]$ is just the randomized process that samples a corner according to the probabilities of the distribution. $\endgroup$ – Aspect Stalence Apr 28 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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