# Proving that a natural cubic spline optimizes a smoothing problem

The GAM book by Hastie and Tibshirani 1990 claims that the natural cubic spline is the function $$f$$ which minimizes the least squares objective

$$\sum_{i=1}^n(y_i-f(x_i))^2 +\lambda\int_a^b f''(t)^2dt$$

They give this as an exercise, where they define the Langrangian functional $$F(f) = \int_a^b f''(x)^2dx +\rho\left[\sum_{i=1}^n(y_i-f(x_i))^2 - \sigma +z^2\right]$$ ($$\sigma$$ is some slack variable, and $$z$$ is an "auxiliary" variable) and give some hints:

They also refer to Reinsch 1967.

How do I prove section (i)?

I assume (i) doesn't involve $$\sigma$$ and $$z$$. This is my derivation so far, but if you have a better one, please tell me!

If I focus on the 1st term in $$F$$, after adding $$\delta h(x)$$, differentiating by $$\delta$$ (and equating $$\delta=0$$, which they didn't mention) I'm left with $$2\int_a^b f''(x)h''(x)dx = 2\sum_{i=1}^n \int_{x_i}^{x_{i+1}} f''(x)h''(x)dx$$

Since $$h$$ is only twice differentiable, I assume the integration by parts is done to find the anti-derivative of $$h$$. Doing so, twice, results in:

$$= 2\sum_{i=1}^n \left[f''(x)h'(x)|_{x_i}^{x_{i+1}} - f'''(x)h(x)|_{x_i}^{x_{i+1}} +\int_{x_i}^{x_{i+1}} f''''(x)h(x)dx\right]$$

Since $$h(x)$$ is an arbitrary function, I can somehow reason why $$f''''(x)=0 \; \forall x$$. Doing the same thing for the 2nd term of $$F$$ will result in $$2\rho\sum_{i=1}^n (f(x_i)-y_i)h(x_i)$$

So I can infer from this that the $$f'''({x_i}_-)-f'''({x_i}_+)=\rho \cdot (y_i-f(x_i))$$

Maybe I can somewhat reason that $$f''$$ must also be equal at the knots. But, what about $$f'$$?

• I think it must be a constraint that $f’$ should take prescribed values at the knots. Consider the initial data $f(-1)=0$, $f’(-1)=2$, $f(1)=0$, $f’(1)=-2$. Without the constraint this is minimized by $f(x)=0$, rather than something reasonable like $f(x)=1-x^2$.
– user225256
Commented Jun 6 at 13:01

Given $$a < x_1 < x_2 < \dotso < x_N < b$$ (with $$N \ge 2$$) and values $$f(x_i)$$ at the knots. Show that an interpolating function $$g$$ defined on $$[a, b]$$ minimizing $$\int_a^b g''(t)^2 \; dt$$ is a natural cubic spline.
• Let $$\tilde{g}$$ be any other interpolating and differentiable function on $$[a, b]$$, and $$h = \tilde{g} - g$$. Then (partial integration) $$\int_a^b g''(t) h''(t) \; dt = -\int_a^b g'''(t) h'(t)\; dt \\ = -\sum_{j=1}^{N-1} g'''(x_j) \int_{x_{j}}^{x_{j+1}} h'(t)\; dt \\ = -\sum_{j=1}^{N-1} g'''(x_j)\left\{ h(t_{j+1}-h(t_j) \right\} =0$$ The first equality uses the condition that $$g$$ is a natural spline, so its second derivative is zero at $$a, b$$. The second splits the integration on subintervals and uses the fact that the third derivative of a cubic polynomial is a constant. The third follows since $$h=0$$ at the knots.
$$\int_a^b \tilde{g}''^2 =\int_a^b (g'' + h'')^2 \\ =\int_a^b g''^2 + 2\int_a^b g'' h'' +\int_a^b h''^2 \\ = \int_a^b g''^2 + \int_a^b h''^2 \ge \int_a^b g''^2$$ (and there can be equality only if $$h''$$ is zero on $$[a, b]$$, meaning that $$h$$ must be linear, such that it could be incorporated in the natural cubic spline $$g$$). Finally
• The optimization problem $$\min_f \left[ \sum_1^N (y_i - f(x_i))^2 +\lambda \int_a^b f''(t)^2\; dt \right]$$ the solution $$f$$ must be a natural cubic spline. Suppose we have found some candidate solution $$f$$. Replace it by some natural cubic spline $$g$$ that interpolated $$f$$ at the knots, then the first term in the criterion is unchanged, while the second is lowered, unless $$f$$ already is a natural cubic spline.