Splines and Series Methods

For $p=0$, support, piecewise degree, and nonnegativity follow from the indicator definition in [F1]. Inductively, each degree-$p$ term is a lower-degree spline multiplied by an affine factor; on the lower-degree spline's support that factor is nonnegative, and the two supports lie inside $[{\xi }_j,{\xi }_{j+p+1}]$. Thus support, degree at most $p$, and nonnegativity hold for every $p$.

Let the distinct interior knots be ${\eta }_1<\cdots <{\eta }_s$ with multiplicities ${\mu }_1,\dots ,{\mu }_s$. For $k\ge 1$ set $u_{r,k}(x)=(x-{\eta }_r{)}^k{\mathbf{1}}_{[{\eta }_r,\mathrm{\infty })}(x)$ and set $u_{r,0}(x)={\mathbf{1}}_{[{\eta }_r,\mathrm{\infty })}(x)$; the value at ${\eta }_r$ follows the right-cell convention of [F1]. The functions $1,x,\dots ,x^p$ together with $u_{r,k}$ for $p-{\mu }_r+1\le k\le p$ span $S_{p,\xi }$: start with the polynomial on the first interval, then at each knot the difference of adjacent pieces has its derivatives through $p-{\mu }_r$ equal to zero, so it is a linear combination of the listed powers, including the right-continuous step when ${\mu }_r=p+1$. They are independent because restriction to successive knot intervals first forces the initial polynomial coefficients, then each new knot's coefficients, to vanish. Thus $\dim S_{p,\xi }=p+1+{\sum }_r{\mu }_r=n$.

Define ${\psi }_{j,0}(y)=1$ and ${\psi }_{j,d}(y)={\prod }_{r=1}^d(y-{\xi }_{j+r})$. When ${\xi }_{j+d}>{\xi }_j$, factoring ${\psi }_{j,d-1}$ gives $(y-x){\psi }_{j,d-1}(y)=\frac{x-{\xi }_j}{{\xi }_{j+d}-{\xi }_j}{\psi }_{j,d}(y)+\frac{{\xi }_{j+d}-x}{{\xi }_{j+d}-{\xi }_j}{\psi }_{j-1,d}(y)$. Fix a nonempty cell $[{\xi }_m,{\xi }_{m+1})$. At degree zero its sole nonzero indicator is $B_{m,0,\xi }$, so the local identity holds. Inductively, the degree-$(d-1)$ local sum has indices $m-d+1\le j\le m$. For every such index, ${\xi }_j\le {\xi }_m<{\xi }_{m+1}\le {\xi }_{j+d}$, so the displayed identity has a strictly positive denominator. Multiply that local sum by $y-x$, apply the identity, and regroup with [F1]. The two extra lower-degree functions $B_{m-d,d-1,\xi }$ and $B_{m+1,d-1,\xi }$ vanish on the cell by support, even when their supports are empty; their recurrence terms are zero under [F1]. Thus $(y-x{)}^d={\sum }_{i=m-d}^m{\psi }_{i,d}(y)B_{i,d,\xi }(x)$ for $0\le d\le p$, and in particular for $d=p$.

Differentiate the identity in step 2.1 exactly $p-k$ times in $y$ and set $y=0$, for each $0\le k\le p$. Since $\frac{d^{p-k}}{d{y}^{p-k}}(y-x{)}^p{\mathrm{\mid }}_{y=0}=\frac{p!}{k!}(-x{)}^k$, this yields $x^k={\sum }_{i=m-p}^m[(-1{)}^k\frac{k!}{p!}{\psi }_{i,p}^{(p-k)}(0)]B_{i,p,\xi }(x)\mathrm{.}$ The coefficients do not depend on $m$, so this is a single expansion valid on every knot interval. Linear combination proves reproduction of every member of ${\mathcal{P}}_p$; taking left limits extends the expansion to $b$.

