I'm doing some self-study with ESL (http://www-stat.stanford.edu/~tibs/ElemStatLearn/download.html) and I've come to 5.2.1, the section on natural cubic smoothing splines and I'm having conceptual issues.
The prior section gives the basis for a linear spline with knots at $\xi_1$ and $\xi_2$ as
$h_1(X) = 1$
$h_2(X) = X$
$h_3(X) = (X-\xi_1)_+$
$h_4(X) = (X-\xi_2)_+$
After some thought this made intuitive sense to me. Left of the first knot you have a line of the form $\beta_1 + \beta_2X$, and as the line passes $\xi_1$ it's still a line with the same form, but now the coefficient on the $X$ is $\beta_2 + \beta_3$, and after the second knot the coefficient is $\beta_2 + \beta_3 + \beta_4$. It's also clear to me how at $X=\xi_1$ the two lines have equivalent values and so they meet. So far so good.
When the formula is extended to cubic splines in formula (5.3) I can't see it in my mind's eye quite as effectively but I can accept the analogous extension to a cubic polynomial of the form
$h_1(X) = 1$
$h_2(X) = X$
$h_3(X) = X^2$
$h_4(X) = X^3$
$h_5(X) = (X-\xi_1)_+^3$
$h_6(X) = (X-\xi_2)_+^3$
Now we're just combining the third term in the polynomial, first $\beta_4$, then $(\beta_4 + \beta_5)$, and finally $(\beta_4 + \beta_5 + \beta_6)$.
Formula (5.4) is where I run into trouble. It describes the basis for $K$ knots with
$N_1(X) = 1$
$N_2(X) = X$
$N_{k+2}(X) = d_k(X) – d_{K-1}(X)$
where
$d_k(X) = \frac{(X-\xi_k)^3_+ – (X-\xi_K)_+^3}{\xi_K – \xi_k}$
How does this form arise? Why isn't it problematic that the $d_k$ expression is undefined for $K=k$?
Best Answer
First it is not the basis but a basis: We want to build a basis for $K$ knots of natural cubic splines.
According to the constraints, "a natural cubic splines with $K$ knots is represented by $K$ basis functions". A basis is described with the $K$ elements $N_1, \ldots, N_K$. Note that "$d_K$" is never used to define any of those elements. [This paragraph is explained in details in this answer https://stats.stackexchange.com/q/233286 ]
I dug into the exercise that $N_1, \ldots, N_K$ is a basis for $K$ knots of natural cubic splines. (this is Ex. 5.4 of the book)
The knots $(\xi_k)$ are fixed. With the truncated power series representation for cubic splines with $K$ interior knots, we have this linear combination of the basis: $$f(x) = \sum_{j=0}^3 \beta_j x^j + \sum_{k=1}^K \theta_k (x - \xi_k)_{+}^{3}.$$
For now, there are $K+4$ degree of freedom, and we will add constraints to reduce it (we already know we need $K$ elements in the basis finally).
Part I: Conditions on the coefficients
We add the constraint "the function is linear beyond the boundary knots". We want to show the four following equations: $\beta_2 = 0$, $\beta_3 = 0$, $\sum_{k=1}^K \theta_k = 0$ and $\sum_{k=1}^K \theta_k \xi_k = 0$.
Proof:
For $x < \xi_1$, $$f(x) = \sum_{j=0}^3 \beta_j x^j$$ so $$f''(x) = 2 \beta_2 + 6 \beta_3 x.$$ The equation $f''(x)=0$ leads to $2 \beta_2 + 6 \beta_3 x = 0$ for all $x < \xi_1$. So necessarily, $\beta_2 = 0$ and $\beta_3 = 0$.
For $x \geq \xi_K$, we replace $\beta_2$ and $\beta_3$ by $0$ and we obtain: $$f(x) = \sum_{j=0}^1 \beta_j x^j + \sum_{k=1}^K \theta_k (x- \xi_k)^3$$ so $$f''(x) = 6 \sum_{k=1}^K \theta_k (x-\xi_k).$$
The equation $f''(x)=0$ leads to $\left( \sum_{k=1}^K \theta_k \right) x - \sum_{k=1}^K \theta_k \xi_k = 0$ for all $x \geq \xi_k$. So necessarily, $\sum_{k=1}^K \theta_k = 0$ and $\sum_{k=1}^K \theta_k \xi_k = 0$.
Part II: Relation between coefficients
We get a relation between $\theta_{K-1}$ and $\left( \theta_{1}, \ldots, \theta_{K-2} \right)$.
Using equations $\sum_{k=1}^K \theta_k = 0$ and $\sum_{k=1}^K \theta_k \xi_k = 0$ from Part I, we write: $$0 = \left( \sum_{k=1}^K \theta_k \right) \xi_K - \sum_{k=1}^K \theta_k \xi_k = \sum_{k=1}^K \theta_k \left( \xi_K - \xi_k \right) = \sum_{k=1}^{K-1} \theta_k \left( \xi_K - \xi_k \right).$$
We can isolate $\theta_{K-1}$ to get: $$\theta_{K-1} = - \sum_{k=1}^{K-2} \theta_k \frac{\xi_K - \xi_k}{\xi_K - \xi_{K-1}}.$$
Part III: Basis description
We want to obtain the base as described in the book. We first use: $\beta_2=0$, $\beta_3=0$, $\theta_K = -\sum_{k=1}^{K-1} \theta_k$ from Part I and replace in $f$:
\begin{align*} f(x) &= \beta_0 + \beta_1 x + \sum_{k=1}^{K-1} \theta_k (x - \xi_k)_{+}^{3} - (x - \xi_K)_{+}^{3} \sum_{k=1}^{K-1} \theta_k \\ &= \beta_0 + \beta_1 x + \sum_{k=1}^{K-1} \theta_k \left( (x - \xi_k)_{+}^{3} - (x - \xi_K)_{+}^{3} \right). \end{align*}
We have: $(\xi_K - \xi_k) d_k(x) = (x - \xi_k)_{+}^{3} - (x - \xi_K)_{+}^{3}$ so:
$$f(x) = \beta_0 + \beta_1 x + \sum_{k=1}^{K-1} \theta_k (\xi_K - \xi_k) d_k(x).$$
We have removed $3$ degree of freedom ($\theta_K$, $\beta_2$ and $\beta_3$). We will proceed to remove $\theta_{K-1}$.
We want to use equation obtained in Part II, so we write: $$f(x) = \beta_0 + \beta_1 x + \sum_{k=1}^{K-2} \theta_k (\xi_K - \xi_k) d_k(x) + \theta_{K-1} (\xi_K - \xi_{K-1}) d_{K-1}(x).$$
We replace with the relationship obtained in Part II:
\begin{align*} f(x) &= \beta_0 + \beta_1 x + \sum_{k=1}^{K-2} \theta_k (\xi_K - \xi_k) d_k(x) - \sum_{k=1}^{K-2} \theta_k \frac{\xi_K - \xi_k}{\xi_K - \xi_{K-1}} (\xi_K - \xi_{K-1}) d_{K-1}(x) \\ &= \beta_0 + \beta_1 x + \sum_{k=1}^{K-2} \theta_k (\xi_K - \xi_k) d_k(x) - \sum_{k=1}^{K-2} \theta_k (\xi_K - \xi_k) d_{K-1}(x) \\ &= \beta_0 + \beta_1 x + \sum_{k=1}^{K-2} \theta_k (\xi_K - \xi_k) (d_k(x) - d_{K-1}(x)). \end{align*}
By definition of $N_{k+2}(x)$, we deduce: $$f(x) = \beta_0 + \beta_1 x + \sum_{k=1}^{K-2} \theta_k (\xi_K - \xi_k) N_{k+2}(x).$$
For each $k$, $\xi_K - \xi_k$ does not depend on $x$, so we can let $\theta'_k := \theta_k (\xi_K - \xi_k)$ and rewrite:
$$f(x) = \beta_0 + \beta_1 x + \sum_{k=1}^{K-2} \theta'_k N_{k+2}(x).$$
We let $\theta'_1 := \beta_0$ and $\theta'_2 := \beta_1$ to get: $$f(x) = \sum_{k=1}^{K} \theta'_k N_{k}(x).$$
The family $(N_k)_k$ has $K$ elements and spans the desired space of dimension $K$. Furthermore, each element verifies the boundary conditions (small exercise, by taking derivatives).
Conclusion: $(N_k)_k$ is a basis for $K$ knots of natural cubic splines.