Chebyshev function approximation using FSharp.Stats¶

Summary: This blogpost introduces the concept of function approximation by using knots spaced according to Chebyshev.

This post is inspired by M. Scroggs blog post and shows how to perform function approximation in F#.

Lets start by generating data in a two dimensional space. The aim is to interpolate the data using a single polynomial. Why in certain cases this is a sensible thing to do will be discussed later. We'll need FSharp.Stats for all the data handling and Plotly.NET for visualization.

Defining data¶

We define a short data sample, that should be interpolated using polynomials, and visualize it using a scatter plot.

The problem¶

Your task is to approximate a function that interpolate these data points to get predictions of the regions between the knots. The simplest and most common way to solve this problem is to just connect the points by straight line segments. This linear segments can be predicted using linear splines from FSharp.Stats.Interpolation:

The drawback of this strategy is the discontinuouity of the function. At each knot, the function value is defined, but its slope and curvature isn't. Additionally the segments are not influenced by neighbouring segments. While integration is possible in principle, there is no single function that enables its calculation. You have to sum up the individual segment areas individually.

Polynomials to the rescue¶

A solution is to use interpolationg polynomials. Polynomials are easy to define and differentiation as well as integration is straight forward. Any data can be interpolated by a single function with a degree of #points-1. With the example data the polynomial has the form of: $$f(x) = ax^{15} + bx^{14} + cx^{13} + ... + dx^2 + ex + g$$

As proved in the cell above, there are n coefficients defining a polynomial of degree n-1. To check the resulting polynomial curve, the function is plotted with a small step size to investigate the regions between the knots in detail

Runge's phenomenon¶

As seen above the resulting interpolating function is worse than the connecting straights. A common problem of polynomial interpolation is Runge's phenomenon, also called Runge's spikes. The only constraints the function must satisfy is to pass through the knots. Obviously between the knots the prediction is quite bad, because it wasn't optimised to be smooth (as in e.g. cubic spline interpolation).

This overfitting gets more extreme the nearer it is to the outmost segments. Thereby the interpolation function is rendered useless for predicting internal points or calculating slopes/integrals. Imagine you should calculate the integral of the range [0,0.2], which obviously should be approximately 1.05 (xRange=0.2, yRange=5.25), but definetely greater than 0.

Because of the spikes, the integral is totally unintuitive and its likely, that the result is wrong. It would be detrimental if this function approximation is used to investigate signal properties.

A clever way of reducing the occurence of these wiggles is to use an x value spacing accrding to Chebyshev. Thereby the x values are not sorted equally spaced like it is common for such interpolation tasks. Instead, they are expanded in the signal center and compressed to the outward knots. This is achieved by streching the x values to a semicircle and from there projecting the x values back to a linear axis. In the picture seen below (from M.Scroggs), x values are equally spaced onto a semicircle and subsequently back projected to the linear x axis. Thereby the desired spacing is achieved.

Mathematically the transformation it is defined within the interval [a,b] as:

In FSharp.Stats this can be done as follows. The spacing of the x values is visualized as scatter plot.

Of course the corresponding y values are missing. Here linear spline are used to predict the new function values at the chebyshev knots (Note: Alternatively, you could predict them by using cubic interpolating splines).

With the new data, a simple polynomial interpolation is performed as before. Of course these procedures can be achieved directly by calling Interpolation.Approximation.approxWithPolynomialFromValues.

Using the determined polynomial coefficients, the standard approach for fitting can be used to plot the signal together with the function approximation. The chebyshev spacing of the x-nodes drastically reduces the overfitting in the outer areas of the signal.

Now we can again approximate the integral of the function between [0,0.2]. The result now should be much closer at the expected value of 1.05.

Approximating a polynomial from a function¶

Instead of starting from data points you can also transform any function you like to easy-to-use polynomials. This comes handy when investigating function properties with complex functions that cannot be differentiated easily. As seen below, a function with y axial symmetry is approximated. While an even number of knots very well approximates the tails, an uneven number precisely predicts the center point. The simple interpolation with equally spaced points nicely depicts a drastic overshoot (Runge's phenomenon).

Use cases¶

• function approximaion of nonlinear relations (e.g. Schrödingers function) with only a few terms
• optimization techniques
• numerical solution of integral equations
• improving wavelet transforms by enhancing the accuracy in outer areas

Drawbacks¶

• The Chebychev knots are interpolated linearly. The points that are interpolated don't exist in the original data. As alternative one may use cubic splines to get a better approximation of the transformed knots, but since the presented strategy aims to minimize computing ressources, it wouldn't make much sense to use cubic splines and then go back to polynomials.

Other techniques to mitigate Runge's phenomenon¶

• using lower degree polynomials: Thereby you automatically move to linear regression instead of interpolation
• switching to splines: Splines are perfect to reduce high oscillating behaviour of regression curves

References¶

• M. Scroggs blog post with its Github repo
• Youtube - Beware the Runge Spikes! from Matt Parker
• FSharp.Stats documentation