Fix an open nonempty knot interval $({\xi }_m,{\xi }_{m+1})$ and $p\ge 1$. The $p+1$ dual polynomials ${\psi }_{i,p}$, $m-p\le i\le m$, form a basis of ${\mathcal{P}}_p$ in $y$: differentiating the identity of step 2.1 in $x$ at an interior point $x_0$ shows that their span contains $(y-x_0{)}^k$ for every $0\le k\le p$. For $m-p+1\le i\le m$, the span ${\xi }_{i+p}-{\xi }_i$ is strictly positive and factoring gives ${\psi }_{i,p}-{\psi }_{i-1,p}=-({\xi }_{i+p}-{\xi }_i){\psi }_{i,p-1}$. Differentiate the degree-$p$ local identity in $x$ and use the degree-$(p-1)$ identity and this difference formula to obtain ${\sum }_{i=m-p}^m{B}_{i,p,\xi }^{\mathrm{\prime }}{\psi }_{i,p}=p{\sum }_{i=m-p+1}^m\frac{B_{i,p-1,\xi }}{{\xi }_{i+p}-{\xi }_i}({\psi }_{i,p}-{\psi }_{i-1,p})$. Comparison in the dual basis yields $B_{j,p,\xi }^{\mathrm{\prime }}=p(\frac{B_{j,p-1,\xi }}{{\xi }_{j+p}-{\xi }_j}-\frac{B_{j+1,p-1,\xi }}{{\xi }_{j+p+1}-{\xi }_{j+1}})$ on this interval. The boundary lower-degree terms vanish by support; any zero denominator corresponds to an identically zero lower-degree spline and its term is zero. For indices outside the active range both sides vanish by support.

Taking $k=0$ in step 3.1 gives ${\sum }_{i=m-p}^m{B}_{i,p,\xi }(x)=1$. Step 3.1 also shows that these $p+1$ active functions span ${\mathcal{P}}_p$ on the interval. Because $\dim {\mathcal{P}}_p=p+1$, they are linearly independent there and are a local basis.

Induct on $p$. If the knot multiplicity $\mu \le p-1$, the lower-degree splines in the recurrence are continuous there by induction, so the recurrence makes $B_{j,p,\xi }$ continuous; the derivative formula then makes its derivative $C^{p-1-\mu }$, hence $B_{j,p,\xi }\in C^{p-\mu }$. If $\mu =p$, a B-spline whose support crosses the repeated knot has one nonzero piece on either side, namely $(x-{\xi }_j{)}^p\mathrm{/}({\xi }_{j+p}-{\xi }_j{)}^p$ and $({\xi }_{j+p+1}-x{)}^p\mathrm{/}({\xi }_{j+p+1}-{\xi }_{j+1}{)}^p$; both one-sided limits equal $1$, while any B-spline not crossing it has zero endpoint value there. If $\mu =p+1$, the required order is $C^{-1}$ and no matching is asserted.

The smoothness and piecewise-degree properties from steps 1.1 and 4.2 put every B-spline in $S_{p,\xi }$. If a linear combination of all $n$ B-splines is zero, then on every nonempty knot interval its active coefficients vanish by the local basis property in step 4.1. Each B-spline has a nonempty support interval by the clamped-knot hypothesis, so every coefficient occurs on at least one such interval and is zero. The B-splines are therefore $n$ independent members of the $n$-dimensional space in step 1.2, hence form its basis. The unique global expansion includes every polynomial from step 3.1.

Put $h_i=x_{i+1}-x_i$ and $d_i=(y_{i+1}-y_i)\mathrm{/}{h}_i$. For $r=2$ there are no interior second derivatives to solve. For $r\ge 3$, let $A$ be the $(r-2)\times (r-2)$ symmetric tridiagonal matrix with diagonal entry $2(h_{i-1}+h_i)$ in row $i$ and adjacent off-diagonal entries $h_i$. For a nonzero vector $v=(v_2,\dots ,v_{r-1})$, using $2v_i{v}_{i+1}\ge -v_i^2-v_{i+1}^2$ gives $v^{T}Av\ge {\sum }_{i=2}^{r-1}(h_{i-1}+h_i)v_i^2>0.$ Thus $A$ is positive definite and invertible, so the displayed system has exactly one solution $M_2,\dots ,M_{r-1}$.

