# Data Interpolation by Near-Optimal Splines with Free Knots Using Linear Programming
## 1 Introduction  
When an exact functional form in a model is unknown, it is often described by measurements represented by available data points and some expected assumptions about the function. Traditionally, data points were interpolated by polynomials more frequently than by spline functions. In a basic way, spline theory deals with a simple but important question of how one uses a _lower degree piecewise_ polynomial function rather than a _single larger degree_ polynomial to represent given data and attendant properties. Spline theory attempts to obtain appropriate problem formulations to obtain the spline, its existence and characterization of solutions, and properties and computation of such functions. While polynomials have many desirable properties, polynomial interpolation suffers from Runge's Phenomena [1]--a polynomial oscillation at the edges of an interval. With large data, the derivatives of a single polynomial at each of the data points tend to grow, thereby resulting in multiple local extrema. In particular, it has been shown that polynomials, extensively used, for example, in thermometry [2], are not capable of recovering local behavior with good quantifiable accuracy. Spline interpolation, on the other hand, tends to greatly reduce oscillation between data points due to lower degree of polynomials. Cubic splines, with a multitude of applications, in particular, have been shown to be able to reproduce local characteristics well [2]. In addition, computationally, the problem of finding a polynomial interpolating a large number of data points is equivalent to inverting a Vandermonde matrix with a large condition number, thereby rendering theinterpolation problem intractable, inefficient, and unstable in computer implementations [3]. On the other hand, the great flexibility of splines, resulting from the use of several lower degree polynomials smoothly connected at optimally chosen points (usually referred to as \"knots\"), resolves the major problems mentioned above effectively. In spline applications, the following features are desired: 1. representation of the function with lower degree polynomials, which leads to efficient computations as well as a good approximation of the original function, and 2. continuous or essentially bounded derivatives (often second and third derivatives in most applications, for quadratic and cubic splines, respectively). The boundedness of derivatives in the interpolation by splines is natural since one can always have a function interpolating the given point with arbitrarily high derivatives, for example, the second derivative in the context of quadratic splines. In function approximation, therefore, to estimate the most favorable possible error in function approximation, one would like to determine the smallest curvature (the second derivative) possible of a function that interpolates the points by finding the optimal quadratic spline [4]. Many important applications require interpolation by splines. The recent and ongoing COVID-19 pandemic has spurred advances in spline-related research; specifically, splines have been shown to be useful for modeling and forecasting the spread of COVID-19 [5; 6; 7; 8], and COVID-19 trends [9]. In [10], splines were also used to analyze the relationship between the ambient temperature and the transmission of COVID-19. Moreover, splines were shown to be useful for capturing the nonlinear relationship between fasting blood glucose levels and risk of intensive care unit admission for COVID-19 patients [11] in comparison to other conventional linear, dichotomous, or categorical methods. Optimal spline with free knots as well as more recent application areas of splines will be briefly discussed in Section 2. Section 3 provides our linear programming formulation to obtain near-optimal splines with free knots interpolating a given set of data points efficiently and with the desired level of accuracy.