Skip to main content

Training Sets

Lagrange Optimal points

Our first candidate for a training set are the Lagrange optimal points which are based on the Lagrange characteristic polynomials.

Let \Pi_\beta^K=\{\chi:\mathbb{R}^K\to \mathbb{R}:\chi \text{ polynomial with } \text{deg}(\chi)\leq \beta\} be the set of polynomials on \mathbb{R}^K with total degree at most \beta and let q=\dim(\Pi_\beta^K)=\binom{\beta+K}{K}. For X_{\beta,K}=\{\xi_j\}_{j=1}^q\subset\Gamma consider \{l_n\}_{n=1}^q , the Lagrange characteristic polynomials, defined so that

l^n(\xi_j)=\delta_{nj}, n,j\in\{1,\ldots,q\} which form a basis of \Pi_\beta^K. They can be written in terms of Vandermonde determinants,

l^n(x)=\frac{\det[V(\xi_1,\ldots,\xi_{n-1},x,\xi_{n+1},\ldots, \xi_q)]}{\det[V(\xi_1,\ldots,\xi_q)]}, \quad n=1,\ldots,q,

where  V\in\mathbb{R}^{q\times q} is such that (V(\lambda_1,\lambda_2, \ldots,\lambda_q))_{jn}=l^n(\lambda_j). Recall that the Lebesgue constant  \lambda_{q,K} of  X_{\beta,K} is defined by,

 \lambda_{q,K}:= \max_{x\in\Gamma} \sum_{n=1}^q|l^n(x)|.

We are interested in the solutions of the following optimization problem,

$ X^*_{\beta,K}=\underset{\{\xi_j\}_{j=1}^q}{\arg\min}\max_{x\in\Gamma} \sum_{n=1}^{q}|l^{n}(x)|.\quad (3) $

These solutions constitute the definition of the Lagrange optimal points.

Lagrange optimal points

Clenshaw-Curtis points

Consider the N-th degree Chebyshev polynomial T_N(x) defined by T_N(cos(\theta))=cos(N\theta). The Gauss-Chebyshev-Lobatto points (of degree  N ) are the extrema in [-1,1] of T_N(x). They are given by the explicit formula:

 x_n=cos\bigg(\frac{n\pi}{N}\bigg) \smallskip n=0,\ldots,N.

The Clenshaw-Curtis points are the nested subsequence of such points with N(i)=2^{i-1}+1  (i.e. \{x_n\}_{1 \le n \le N(i)} \subset \{x_n\}_{1 \le n \le N(i+1)})

A property of the Clenshaw-Curtis points that can be easily deduced from the explicit formula above is the asymptotic (for N large) clustering of points near the boundary (i.e. near -1 and 1).

Clenshaw-Curtis (Tensor Product)

Sparse Grids

Previously we discussed the one dimensional Clenshaw-Curtis points and now we would like to go to an arbitrary dimension  K > 1. As soon as we try that we run into the Curse of Dimensionality: If we took the full tensor product of N one dimensional points we end up with N^K points in K dimensions which is far too big a number for numerical schemes. The technique of Sparse Grids allows us to overcome this problem.

We start off with N one dimensional points \{x_1,\dots x_N\}. We would like to build a collection H^{s}_{K,q} of K-dimensional points, our sparse grid. Let i=(i_1,\ldots,i_K) be a multi-index and consider the norm |i|_{l_1}= \Sigma_{k=1}^{K}i_k and let q \geq K.

Take a nested family of collections of points \{\Theta^{j}\} so that

\Theta^{j} \subset \{x_1,\dots x_N\} for all j, \Theta^{j} \subset \Theta^{l} if l>j and |\Theta^{j}|=2^{j-1}+1.

Now define the sparse grid in K dimensions as follows,

 H_{K,q}^s= \underset{q-K+1 \leq |i|_{{l}_{1}} \leq q}{\bigcup} \big( \Theta^{i_1} \times \ldots \times \Theta^{i_K} \big).

One should note that even though the actual points in the sparse grid depend on how we chose the nested family \{\Theta^j\}, the cardinality of the sparse grid is independent of this choice.

Sparse Grid

Other points that we have used as training sets are :

  • Uniform Grid points.
  • Random points.