On $[x_i,x_{i+1}]$, define $s_i(x)=\frac{M_i(x_{i+1}-x{)}^3+M_{i+1}(x-x_i{)}^3}{6h_i}+(y_i-\frac{M_i{h}_i^2}{6})\frac{x_{i+1}-x}{h_i}+(y_{i+1}-\frac{M_{i+1}{h}_i^2}{6})\frac{x-x_i}{h_i}\mathrm{.}$ Direct substitution gives $s_i(x_i)=y_i$, $s_i(x_{i+1})=y_{i+1}$, and $s_i^{\mathrm{\prime }\mathrm{\prime }}(x_i)=M_i$, $s_i^{\mathrm{\prime }\mathrm{\prime }}(x_{i+1})=M_{i+1}$. Its left and right endpoint slopes are respectively $s_i^{\mathrm{\prime }}(x_i)=d_i-M_i{h}_i\mathrm{/}3-M_{i+1}{h}_i\mathrm{/}6$ and $s_i^{\mathrm{\prime }}(x_{i+1})=d_i+M_i{h}_i\mathrm{/}6+M_{i+1}{h}_i\mathrm{/}3$. Equating the right slope from $s_{i-1}$ and the left slope from $s_i$ gives the tridiagonal equation at $x_i$. Hence the pieces join $C^1$; their second derivatives are linear with the same nodal values, so they join $C^2$. At the extreme knots $M_1=M_r=0$, so adjoining the tangent line gives the required linear tails and preserves $C^2$. For $r=2$, the formula is the straight line between the two values and the same endpoint argument applies.

Any natural cubic interpolant has nodal second derivatives with $M_1=M_r=0$. Equality of its adjacent endpoint slopes forces the displayed tridiagonal equations, so by step 1.1 its nodal second derivatives equal the constructed ones. On each interval, the difference from $s_i$ is a cubic with zero second derivative at both endpoints; its second derivative is affine and therefore zero throughout, so the difference is affine and vanishes at both endpoint values. It is identically zero. Thus the interpolant is unique.

Let $g\in W^{2,2}(a,b)$ and use the continuous representative in [F2] for $g$ and $g^{\mathrm{\prime }}$. The Countable Choice convention in [F1] and the choice hypotheses for [F2] are available by [F5] and [A1]. Interpolate the values $g(t_j)$ by the natural cubic $s$ from [F3], and put $h=g-s$. Then $h(t_j)=0$ for every $j$. On each interval between distinct knots, $s^{\mathrm{\prime }\mathrm{\prime }\mathrm{\prime }}$ is constant; on the two linear tails, $s^{\mathrm{\prime }\mathrm{\prime }}=s^{\mathrm{\prime }\mathrm{\prime }\mathrm{\prime }}=0$.

The natural spline with knots $t_1,\dots ,t_r$ is uniquely determined by its nodal vector $z=(s(t_1),\dots ,s(t_r))\in {\mathbb{R}}^r$ by [F3]. The tridiagonal system in the interpolation proof is linear in its data, and the interval formula is linear in the nodal values and second derivatives; hence $z\mapsto s_z^{\mathrm{\prime }\mathrm{\prime }}$ is linear into the finite-dimensional space of piecewise-linear functions. Therefore $R(z)=\int \mathrm{\mid }{s}_z^{\mathrm{\prime }\mathrm{\prime }}{\mathrm{\mid }}^2$ is a finite nonnegative quadratic form. In these coordinates $J(s)={\sum }_j{\sum }_{i:x_i=t_j}(y_i-z_j{)}^2+\lambda R(z)$. The data term has positive-definite diagonal quadratic part because every $t_j$ occurs at least once. Adding the nonnegative quadratic form $\lambda R$ leaves a positive-definite quadratic objective, which has a unique minimizer by completing the square.

