Google Drive
Gist
Clipboard
In the previous note, we discussed two representations for univariate polynomials, as well as a precise view on what it means to "interpolate" a univariate polynomial from a set of points. This note is the continuation of the previous one, but for multilinear polynomials instead of univariate. That is, mulvariate polynomials where the degree in each variable is at most \(1\).
Of particular interest to us will be the multilinear extension (or, equivalently the "multivariate Lagrange interpolating polynomial"), due to its heavy use in LogUp-GKR.
The most common way to define multilinear polynomial is:
\[ p(x_0, \dots, x_{m - 1}) = \sum_{i_0 = 0}^1 \dots \sum_{i_{m-1} = 0}^1 a_{i_0, \dots, i_{m-1}} x_0^{i_0} \dots x_{m-1}^{i_{m-1}} \]
For example, if there are 2 variables,
\[ p(x_0, x_1) = a_{11} \cdot x_0x_1 + a_{10} \cdot x_0 + a_{01} \cdot x_1 + a_{00} \]
Just like univariate polynomials, multilinear polynomials form a vector space. The same proof sketch as for univariate polynomials applies for multilinear polynomials. For example, if \(f\) and \(g\) are multilinear polynomials defined as
\[ \begin{align} f(x_0, \dots, x_{m - 1}) &= \sum_{i_0 = 0}^1 \dots \sum_{i_{m-1} = 0}^1 a_{i_0, \dots, i_{m-1}} x_0^{i_0} \dots x_{m-1}^{i_{m-1}} \\ g(x_0, \dots, x_{m - 1}) &= \sum_{i_0 = 0}^1 \dots \sum_{i_{m-1} = 0}^1 b_{i_0, \dots, i_{m-1}} x_0^{i_0} \dots x_{m-1}^{i_{m-1}} \\ \end{align} \]
Then the addition operation over \(f\) and \(g\) is once again defined point-wise:
\[ \begin{align} &(f+g)(x_0, \dots, x_{m-1}) \\ &= f(x_0, \dots, x_{m-1}) + g(x_0, \dots, x_{m-1}) \\ &= (\sum_{i_0 = 0}^1 \dots \sum_{i_{m-1} = 0}^1 a_{i_0, \dots, i_{m-1}} x_0^{i_0} \dots x_{m-1}^{i_{m-1}}) + (\sum_{i_0 = 0}^1 \dots \sum_{i_{m-1} = 0}^1 b_{i_0, \dots, i_{m-1}} x_0^{i_0} \dots x_{m-1}^{i_{m-1}}) \\ &= \sum_{i_0 = 0}^1 \dots \sum_{i_{m-1} = 0}^1 (a_{i_0, \dots, i_{m-1}} x_0^{i_0} \dots x_{m-1}^{i_{m-1}} + b_{i_0, \dots, i_{m-1}} x_0^{i_0} \dots x_{m-1}^{i_{m-1}}) \\ &= \sum_{i_0 = 0}^1 \dots \sum_{i_{m-1} = 0}^1 (a_{i_0, \dots, i_{m-1}} + b_{i_0, \dots, i_{m-1}} ) x_0^{i_0} \dots x_{m-1}^{i_{m-1}} \end{align} \]
So \(f+g\) is also a multilinear polynomial, with coefficients \((a_{i_0, \dots, i_{m-1}} + b_{i_0, \dots, i_{m-1}})\).
The definition of the scalar multiplication operation is analogous and is left as an exercise. Similar to the previous note, we will not show here that every other property of vector spaces is valid; these are also left as an exercise.
Now that we've shown that the set of all multilinear polynomials forms a vector space, then it must be that we can identify a basis in that space, and refer to every polynomial in the vector space as coefficients (or equivalently, "coordinates") in that basis. As it turns out, we vector space of multilinear polynomials also has 2 useful bases that are analogous to the univariate case: the "monomial" and "evaluation" bases.
The monomial representation of multilinear polynomials comes from the equation presented earlier:
\[ p(x_0, \dots, x_{m - 1}) = \sum_{i_0 = 0}^1 \dots \sum_{i_{m-1} = 0}^1 a_{i_0, \dots, i_{m-1}} x_0^{i_0} \dots x_{m-1}^{i_{m-1}} \]
The set \(M = \{ x_0^{i_0} \dots x_{m-1}^{i_{m-1}} \}_{(i_0, \dots,i_{m-1}) = (0, \dots, 0)}^{(i_0, \dots,i_{m-1}) = (1, \dots, 1)}\) is the monomial basis, and the coefficients \([a_{0\dots0}, \dots, a_{1\dots1}]_M\) is the monomial representation of \(p\) in the basis \(M\).
For example, when \(m=2\), then \(M = \{x_0x_1, x_1, x_0, 1\}\), and the monomial representation of \(p\) is \([a_{11},a_{01}, a_{10}, a_{00}]_M\).
Recall from the univariate case that the interpolating polynomial is the polynomial of degree \(n-1\) which passes through every point of some dataset \(D = \{(x_0, y_0), \dots, (x_{n-1}, y_{n-1})\}\). We also presented the "extension" view which modeled \(D\) instead as a function \(f: \{x_0, \dots, x_{n-1}\} \rightarrow \mathbb{F}\).
In the multilinear case, although we could model the interpolating polynomial as a polynomial going through a set of points, it will prove more useful to focus on the extension view. Hence, given a function \(f: \{0, 1\}^m \rightarrow \mathbb{F}\), the Lagrange interpolating polynomial is defined as the m-variate multilinear polynomial which extends \(f\). We will write this polynomial as \(\tilde{f}\) to remind ourselves that it extends \(f\). However, do note that the "interpolating a dataset" is still a very valid of interpretation of the Lagrange interpolating polynomial.
To recap,
Since the extension of \(f\) always multilinear, we call \(\tilde{f}\) the multilinear extension of \(f\). It is defined as,
\[ \tilde{f}(r_0, \dots, r_{m-1}) = \sum_{x_0=0}^1 \dots \sum_{x_{m-1}=0}^1 \mathrm{eq}_{(x_0, \dots, x_{m-1})}(r_0, \dots, r_{m-1}) \cdot f(x_0, \dots, x_{m-1}) \]
where
\[ \mathrm{eq}_{(x_0, \dots, x_{m-1})}(r_0, \dots, r_{m-1}) = \prod_{i=0}^{m-1} x_i r_i + (1-x_i)(1-r_i). \]
Note that the \((r_0, \dots, r_{m-1})\) subscript to the \(\mathrm{eq}\) function denotes function parameters, which you can think of simply as constants that belong to \(\mathrm{eq}\).
Note that \(\mathrm{eq}_{(x_0, \dots, x_{m-1})}: \mathbb{F}^m \rightarrow \mathbb{F}\) is an m-variate polynomial, which from the definition we can see if multilinear. You should convince yourself that the degree in each \(r_i\) is \(1\). Then, \(\mathrm{eq}_{(x_0, \dots, x_{m-1})}\) is specifically designed so that
Going back to the definition of \(\tilde{f}\), you should then convince yourself that \(\tilde{f}(x_0, \dots, x_{m-1}) = f(x_0, \dots, x_{m-1})\) for every \((x_0, \dots, x_{m-1}) \in \{0, 1\}^m\) (or, in words, that \(\tilde{f}\) does indeed extend \(f\)). You should also convince yourself that \(\tilde{f}\) is multilinear (\(\mathrm{eq}\) is multilinear, and \(\tilde{f}\) is a linear combination of those \(\mathrm{eq}\), which doesn't change the degree in each \(r_i\)).
Similar to univariate polynomials, multilinear polynomials have an evaluation representation based on the Lagrange interpolating polynomial.
We saw in the previous section that \(\tilde{f}\) is defined as
\[ \tilde{f}(r_0, \dots, r_{m-1}) = \sum_{x_0=0}^1 \dots \sum_{x_{m-1}=0}^1 \mathrm{eq}_{(x_0, \dots, x_{m-1})}(r_0, \dots, r_{m-1}) \cdot f(x_0, \dots, x_{m-1}) \]
Do take note that in this expression, the only variables are \((r_0, \dots, r_{m-1})\); \((x_0, \dots, x_{m-1})\) are constants. By the same token, \(f(x_0, \dots, x_{m-1})\) is also a constant. Finally, for each \((x_0, \dots, x_{m-1}) \in \{0, 1\}^m\), \(\mathrm{eq}_{(x_0, \dots, x_{m-1})}\) is a multilinear polynomial.
Then, we have it again: the set \(E = \{\mathrm{eq}_{(0, 0, \dots, 0)}, \mathrm{eq}_{(1, 0, \dots, 0)}, \mathrm{eq}_{(0, 1, \dots, 0)}, \mathrm{eq}_{(1, 1, \dots, 0)}, \dots, \mathrm{eq}_{(1, 1, \dots, 1)}\}\) is a basis, and our evaluation representation for \(\tilde{f}\) is \[[f(0, 0, \dots, 0), f(1, 0, \dots, 0), f(0, 1, \dots, 0), f(1, 1, \dots, 0), \dots, f(1, 1, \dots, 1)]\] (that is, the evaluations of \(f\) over its entire domain).
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe