Polynomial degree reduction in the discrete $L_2$-norm equals best Euclidean approximation of h-Bézier coefficients

Abstract

We show that the best degree reduction of a given polynomial P from degree n to m with respect to the discrete $L_2$-norm is equivalent to the best Euclidean distance of the vector of h-Bézier coefficients of P from the vector of degree raised h-Bézier coefficients of polynomials of degree m. Moreover, we demonstrate the adequacy of h-Bézier curves for approaching the problem of weighted discrete least squares approximation. Applications to discrete orthogonal polynomials are also presented.

1 Introduction

Degree reduction of Bézier curves is a fundamental technique in Computer Aided Geometric Design (CAGD) that allows for data reduction while preserving, to some extent, the shape of the original curve. The technique consists of finding the best low degree polynomial approximation, with respect to a given norm, of a given Bézier curve. The solution of the approximation problem depends strongly on the norm that measures the distance between curves. Polynomial degree reduction techniques with respect to different norms attracted considerable interest for decades, e.g., $L_{\infty }$-norm [7, 19], $L_2$-norm [13, 14, 16], $L_1$-norm [12], $L_p$-norm [5].

An interesting result emerged in the case of the $L_2$-norm [14]. To state the result, we denote by ${\mathbb {P}}_n$ the linear space of polynomials of degree at most n and define the following two inner products on ${\mathbb {P}}_n$; the classical $L_2$-inner product

$$\begin{aligned} \langle P,Q\rangle _{L_2} = \int _{0}^{1} P(x)Q(x) dx \end{aligned}$$

(1.1)

and the Euclidean inner product of the Bézier coefficients

$$\begin{aligned} \langle P,Q\rangle _{E_2} = \sum _{i=0}^{n} {p_i} q_{i}, \end{aligned}$$

(1.2)

where $(p_0,p_1,\ldots ,p_n)$ and $(q_0,q_1,\ldots ,q_n)$ are the Bézier coefficients over the interval [0, 1] of the polynomials P and Q respectively. The main result in [14] is the following:

Theorem 1.1

Given a polynomial P of degree n and a positive integer $m \le n$, the approximation problem

$$\begin{aligned} \min _{Q \in {\mathbb {P}}_m} ||P - Q|| \end{aligned}$$

(1.3)

has the same minimizer for the norm induced either by the inner product (1.1) or the inner product (1.2).

Besides its elegance, Theorem 1.1 has practical implications: it allows for direct computation of the control structure of the polynomial solution to (1.3) in terms of the pseudo-inverses of the degree raising matrices. Theorem 1.1 was generalized to handle the problem of polynomial degree reduction under endpoints constraints [1]. The generalization was achieved by modifying the inner product (1.2) via associating a fixed weight to each Bézier coefficient of the polynomials P and Q.

In this work, we initiate the problem of polynomial degree reduction with respect to discrete norms. First, we give a discrete analogue of Theorem 1.1 in the following sense: Given polynomials P and Q both of degree at most n, we fix an integer $N \ge n$ and define the classical $L_2$-discrete inner product on ${\mathbb {P}}_n$ as

$$\begin{aligned} \langle P,Q\rangle _{L^h_2} = \sum _{j=0}^{N} P(x_j)Q(x_j), \end{aligned}$$

(1.4)

where $(x_0,x_1,\ldots ,x_N)$ is an equidistant partition of the interval [0, 1], where $h = 1/N$ is the sampling parameter and $x_j = j h$ for $j=0,1,\ldots ,N$. We also define the Euclidean inner product of the h-Bézier coefficients as

$$\begin{aligned} \langle P,Q\rangle _{E^{h}_{2}} = \sum _{i=0}^{n} p^{h}_{i} q^{h}_{i}, \end{aligned}$$

(1.5)

where $(p^h_0,p^h_1,\ldots ,p^h_n)$ (resp. $(q^h_0,q^h_1,\ldots ,q^h_n)$) are the h-Bézier coefficients of the polynomial P (resp. Q) over the interval [0, 1] with $h = 1/N$. (See Sect. 2 for the notion of h-Bézier curves). Our first main result is:

Theorem 1.2

Given a polynomial P of degree n and a positive integer $m \le n$, the approximation problem

$$\begin{aligned} \min _{Q \in {\mathbb {P}}_m} ||P - Q|| \end{aligned}$$

(1.6)

has the same minimizer for the norm induced either by the inner product (1.4) or the inner product (1.5).

In the limit case when h converges to zero, we recover Theorem 1.1 as a particular case.