On each knot interval, the product $s^{\mathrm{\prime }\mathrm{\prime }}{h}^{\mathrm{\prime }}$ is absolutely continuous, so the fundamental theorem of calculus gives $\int s^{\mathrm{\prime }\mathrm{\prime }}{h}^{\mathrm{\prime }\mathrm{\prime }}=[s^{\mathrm{\prime }\mathrm{\prime }}{h}^{\mathrm{\prime }}]-\int s^{\mathrm{\prime }\mathrm{\prime }\mathrm{\prime }}{h}^{\mathrm{\prime }}$. Summing over the intervals, the interior boundary terms cancel because $s^{\mathrm{\prime }\mathrm{\prime }}$ and $h^{\mathrm{\prime }}$ are continuous. At each outer endpoint, $s^{\mathrm{\prime }\mathrm{\prime }}=0$ either on a linear tail or by the natural condition when that endpoint is a knot. The remaining terms are $-s^{\mathrm{\prime }\mathrm{\prime }\mathrm{\prime }}{\mathrm{\mid }}_{(t_j,t_{j+1})}(h(t_{j+1})-h(t_j))=0$. Thus ${\int }_a^b{s}^{\mathrm{\prime }\mathrm{\prime }}{h}^{\mathrm{\prime }\mathrm{\prime }}=0$.

Since $g=s+h$, expanding the square and applying step 2.1 yields ${\int }_a^b\mathrm{\mid }{g}^{\mathrm{\prime }\mathrm{\prime }}{\mathrm{\mid }}^2={\int }_a^b\mathrm{\mid }{s}^{\mathrm{\prime }\mathrm{\prime }}{\mathrm{\mid }}^2+{\int }_a^b\mathrm{\mid }{h}^{\mathrm{\prime }\mathrm{\prime }}{\mathrm{\mid }}^2\mathrm{.}$ Also $s(x_i)=g(x_i)$ for every observed input, so their data residual terms agree. Therefore $J(g)=J(s)+\lambda {\int }_a^b\mathrm{\mid }{h}^{\mathrm{\prime }\mathrm{\prime }}{\mathrm{\mid }}^2\ge J(s)$, with equality only if $h^{\mathrm{\prime }\mathrm{\prime }}=0$ almost everywhere.

Let $s_{\ast }$ be this finite-dimensional minimizer. Step 3.1 shows $J(g)\ge J(s_{\ast })$ for every $g\in W^{2,2}$. If equality holds, then $h^{\mathrm{\prime }\mathrm{\prime }}=0$ almost everywhere, so by [F2] $h$ is affine; its zero values at the two distinct knots $t_1,t_r$ force $h=0$. Thus $s_{\ast }$ is the unique minimizer over the full Sobolev class, and its natural cubic form and linear tails are those of [F3].

On any neighborhood $J=[c,d]$, use the continuous representatives of $D^{j}f$, $0\le j\le l$, supplied by [F2]. Their Sobolev-class convention [F1] and the choice hypotheses for [F2] are available under [A1] by [F5]. Repeated integration by parts for absolutely continuous functions gives the Taylor identity $f(x)-T_{c,l}f(x)=\frac{1}{l!}{\int }_c^x(x-t{)}^l{D}^{l+1}f(t)dt,$ where $T_{c,l}f(x)={\sum }_{j=0}^l{D}^{j}f(c)(x-c{)}^j\mathrm{/}j!$. For completeness, the case $l=0$ is the increment formula in [F2]; passing from order $l-1$ to $l$ integrates ${\int }_c^x(x-t{)}^{l-1}{D}^{l}f(t)dt$ by parts with antiderivative $-(x-t{)}^l\mathrm{/}l$, producing the degree-$l$ endpoint term and the displayed remainder. For finite $q$, Hölder [F3] bounds the pointwise remainder by $\mathrm{\mid }J{\mathrm{\mid }}^{l+1\mathrm{/}{q}^{\mathrm{\prime }}}\mathrm{/}l!\mathrm{\parallel }{D}^{l+1}f{\mathrm{\parallel }}_{L^q(J)}$, where $1\mathrm{/}{q}^{\mathrm{\prime }}=1-1\mathrm{/}q$ and $1\mathrm{/}{q}^{\mathrm{\prime }}=0$ for $q=1$; multiplying by $\mathrm{\mid }J{\mathrm{\mid }}^{1\mathrm{/}q}$ gives $\mathrm{\parallel }f-T_{c,l}f{\mathrm{\parallel }}_{L^q(J)}\le \mathrm{\mid }J{\mathrm{\mid }}^{l+1}\mathrm{\parallel }{D}^{l+1}f{\mathrm{\parallel }}_{L^q(J)}\mathrm{/}l!$. For $q=\mathrm{\infty }$, integrating the kernel in the remainder gives the same bound.

Choose $c$ as the left endpoint of $J_m$ and write $T=T_{c,l}f$. Since $Q$ reproduces ${\mathcal{P}}_l$, $QT=T$. Because $I_m\subseteq J_m$, the triangle inequality and local stability give $\mathrm{\parallel }f-Qf{\mathrm{\parallel }}_{L^q(I_m)}\le \mathrm{\parallel }f-T{\mathrm{\parallel }}_{L^q(I_m)}+\mathrm{\parallel }Q(f-T){\mathrm{\parallel }}_{L^q(I_m)}\le (1+C_Q)\mathrm{\parallel }f-T{\mathrm{\parallel }}_{L^q(J_m)}\mathrm{.}$ The definition gives $\mathrm{\mid }{J}_m\mathrm{\mid }\le M{h}_m$; applying step 1.1 proves the stated local estimate.

Raise the local estimates to the $q$th power and sum over the disjoint mesh cells. Each point belongs to at most $M$ neighborhoods, so ${\sum }_m\mathrm{\parallel }{D}^{l+1}f{\mathrm{\parallel }}_{L^q(J_m)}^q\le M\mathrm{\parallel }{D}^{l+1}f{\mathrm{\parallel }}_{L^q([a,b])}^q$. Taking the $q$th root and using $h_m\le h$ gives the stated global bound for finite $q$. For $q=\mathrm{\infty }$, take the maximum of the local bounds; the factor $M^{1\mathrm{/}q}$ is $1$.

For a uniform mesh with interior knots repeated $p+1$ times, $S_{p,\xi }$ is the space of independent degree-$p$ polynomials on the cells by the definition and basis theorem. On a cell $I$, use the real $L^2(I)$ pairing $⟨u,v{⟩}_I={\int }_{I}uv$: it is finite by Hölder [F3], bilinear and symmetric by linearity of the integral, and positive definite since ${\int }_I{u}^2=0$ implies each set $\{\mathrm{\mid }u\mathrm{\mid }\ge 1\mathrm{/}m\}$ has measure zero, hence $u=0$ almost everywhere. Put ${\varphi }_j(x)=x^j$, $0\le j\le p$, and $G_{ij}=⟨{\varphi }_i,{\varphi }_j{⟩}_I$. For any nonzero coefficient vector $c$, $c^{T}Gc={\int }_I({\sum }_j{c}_j{x}^j{)}^2>0$, since a nonzero polynomial has only finitely many roots; hence $G$ is invertible. For $f\in L^2(I)$, put $b_i=⟨f,{\varphi }_i{⟩}_I$ and $c=G^{-1}b$, and define $Q_{h}f={\sum }_{j=0}^p{c}_j{\varphi }_j$ on $I$. The defining equations give $⟨f-Q_{h}f,{\varphi }_i{⟩}_I=0$ for every $i$. Thus $Q_h$ is linear, fixes ${\mathcal{P}}_p$, and has residual orthogonal to its range; Pythagoras [F4] gives $\mathrm{\parallel }{Q}_{h}f{\mathrm{\parallel }}_{L^2(I)}\le \mathrm{\parallel }f{\mathrm{\parallel }}_{L^2(I)}$. Assign knot values from the cell on their right and the value at $b$ by the left limit. The cellwise polynomials then form a member of $S_{p,\xi }$. As $J$ varies, these operators form a mesh-uniform local quasi-interpolant family with one-cell neighborhoods, $M=1$, and $C_Q=1$. Applying steps 1.1–3.1 with $l=s-1$ gives $\mathrm{\parallel }f-Q_{h}f{\mathrm{\parallel }}_{L^2}\le 2h^s\mathrm{\parallel }{D}^{s}f{\mathrm{\parallel }}_{L^2}\mathrm{/}(s-1)!$ for $1\le s\le p+1$.

Write $\mathbf{X}=(X_1,\dots ,X_n)$ and ${ϵ}_i=Y_i-g_0(X_i)$. For fixed $\mathbf{x}$, set ${\kappa }_1=\kappa (x_1,\cdot )$ and, for $1\le m<n$, apply [F10] to ${\kappa }_m$ and $\kappa (x_{m+1},\cdot )$ to obtain ${\kappa }_{m+1}$; both factors are probability measures, so the rectangle formula gives total mass one at each stage. Induction gives the finite product probability measure ${\kappa }_n(\mathbf{x},\cdot )$ with rectangle values ${\kappa }_n(\mathbf{x},{\prod }_i{B}_i)={\prod }_i\kappa (x_i,B_i)$. The response rectangles form a pi-system because intersections of rectangles are rectangles, and [F5] says they generate the response product sigma-algebra. On response rectangles the evaluation is Borel in $\mathbf{x}$ by [F4] and [F10]. Because ${\kappa }_n(\mathbf{x},\cdot )$ is a probability measure, the class of sets with Borel evaluation contains the whole space, is closed under complements by subtraction from $1$, and is closed under disjoint countable unions by limits of partial sums; [F11] therefore gives measurability for every response Borel set. For rectangles $A={\prod }_i{A}_i$ and $B={\prod }_i{B}_i$, iid sampling gives $P(\mathbf{X}\in A,\mathbf{Y}\in B)={\prod }_i{\int }_{A_i}\kappa (x,B_i)P_X(dx)$, and repeated Tonelli [F13] gives ${\int }_A{\kappa }_n(\mathbf{x},B)P_X^{\otimes n}(d\mathbf{x})={\prod }_i{\int }_{A_i}\kappa (x,B_i)P_X(dx)\mathrm{.}$ For each fixed response rectangle $B$, the left side of the target identity is a finite measure in $A$; the right side is also a measure by [F12], applied to the nonnegative measurable function $\mathbf{x}\mapsto {\kappa }_n(\mathbf{x},B)$. Design rectangles form a pi-system because intersections are rectangles and generate the design product sigma-algebra by [F5], so [F11] extends the equality to every design Borel $A$. For each such $A$, both sides are finite measures in $B$: countable additivity on the right follows from countable additivity of ${\kappa }_n(\mathbf{x},\cdot )$ and monotone convergence [F14], and their common total mass is $P_X^{\otimes n}(A)$ because the joint design marginal is $P_X^{\otimes n}$ and ${\kappa }_n$ is a probability kernel. Thus the response sets $B$ for which the identity holds for every $A$ form a Dynkin system (complements use the common total mass); they contain the response rectangles, so [F11] gives equality for every response Borel set. Hence ${\kappa }_n$ is a conditional law of $\mathbf{Y}$ given $\mathbf{X}$. Under this product law the residuals are conditionally independent, have conditional means zero by [A2], and conditional second moments at most $\mathrm{\Delta }$. Hence $E[{ϵ}_i{ϵ}_j\mid \mathbf{X}]=0$ for $i\mathrm{\ne }j$ and $E[{ϵ}_i^2\mid \mathbf{X}]\le \mathrm{\Delta }$.