EPF Week 6 Update 7

Vector Commitments for Multipoint: Intro

Basic Refresher

Monomial Basis

A polynomial can be represented in different bases, one of which is the monomial basis. In the monomial basis, a polynomial

$P(t)$ of degree

$t$ is expressed as:

$$P(t)=a_0+a_{1}t+a_2{t}^2+...+a_n{t}^n$$

To evaluate the

$P(t)$ at a specific point

$t=t_0$, we simply substitute t_0 into the polynomial and perform the assigned mathematical operations.

$$P(t_0)=a_0+a_1{t}_0+a_2{t}_0^2+...+a_n{t}_0^n$$

For example, if we have the polynomial

$P(t)=3+2t-t^2+4t^3$ and we want to evaluate it at

$t=2$, then:

$$P(t)=3+2(2)-(2{)}^2+4(2{)}^3=3+4-4+4\times 8=35$$

So,

$P(2)=35.$

Polynomial Interpolation

Polynomial interpolation is the task of finding a polynomial that fits a set of points

$(x_i,y_i)$ for

$i=0,1,2,3,...,n$. The central idea is to find a Polynomial

$P(x)$ of degree at most

$n$ that passes through these

$(n+1)$ points.

Lagrange Interpolation

Given

$n+1$ distinct points

$x_0,x_1,x_2,...,x_n$ and their corresponding

$y$-values

$y_0,y_1,y_2,...,y_n$, the Lagrange interpolation is defined as:

where

$L_i(x)$ is the

$i$-th Lagrange basis polynomial, which is defined by:

The Lagrange interpolation polynomial is unique and hence, passes through all the given points.

Barycentric Lagrange Interpolation

The barycentric form of the Lagrange Interpolation is a numerically stable and computationally efficient representation of the Lagrange polynomial. The barycentric form of the Lagrange polynomial is:

where

$w_i=1/L_i^{\prime }(x_i)$ and

$L_i^{\prime }(x_i)$ is the derivative of the

$i$-th Lagrange Basis polynomial evaluated at

$x$.

As an example, let us consider a simple example where we want to interpolate a function

$f(x)=x^2$ at three points

$x=-1,0,1$ using Barycentric interpolation.

First, we would need to choose our data points. For

$f(x)=x^2$, these would be:

Step 1: Computing the Barycentric weights

The barycentric weights

$w_i$ are computed using the Lagrange basis polynomials

$L_i(x)$. However, for the case of equally spaced

$x$-values (or in simple cases), they can often be computed more efficiently.

For example, using

$n=2$ (three points, so

$n+1=3$).

1. $w_0=\frac{1}{0-(-1)}=1$
2. $w_1=\frac{1}{0-0}$ that will be undefined
3. $w_2=\frac{1}{0-1}=-1$

Note that for

$w_1$, it's undefined because the term

$x_i-x_j$ would be zero, from the Lagrangian basis formula. However, in the case of distinct

$x$-values, this situation should not arise. Since all the

$x$-values are distinct here, there should not be a 0 denominator.

On plugging these values on the Barycentric Lagrange Interpolation formula we get the following:

• $P(x)=\frac{\frac{1}{(x-(-1)).1+0+(-1)(x-1).1}}{\frac{1}{(x-(-1))+0+(-1)(x-1)}}$

• Simplifying,

  $P(x)=\frac{\frac{1}{(x+1)}-\frac{1}{(x-1)}}{\frac{1}{(x+1)}-\frac{1}{(x-1)}}$

• After more simplification, we get this

  $P(x)=x^2$

If we evaluate

$P(x)$ at say,

$x=0.5$, we should get

$(0.5{)}^2=0.25$, which matches

$f(x)=x^2$

This is a simple example, but it demonstrates the basic steps of Barycentric Lagrange Interpolation. The real power of barycentric form becomes evident in more complex, higher degree functions with interpolations.

The concept of representing vectors in a monomial basis can be explored from both algebraic and computational perspectives. Here are the 2 major forms in which both are usually represented…

Coefficient Forms in a Monomial Basis

In algebra, the coefficient form of a polynomial is its representation as a linear combination of monomials. A monomial basis is a set of monomials

$1,x,x^2,x^3,...,x^n$, which serves as the "building blocks" for polynomials of degree

$n$ or less.

In this form, a polynomial

$P(x)$ of degree

$n$ is represented as

$$P(x)=a_0.1+a_1.x+a_2.x^2+a_3.x^3+....+a_n.x^n$$

Here, the coefficients

$a_0,a_1,a_2,...,a_n$ are the coordinates of

$P(x)$ in the vector space spanned by the monomial basis. This representation allows us to work with the polynomial using the coefficients, which are stored as a vector

$a=[a_0,a_1,...,a_n]$.

Evaluation Forms in a Monomial Basis

In the evaluation form, we view a polynomial through the lens of it's values at

$n+1$ distinct points

$x_0,x_1,...,x_n$. Each of these values can be computed using the polynomial's expression in the monomial basis.

$$P(x_i)=a_0.1+a_1.x_i+a_2.{x_i}^2+...+a_n.{x_i}^n$$

By evaluating

$P(x)$ at these

$n+1$ distinct points, we obtain a vector

$$b=[P(x_0),P(x_1),...,P(x_n)].$$

Conversion between Coefficient and Evaluation forms

Coefficient to Evaluation

The process of converting from the coefficient form to the evaluation form involves substituting each

$x_i$ into

$P(x)$ and computing the result. This can be computationally intensive, with a naive implementation in

$O(n^2)$ time. However, specialized algorithms like the Fast Fourier Transform (FFT) can do this more effieciently, in

$O(n$

$log$

$n)$ time, when the evaluation points are roots of unity.

Evaluation to Coefficient

Conversely, going from evaluation form to coefficient form requires solving a interpolation problem. Given

$n+1$ points, that are,

$(x_0,P(x_0)),(x_1,P(x_1)),....,(x_n,P(x_n))$, we wish to find the unique polynomial of degree

$n$ or less that passes through these points. One classic approach is Lagrange interpolation as I stated before.

Apart from this, specialized algorithms like Inverse Fast Fourier Transform (IFFT) can perform this conversion efficiently when the evaluation points are roots of unity.