Our second main finding is the realization of the adequacy of using the h-Bernstein bases to approach the problem of polynomial degree reduction with respect to weighted discrete norms. The results we obtain with the weighted discrete norms have no continuous weighted $L_2$-norm analogue. We also reveal that the validity of Theorems 1.1 and 1.2 can be traced back to some relations between the pseudo-inverses of the degree raising matrices.

Another interesting application of Theorem 1.2 is a simple proof and interpretation of the well-known fact that the Bernstein coefficients of Legendre polynomials are discrete Legendre polynomials. The proof relies on Theorem 1.2 and the fact that degree elevation of h-Bézier curves is independent of the sampling parameter h.

The paper is organized as follows: In Sect. 2 we review the notion of h-Bernstein bases and h-Bézier curves. Some consequences, that will be used subsequently, of the fact that degree elevation for h-Bézier curves is independent of the sampling parameter h will be given. Our main Theorem 1.2 will be proved in Sect. 3 and methods for the solution to the discrete polynomial degree reduction problem are given in Sect. 4. An application to discrete Legendre polynomials will be presented in Sect. 5. Weighted discrete polynomial degree reduction is the object of Sect. 6. We conclude in Sect. 7 with possible generalizations of this work.

2 Degree elevation of h-Bézier curves

Denote by ${\mathbb {P}}_n$ the linear space of polynomials of degree at most n. The h-Bernstein basis over the unit interval [0, 1] of the space ${\mathbb {P}}_n$ is defined by [18]¹

$$\begin{aligned} B_{k}^{n}(t;h) = \left( {\begin{array}{c}n\\ k\end{array}}\right) \frac{\prod _{i=0}^{k-1}(t-ih) \prod _{i=0}^{n-k-1}(1-t-ih)}{\prod _{i=0}^{n-1}(1-ih)}, \quad k=0,1,\ldots ,n, \end{aligned}$$

(2.1)

where h, throughout this work, is understood to be a real number different from $1/i, i=1,2,\ldots ,n-1$. For $h=0$, the h-Bernstein basis coincides with the classical Bernstein basis which we denote simply by $B_{k}^{n}, k=0,1,\ldots ,n$. The h-Bernstein bases share many similar properties with the classical Bernstein bases, e.g., for $h \le 0$ the h-Bernstein functions $B_{k}^{n}(t;h)$ are nonnegative on [0, 1]; the basis form a partition of unity, i.e.,

$$\begin{aligned} \sum _{k=0}^{n} B_{k}^{n}(t;h) \equiv 1. \end{aligned}$$

An h-Bézier curve is a parametric polynomial of the form

$$\begin{aligned} P(t) = \sum _{k=0}^{n} B_{k}^{n}(t;h) P_k, \quad P_i \in {\mathbb {R}}^s; \quad s \ge 1. \end{aligned}$$

The points $P_i$ are called the h-Bézier points or coefficients of P over the interval [0, 1]. Values of the polynomial P can be computed using an h-de Casteljau algorithm [18]. Moreover, the h-blossoms introduced in [18], as a generalization of the classical polynomial blossoms by altering the diagonal property, allow for the understanding of many concepts related to h-Bézier curves with rather considerable ease.

To a polynomial P of degree at most n, we associate a family of parametrized polynomials as:

$$\begin{aligned} P(t;h) = \sum _{k=0}^n p_k B_{k}^{n}(t;h), \end{aligned}$$

where $(p_0,p_1,\ldots ,p_n)$ are the Bézier coefficients of P over [0, 1] with respect to the classical Bernstein basis, i.e., $P(t;0) = P(t)$ for all $t\in {\mathbb {R}}$.

Lemma 2.1

Let P be a polynomial of degree $n\le N$ written as

$$\begin{aligned} P(t) = \sum _{k=0}^n p_k B_{k}^{n}(t) = \sum _{k=0}^N q_{k}^{(N)} B_{k}^{N}(t). \end{aligned}$$

(2.2)

For $j=0,1,\ldots ,N$

$$\begin{aligned} q_{j}^{(N)} = P\left( \frac{j}{N};\frac{1}{N}\right) \!. \end{aligned}$$

Proof

It can be checked that the h-Bernstein basis $B_{k}^{n}(.,h)$ satisfies the identity [10]

$$\begin{aligned} B_{k}^{n}(t;h) = \frac{n+1-k}{n+1} B_{k}^{n+1}(t;h) + \frac{k+1}{n+1} B_{k+1}^{n+1}(t;h), \quad k=0,1,\ldots ,n. \end{aligned}$$

