# Formulating spline interpolation as a matrix problem

I have $N\times m$ data sets, with the same independent variables (time), i.e., $(t_i, y_{nmi})$. I want to interpolate (linear is fine, but understanding the generalizing for any set of basis functions would be awesome) them all onto a different grid (lets say $t'_i$). For speed/memory-efficiency I don't want to iterate over each $n,m$ an interpolate each one (especially since I'm using python/numpy), so I'm trying to formulate the problem using matrices which can then be computed more easily.

I understand (the basics of) how to fit a set of basis functions as a matrix problem.

Lets say we're fitting with a linear and sinusoidal model, so we have basis functions $[1, t, \sin(t), \cos(t)]$, so we can write,

$$X(t) = \begin{bmatrix} 1 & t_0 & \sin(t_0) & \cos(t_0) \\ \dots \\ 1 & t_i & \sin(t_i) & \cos(t_i) \\ \end{bmatrix}$$

with parameters, $B = [\beta_0, \beta_1, \beta_2, \beta_3]$, and then solve $Y = X(t) \, B$, (where $Y = y_{nm0}, y_{nm1}, ...$) to find the coefficients $B$...

$$B = (X^T X)^{-1} (X^T Y)$$

We can then interpolate using this fit to find $Y(t') = X(t') \, B$.

But how do you extend this to be piecewise defined?

There are lots of great wikipedia articles giving procedures of how to construct a spline (e.g. 1, 2, etc), but I haven't found any in which the extrapolation to a fully matricized implementation is clear...

For example, this source shows that you can write a linear spline as $S(x) = \sum_i^n y_i \, l_i(x)$, where,

$$l_i(x) = \begin{cases} \frac{x - x_{i-1}}{x_i - x_{i-1}}, & x \in [x_{i-1}, x_i] \\ \frac{x_{i+1} - x}{x_{i+1} - x_{i}}, & x \in [x_{i}, x_{i+1}] \\ 0 \end{cases}$$

But how can this be written as something like $X \, B$ above?

• @Glen_b, you were very helpful in understanding general fitting formalisms, perhaps you have a pointer here as well? – DilithiumMatrix Sep 26 '17 at 17:35
• the piece-wise part comes from the structure of matrices: they end up being sparse band matrices – Aksakal Sep 26 '17 at 17:46
• @Aksakal right, depending on the order of the fit/spline, we want to grab something like $y_{i-1}, y_i, y_{i+1}$ to construct the fit for section $i$, i.e $S_i(x)$... but I'm not sure how this fits together. – DilithiumMatrix Sep 26 '17 at 17:50
• what's not clear? there are so many little things that may be confusing, you better pinpoint the one you're struggling with. a general idea's the band matrix causes two things: a) each piece is a low order polynomial, and b) these are interlocked at each's ends. so, a) you need a few points to define low order polynomial thus the width of the bands in the matrix, and b) to make the spline smooth you need continuity of its derivatives, hence, overlapping the splines at the ends to ensure that – Aksakal Sep 26 '17 at 18:09
• – AdamO Sep 26 '17 at 18:40