Multilinear Extensions (MLEs)

Let $f(x_1,x_2,\dots ,x_n)$ be a function $\in {\mathbb{F}}^n\mapsto \mathbb{F}$. Its multilinear extension $\tilde{f}(x_1,\dots ,x_n)$ is defined such that $\tilde{f}$ is linear in each $x_j\in \mathbb{F}$, and where $\tilde{f}(x)=f(x)\forall x\in \{0,1{\}}^n$.

Equality MLE

In order to explicitly formulate $\tilde{f}$ in terms of $f$, let us define the following indicator function:

$$\mathrm{eq}(x;z):\{0,1{\}}^{2n}\mapsto \{0,1\}=\{\begin{array}{ll}1,& \text{if }x=z\\ 0,& \text{otherwise}.\end{array}$$

Fortunately, $\mathrm{eq}(x;z):\{0,1{\}}^{2n}\to \{0,1\}$ has an explicit formula which is linear in each of $x_i$, or the bits of $x$. Intuitively, if $x=z$, then each of its bits must be equal. In boolean logic, this is the same thing as saying $(x_i=z_i=0)$ OR $(x_i=z_i=1)$ for all of the bits $i$ (which is an AND over all of the bits $i$).

When our inputs $x_i,z_i\in \{0,1\}$ this statement can be expressed as the following product: $$\prod _{i=1}^n(1-x_i)(1-z_i)+x_i{z}_i.$$ Taking the multilinear extension of $\mathrm{eq}$ simply means allowing for non-binary inputs $x_i,z_i\in \mathbb{F}$, because the polynomial is already linear in each variable. Since for all binary $x_i,z_i\in \{0,1\}$ we have that $\mathrm{eq}(x;z)=\widetilde{\mathrm{eq}}(x;z)$, the above definition of $\widetilde{\mathrm{eq}}(x;z)$ is an actual multilinear extension of $\mathrm{eq}$.

Construction from $\widetilde{\mathrm{eq}}$

We now have a polynomial extension of $\mathrm{eq}(x,z)$ which happens to be (by construction) linear in the $x$ variables (again, denote this function $\widetilde{\text{eq}}$). We can now define the multilinear extension of any function, as hoped for above:

$$\tilde{f}(x_1,\dots ,x_n)=\sum _{z_1,...,z_n\in \{0,1{\}}^n}\widetilde{\mathrm{eq}}(x;z)\cdot f(z_1,\dots ,z_n)$$

where $z_i$ are the bits of $z$.

Why is the above a valid multilinear extension of $f$? The idea here is that when evaluating $\tilde{f}$ on any $x_1,...,x_n\in \{0,1{\}}^n$, we have $\widetilde{\mathrm{eq}}(x;z)=0$ for all $z\ne x$ (since both $z$ and $x$ are binary, $\widetilde{\mathrm{eq}}(x;z)=\mathrm{eq}(x;z)$ behaves exactly like the boolean equality function), and thus all the terms in the above summation over $z_1,...,z_n\in \{0,1{\}}^n$ are zero except for the term where $z=x$, where we have $\widetilde{\mathrm{eq}}(x;z)=1$, and the value of that term is exactly $f(z_1,...,z_n)=f(x_1,...,x_n)$.

Another nice property of multilinear extensions which can be proven is that they are uniquely defined. I.e., ${\sum }_{z_i\in \{0,1\}}\widetilde{\mathrm{eq}}(x;z)\cdot f(z_1,\dots ,z_n)$ is the only multilinear function in $n$ variables which extends $f$.

Example

Let $f(x_1,x_2,x_3)=2x_1^2{x}_3+4x_2{x}_3^3+3x_1{x}_2^2{x}_3+5x_1+6x_2+3.$ Let us first build a table of evaluations of $f$ for $x_i\in \{0,1\}:$

We also build a table for $\widetilde{\mathrm{eq}}(x;z)$ for $x_i\in \{0,1\}$ in terms of $z$:

Then, using the formula for $\tilde{f}(x_1,\dots ,x_n)={\sum }_{z_i\in \{0,1\}}\widetilde{\mathrm{eq}}(x;z)\cdot f(z_1,\dots ,z_n)$, we get the explicit formula:

$$\begin{gathered} \tilde{f}(x_1,\dots ,x_n)=3(1-x_1)(1-x_2)(1-x_3)+3(1-x_1)(1-x_2)(x_3) \\ +9(1-x_1)(x_2)(1-x_3)+13(1-x_1)(x_2)(x_3)+8(x_1)(1-x_2)(1-x_3) \\ +10(x_1)(1-x_2)(x_3)+14(x_1)(x_2)(1-x_3)+23(x_1)(x_2)(x_3) \end{gathered}$$.

From here you can verify that $\tilde{f}(x)=f(x)$ when $x\in \{0,1{\}}^n$, and that $\tilde{f}(x)$ is linear in each of the $x$ variables.