(2.3)

Since the coefficients attached to the h-Bernstein functions on the right hand side of (2.3) are independent of h, we deduce that degree elevation for h-Bézier curves is independent of the parameter h. Therefore,

$$\begin{aligned} P(t;h) = \sum _{k=0}^n p_k B_{k}^{n}(t;h) = \sum _{k=0}^N q_{k}^{(N)} B_{k}^{N}(t;h). \end{aligned}$$

We conclude the proof using the simple computational fact that

$$\begin{aligned} B_j^N\left( \frac{k}{N};\frac{1}{N}\right) = \delta _{jk}; \quad j,k=0,1,\ldots ,N. \end{aligned}$$

(2.4)

$\square$

Equation (2.4) shows that

$$\begin{aligned} B_j^N\left( t;\frac{1}{N}\right) = l_j^N(t), \end{aligned}$$

where $l_j^N, j=0,1,\ldots ,N$ is the Lagrange basis with respect to the points 0, 1 / N, $2/N,\ldots ,1$. In other words, we can state that P(t; 1 / N) is the Lagrange interpolating polynomial of the degree raised Bézier coefficients to order N of the polynomial P (see Fig. 1). This fact is more or less explicit in [9, 10].

Fig. 1

An h-Bézier curve with $h = 1/N$ and with h-Bézier coefficients coinciding with the Bézier coefficients of a polynomial P, interpolates the raised Bézier coefficients of P to degree N. Black the classical quintic Bézier curve and its control polygon. Red the control polygon of P raised to degree 8. Blue the h-Bézier curve with $h = 1/8$ (color figure online)

From now on, we adopt the following notation: For a vector $p = (p_0,\ldots ,p_n)$, we write $B^n p = \sum _{i=0}^n p_i B_i^n$ and $B^n_h p = \sum _{i=0}^n p_i B_i^n(.;h)$. As degree elevation for h-Bézier curves is independent of the parameter h, we readily obtain the following:

Lemma 2.2

A polynomial $B^n p$ is of degree less or equal $m \le n$ if and only if a polynomial $B_h^n p$ is of degree less or equal m, i.e.;

$$\begin{aligned} B^n p \in {\mathbb {P}}_m \Leftrightarrow B_h^n p \in {\mathbb {P}}_m\; \quad \text {for an} \quad h \in {\mathbb {R}} / \left\{ 1,\frac{1}{2}, \ldots , \frac{1}{n-1} \right\} \!. \end{aligned}$$

Remark 2.1

If we set $h = 1/n$ in the previous Lemma, and using the fact that $B_{1/n}^n p$ is the Lagrange interpolation polynomial of the control points of $B^n p$, we recover a well-known result [11] (Lemma 4.4), which essentially states the following: if the Bézier coefficients $p(k) :=p_k$ of the polynomial $B^n_h p$ can be expressed as a polynomial of degree at most m in k, then the polynomial $B^n_h p$ is a polynomial of degree at most m. This is the version of Lemma 2.2 we will use subsequently.

In the next section, we will need the following proposition.

Proposition 2.1

Fix an integer $n \ge 1$. Let R be a polynomial of degree at most $s \le n$ and denote by $x_j = j/N, j=0,\ldots ,N$ with $N \ge n$. The function

$$\begin{aligned} \psi (k) = \sum _{j=0}^{N} R(j) B_{k}^{n}\left( x_j;\frac{1}{N}\right) \end{aligned}$$

is a polynomial in k of degree at most s.

Proof

We proceed by induction on N. If $N = n$ then invoking (2.4) we obtain $\psi (k) = R(k)$ which is a polynomial of degree at most s in k. Now let us prove the proposition for $N+1$ assuming its validity for any $l \le N$. Consider the function

$$\begin{aligned} \psi (k) = \sum _{j=0}^{N+1} R(j) B_{k}^{n}\left( \tilde{x}_j;\frac{1}{N+1}\right) , \quad \tilde{x}_j = \frac{j}{N+1},\; j=0,\ldots ,N+1. \end{aligned}$$

(2.5)

If we write

$$\begin{aligned} B_{k}^{n}(t) = \sum _{k=0}^N q_{k}^{(N)} B_{k}^{N}(t) = \sum _{k=0}^{N+1} q_{k}^{(N+1)} B_{k}^{N+1}(t) \end{aligned}$$

then by Lemma 2.1, for $j=0,1,\ldots ,N+1$

$$\begin{aligned} B_{k}^{n}\left( \tilde{x}_j; \frac{1}{N+1}\right) = q_{j}^{(N+1)} = \frac{N+1 -j}{N+1} q_{j}^{(N)} + \frac{j}{N+1} q_{j-1}^{(N)}, \end{aligned}$$

with the convention that $q_{-1}^N = q_{N+1}^{N} =0$. Therefore,

$$\begin{aligned} B_{k}^{n}\left( \tilde{x}_j;\frac{1}{N+1}\right) = \frac{N+1 -j}{N+1} B_{k}^{n}\left( x_j;\frac{1}{N}\right) + \frac{j}{N+1} B_{k}^{n}\left( x_{j-1};\frac{1}{N}\right) \!. \end{aligned}$$

(2.6)

Inserting (2.6) into (2.5) gives

$$\begin{aligned} \psi (k) = \frac{1}{N+1} \sum _{j=0}^N \left( (N+1-j)R(j) + (j+1) R(j+1) \right) B_{k}^{n}\left( x_j;\frac{1}{N}\right) \!. \end{aligned}$$

Since the polynomial R is of degree at most s, the polynomial $\tilde{R}(x) := (N+1-x)R(x) + (x+1) R(x+1)$ is also of degree at most s. This completes the proof by the induction hypothesis. $\square$

3 Discrete polynomial degree reduction

Fix a positive integer $n \ge 1$. For each integer $N \ge n$, we define an equidistant partition $X_{N} = (x_0,x_1,\ldots ,x_N)$ of the interval [0, 1] by requiring $x_j = j/N, j=0,1,\ldots ,N$. Denote by h the sampling parameter $h= 1/N$. The discrete $L^h_2$ inner product $\langle \cdot ,\cdot \rangle _{L^h_{2}}$ over ${\mathbb {P}}_n$ is defined as

$$\begin{aligned} \langle f,g\rangle _{L^h_2} := \sum _{j=0}^N f(x_j) g(x_j). \end{aligned}$$

(3.1)

Moreover, we define the h-Euclidean inner product $\langle \cdot ,\cdot \rangle _{E_2^{h}}$ of the h-Bézier coefficients over ${\mathbb {P}}_n$ by

$$\begin{aligned} \langle B^n_h b,B^n_h c\rangle _{E_2^{h}} := \sum _{i=0}^n b_i c_i. \end{aligned}$$

(3.2)

Theorem 3.1

The orthogonal complements of ${\mathbb {P}}_m$ in ${\mathbb {P}}_n$ with respect to the discrete $L_2^h$ inner product (3.1) and the h-Euclidean inner product (3.2) are equal.

Proof

Denote by ${\mathbb {P}}_{m,n}$ the orthogonal complement of ${\mathbb {P}}_m$ in ${\mathbb {P}}_n$ with respect to the Euclidean inner product $\langle \cdot , \cdot \rangle _{E_2^{h}}$. Let $B^n_h q$ be an element of ${\mathbb {P}}_{m,n}$. Then $\langle B^n_h q , B^n_h p\rangle _{E_2^{h}}= 0$ for any element $B^n_h p \in {\mathbb {P}}_m$. Let s be an integer smaller than m. We have

$$\begin{aligned} \langle B^n_h q , t^s\rangle _{L_2^{h}} = \sum _{j=0}^N (x_j)^s B^n_h q(x_j) =\, \langle B^n_h q , B^n_h \phi \rangle _{E_2^{h}}, \end{aligned}$$

(3.3)

where $\phi = (\phi _0,\phi _1,\ldots ,\phi _n)$ with

$$\begin{aligned} \phi _k = \sum _{j=0}^N (x_j)^s B_{k}^n(x_j;h). \end{aligned}$$

As $B^n_h q$ is an element of ${\mathbb {P}}_{m,n}$ and by Remark 2.1, the inner product (3.3) vanishes if and only if $B_h^n \phi$ is an element of ${\mathbb {P}}_m$ i.e.; $\phi (k) := \phi _k$ is a polynomial in k of degree at most m. This is true as can be seen by writing $\phi _k$ as

$$\begin{aligned} \phi _k = \frac{1}{N^s} \sum _{j=0}^N j^s B_{k}^n(x_j;h) \end{aligned}$$

and invoking Proposition 2.1. Therefore, ${\mathbb {P}}_{m,n}$ is contained in the orthogonal complement of ${\mathbb {P}}_m$ in ${\mathbb {P}}_n$ with respect to the h-Euclidean inner product $\langle \cdot ,\cdot \rangle _{L_2^{h}}$. We conclude the proof by virtue of the equality of dimensions of the two orthogonal complements. $\square$

A direct consequence of Theorem 3.1 is our main result:

Corollary 3.1

Given a polynomial P of degree n and a positive integer $m \le n$, the approximation problem

$$\begin{aligned} \min _{Q \in {\mathbb {P}}_m} ||P - Q|| \end{aligned}$$

(3.4)

has the same minimizer for the norm induced either by the inner product (3.1) or the inner product (3.2).

A simple consequence of Corollary 3.1 is the following factorization of discrete polynomial degree reduction: Denote by ${\fancyscript{P}}^{h}_{m,n}$ the linear operator that maps a polynomial of degree n to the best discrete $L_2^{h}$-approximation in ${\fancyscript{P}}_m$, then we have the factorization ${\fancyscript{P}}^{h}_{m,n} = {\fancyscript{P}}^{h}_{m,l} {\fancyscript{P}}^{h}_{l,n}$ with $m \le l \le n$.

Remark 3.1

In the limit case, when the parameter h goes to zero, we have

$$\begin{aligned} \lim _{h \rightarrow 0} h \langle f,g\rangle _{L_2^h} = \int _{0}^{1} f(x) g(x) dx \end{aligned}$$

and

$$\begin{aligned} \lim _{h \rightarrow 0} \langle B^n_h p,B^n_h q\rangle _{L_2^h} = \, \langle B^n p,B^n q\rangle _{L_2}. \end{aligned}$$

From this, we see that when h goes to 0, Corollary 3.1 coincides with the main result in [14].

4 Methods of solution

Denote by $A_{n,m}$ the degree raising matrix for mapping the Bézier coefficients of a polynomial P from degree m to n. The matrix A is of order $(n+1)\times (m+1)$ and can be decomposed into elementary degree raising matrices [14] as $A_{n,m} = A_{n,n-1}$ $A_{n-1,n-2} \ldots A_{m+1,m}$ where

$$\begin{aligned} A_{k,k-1}(i,j) = \left\{ \begin{array}{l@{\quad }l} i/k &{} \text{ if }\;j = i-1, \\ 1 - i/k &{} \text{ if }\;j=i, \\ 0 &{} \text{ else }. \end{array}\right. \end{aligned}$$

Let P be a polynomial of degree n with h-Bézier coefficients $p^{h} = (p_0^{h},p_1^{h},\ldots ,p_n^{h})$. According to Corollary 3.1 and since degree raising matrices for h-Bézier curves coincide with those of the classical Bézier curves, the h-Bézier coefficients $q^h = (q_0^{h},q_1^{h},$ $\ldots ,q_m^{h})$ of the polynomial Q solution to the minimization problem (3.4) coincide with the solution of the least squares problem

$$\begin{aligned} \min _{q^h \in {\mathbb {R}}^{m+1}} \left| \left| p^{h} - A_{n,m} q^{h}\right| \right| _2. \end{aligned}$$

(4.1)

The solution to (4.1) is given, using the pseudo-inverse $A_{n,m}^{\dagger }$, by

$$\begin{aligned} q^{h} = A_{n,m}^{\dagger } p^{h} := \left( A_{n,m}^t A_{n,m}\right) ^{-1} A_{n,m}^{t} p^{h}. \end{aligned}$$

(4.2)

As the solution (4.2) depends on the parameter h, namely the chosen spacing of the partition of the interval [0, 1], we would want to monitor the solution as a function of the parameter h. There are several ways to compute the h-Bézier coefficients of a polynomial. One way is through the use of the notion of h-blossoming introduced in [18]. Namely, given a polynomial P of degree at most n and a parameter h, there exists a unique multi-affine symmetric function $f(u_1,u_2,\ldots ,u_n)$ called the h-blossom of P such that

$$\begin{aligned} f(u,u+h,\ldots ,u+(n-1)h) = P(u) \quad \text {for any} \; u \in {\mathbb {R}}. \end{aligned}$$

From the expression of the h-blossom of the polynomial P, the h-Bézier coefficients of $P = B^n_h p^h$ can be derived as

$$\begin{aligned} p^h_k = f(k h,(k+1) h,\ldots ,(n-1) h, 1,1+h,\ldots ,1 + (k-1)h), \quad k=0,1,\ldots ,n. \end{aligned}$$

Methods for computing the h-blossom of a polynomial are discussed in [18]. Another more efficient method is to use the conversion formula between the h-Bernstein bases and the discrete Legendre polynomials as described in the next section. As the coefficients of the conversion formula are equal to the ones of the continuous case, i.e., the case $h =0$, the results in [8] can be used to study the efficiency and the stability of the method. Another method, the one we will adopt here, is as follows: Let P be a polynomial of degree n with h-Bézier coefficients $p^h = (p^h_0,p^h_1,\ldots ,p^h_n)$, i.e.,

$$\begin{aligned} P(t) = \sum _{j=0}^n p^h_j B_j^n(t; h) = \sum _{j=0}^N p_j^{(N)} B_j^N(t; h). \end{aligned}$$

Denote by $V_h = (P(0),P(h),P(2h),\ldots ,P(1))^{T}$. Then by (2.4) we have

$$\begin{aligned} A_{N,n} \left( p^h_0,p^h_1,\ldots ,p^h_n\right) ^{T} = \left( p_0^{(N)},p_1^{(N)}, \ldots ,p_N^{(N)}\right) ^{T} = V_h. \end{aligned}$$

Therefore, we can compute the h-Bézier coefficients of P using the pseudo-inverse as

$$\begin{aligned} p^h = A_{N,n}^{\dagger } V_h. \end{aligned}$$

(4.3)

Hence, according to (4.2), the solution to the problem (3.4) as a function of the parameter h is given by

$$\begin{aligned} q^h = A_{n,m}^{\dagger } A_{N,n}^{\dagger } V_h. \end{aligned}$$

Summarizing:

Theorem 4.1

The h-Bézier coefficients of the solution $Q = B^m_h q^h$ to the minimization problem (3.4) are given by

$$\begin{aligned} q^h = A_{n,m}^{\dagger } A_{N,n}^{\dagger } V_h, \end{aligned}$$

where $m \le n \le N$, $h = 1/N$, $V_h = \left( P(0),P(h),P(2h),\ldots ,P(1)\right) ^T$ and $A_{i,j}$ denote the degree raising matrices.

Figure 2 shows an application of Theorem 4.1 to the best discrete degree reduction of a polynomial of degree five to degree three and one polynomials for various values of the sampling parameter h.

Fig. 2

Best discrete degree reduction of a Bézier curve of degree five to degree three (left) and degree one (right) at different sampling rate h. Black the original Bézier curve and its control polygon. Green $h = 1/6$. Blue $h = 1/10$. Red the best degree reduction for the classical $L_2$ norm obtained when $h=0$. Note that the right figure can be interpreted as the regression lines at different sampling of the Bézier curve (color figure online)

5 An application to discrete and classical Legendre polynomials

The discrete Legendre polynomials $L^h_{0}, L^h_1,\ldots ,L^h_N$ with $h = 1/N$ are defined as the polynomials orthogonal with respect to the h-discrete inner product (3.1) and normalized with the conditions $L^h_k(1) = (-1)^k, k=0,1,\ldots ,N$. An explicit expression for $L^h_k,\; k=0,1,\ldots N$ is given by [15]

$$\begin{aligned} L^h_k(x) = \sum _{j=0}^k (-1)^{j} \left( {\begin{array}{c}k\\ j\end{array}}\right) \left( {\begin{array}{c}k+j\\ j\end{array}}\right) \frac{x(x-h)\ldots (x-(j-1)h)}{h^j N(N-1)\ldots (N-j+1)}. \end{aligned}$$

When the parameter h goes to zero, the discrete Legendre polynomials converge to the classical Legendre polynomial $L_k$ over the interval [0, 1] (the Legendre polynomials here are normalized with the conditions $L_k(1) = (-1)^k, k=0,1,\ldots$. Discrete Legendre polynomials are particular cases of Hahn polynomials defined in terms of the terminating generalized hypergeometric functions as:²

(5.1)

For the parameters $\alpha =\beta =0$, we have $L^h_k(x) = Q_k (x;0,0, h)$. The conversion formula between the classical Legendre polynomials and the Bernstein basis over the interval [0, 1] is given by [8]

$$\begin{aligned} L_k(x) = \sum _{i=0}^{k} (-1)^{i} \left( {\begin{array}{c}k\\ i\end{array}}\right) B_i^k(x). \end{aligned}$$

(5.2)

We show now how we can use Corollary 3.1 and (5.2) to prove the following:

Proposition 5.1

The discrete Legendre polynomials $L_k^h$ can be expressed in terms of the h-Bernstein basis of order k as

$$\begin{aligned} L_{k}^{h}(x) = \sum _{i=0}^{k} (-1)^{i} \left( {\begin{array}{c}k\\ i\end{array}}\right) B_i^k(x;h). \end{aligned}$$

Proof

Let P be the polynomial of exact degree k with h-control points $p^h = (a,0,\ldots ,0)$ over the interval [0, 1], where $a = \left( {\begin{array}{c}2k\\ k\end{array}}\right)$. Denote by Q the polynomial solution of degree $k-1$ to the minimization problem (3.4). Using orthogonality and comparing the leading coefficients of the polynomials P and $L_k^h$, we obtain

$$\begin{aligned} Q(x) = P(x) - L_k^{h}(x). \end{aligned}$$

Denote by $q^h$ the h-Bézier coefficients of the polynomials Q over the interval [0, 1]. Using (4.2) we obtain

$$\begin{aligned} L_k^h(x) \!=\! P(x) - Q(x) \!=\! B^k_h \left( p^h \!-\!A_{k,k-1}q^h\right) \!=\! B^k_h \left( I \!-\! A_{k,k-1}A_{k,k-1}^{\dagger }\right) p^h.\quad \end{aligned}$$

(5.3)

The matrix $I - A_{k,k-1}A_{k,k-1}^{\dagger }$ and the h-control points $p^h$ are independent of the parameter h. Therefore, the vector $(I - A_{k,k-1}A_{k,k-1}^{\dagger })p^h$ is independent of h. For $h=0$, the h-Bernstein bases coincide with the classical ones and the discrete Legendre polynomials coincide with the classical Legendre polynomial $L_k$. Thus, by (5.2) and (5.3)

$$\begin{aligned} \left( I - A_{k,k-1}A_{k,k-1}^{\dagger }\right) p^h= \left( \left( {\begin{array}{c}k\\ 0\end{array}}\right) ,\ldots , (-1)^{i} \left( {\begin{array}{c}k\\ i\end{array}}\right) ,\ldots , (-1)^{K}\left( {\begin{array}{c}k\\ k\end{array}}\right) \right) \!. \end{aligned}$$

This concludes the proof. $\square$

Another interesting insight from the h-Bernstein basis and Proposition 5.1 is the ability to easily derive representations of the classical Legendre polynomials in higher order Bernstein bases, i.e., degree raising of Legendre polynomials. Let us assume we want explicit expressions for the coefficients $b_i, i=0,\ldots ,M; (M \ge k)$ in the representation

$$\begin{aligned} L_k(x) = \sum _{j=0}^M b_j B_j^{M}(x); \quad M \ge k. \end{aligned}$$

As degree elevation of the h-Bernstein basis is independent of the parameter h, we can set $h = 1/M$ and we have

$$\begin{aligned} L_k^h(x) = \sum _{j=0}^M b_j B_j^{M}(x;h). \end{aligned}$$

From (2.4), we have $b_j = L_k^h(j/M)$ and using (5.1), we get

Corollary 5.1

The Legendre polynomials $L_k$ can be expressed in terms of the Bernstein basis of order $M \ge k$ as

(5.4)

The expression (5.4) is essentially the same as derived in [8] and proved using an induction on the degree raising. Ciesielski [6] was the first to derive and generalize (5.4) by showing that the Bézier coefficients of Jacobi polynomials are Hahn polynomials.

We can use Corollary 5.1 while arguing that degree raising does not depend on the parameter h to deduce that for any $h = 1/N$, we have

The last expression was derived in [17] using the Olinde-Rodrigues formula for Hahn polynomials.

6 Weighted discrete degree reduction

Let us fix $N \ge n$ and a set of positive real numbers $\omega _j, j=0,1,\ldots ,N$. Define the following weighted discrete inner product on ${\mathbb {P}}_n$

$$\begin{aligned} \langle f,g\rangle _{L^{\omega }_h} := \sum _{j=0}^N \omega _j f(x_j) g(x_j), \end{aligned}$$

(6.1)

where $x_j = hj; j=0,1,\ldots ,N$ and $h = 1/N$. Moreover, we define the following weighted h-Euclidean inner product $\langle \cdot ,\cdot \rangle _{E^{\omega }_{h}}$ over ${\mathbb {P}}_n$ by

$$\begin{aligned} \langle B^n_h b,B^n_h c\rangle _{E^{\omega }_{h}} := \sum _{j=0}^N \omega _j b^{(N)}_j c^{(N)}_j, \end{aligned}$$

(6.2)

where $b_i^{(N)}$ (resp. $c_{i}^{(N)}$) are the h-Bézier coefficients of $B^n_h b$ (resp. $B^n_h c$) once raised to order N. Using (2.4), we easily deduce that

$$\begin{aligned} \langle B_n^h b,B_n^h c\rangle _{L^{\omega }_h} = \, \langle B^n_h b,B^n_h c\rangle _{E^{\omega }_{h}}. \end{aligned}$$

Therefore, given a polynomial P of degree n, the approximation problem

$$\begin{aligned} \min _{Q \in {\mathbb {P}}_m} ||P - Q||_{L^{\omega }_h} \end{aligned}$$

(6.3)

can be solved using pseudo-inverses. To proceed with giving the solution, we denote by W (resp. $\sqrt{W}$) the diagonal $(N+1)\times (N+1)$ weight matrix with diagonal elements $\omega _j$ (resp. $\sqrt{\omega _j})$; $j=0,1,\ldots ,N$. Denote by $p^h = (p_0^h,p_1^h,\ldots ,p_n^h)$ the h-Bézier coefficients of the polynomial P. The h-Bézier coefficients $q^h$ of the polynomial Q, solution to the minimization problem (6.3), are solutions to the least squares problem

$$\begin{aligned} \min _{q^h \in {\mathbb {R}}^{m+1}} \left| \left| \sqrt{W}A_{N,m} q^h - \sqrt{W} A_{N,n} p^h\right| \right| _2. \end{aligned}$$

(6.4)

Using the pseudo-inverse, the solution to (6.4) is given by

$$\begin{aligned} q^h = \left( \sqrt{W}A_{N,m}\right) ^{\dagger } \sqrt{W} A_{N,n} p^h = \Big ( A_{N,m}^{t} W A_{N,m}\Big )^{-1} A_{N,m}^{t} W A_{N,n} p^h. \end{aligned}$$

(6.5)

Note that if the matrix W is the identity matrix, then the solution $q^h$ is given by

$$\begin{aligned} q^h = A_{N,m}^{\dagger } A_{N,n} p^h, \end{aligned}$$

(6.6)

while by (4.2), we know that the solution $q^h$ is given by

$$\begin{aligned} q^h = A_{n,m}^{\dagger } p^h. \end{aligned}$$

(6.7)

The difference between the two proposed solutions (6.6) and (6.7) is that in order to use (6.6) we need to raise the degree of the original polynomial to order N, while the use of the second solution (6.7) requires degree raising to degree $n \le N$ only. Moreover, our proof for obtaining the solution (6.6) is rather trivial, while our proof for obtaining the solution (6.7) uses in some sense the fact that Bernstein operators are degree reducing. Comparing (6.6) and (6.7) we deduce that the fact that polynomial reduction in the discrete $L^h_2$-norm is equal to the best Euclidean approximation of the h-Bézier coefficients stems from the following relations between degree raising matrices:

$$\begin{aligned} A_{N,m}^{\dagger } A_{N,n} = A_{n,m}^{\dagger }, \quad m \le n \le N. \end{aligned}$$

(6.8)

Relations (6.8) are not valid for degree raising, or more appropriately, for dimension raising matrices of Gelfond–Bézier curves [2, 4] or Müntz –Bézier curves in general [3]. This may explain to some extent the lack of an analogous result to Corollary 3.1 for Chebyshev spaces other than the polynomial ones.

Using (6.5) and (4.3), we conclude

Theorem 6.1

The h-Bézier coefficients of the polynomial solution to the minimization problem (6.3) are given by

$$\begin{aligned} q^h = \Big ( A_{N,m}^{t} W A_{N,m}\Big )^{-1} A_{N,m}^{t} W A_{N,n} A_{N,n}^{\dagger } V_h, \end{aligned}$$

where $m \le n \le N$, $h = 1/N$, $V_h = \left( P(0),P(h),P(2h),\ldots ,P(1)\right) ^T$, $A_{i,j}$ are the degree raising matrices and W is the diagonal weight matrix.

7 Conclusion

In this work we provided a discrete analogue to the main Theorem in [14]. We also revealed the adequacy of using the h-Bernstein bases to solve the problem of discrete weighted degree reduction. The most pressing research direction in our agenda is to find a discrete counterpart to the results of [1] for the discrete degree reduction with discrete endpoints constraints. Also in our agenda is the generalization of this work to the multivariate setting.