Skip to content

B-splines and penalized fitting ​

Bases ​

All splines in furca are cubic (p=3) on [0,1].

Clamped basis with n functions. The knot vector has p+1 zeros, n−p−1 equally spaced interior knots and p+1 ones:

ξ=(0,…,0⏟p+1, 1n−p, …, n−p−1n−p, 1,…,1⏟p+1).

The spline interpolates its first and last coefficients. It is used along the vessel. The interior knots may also be given explicitly (any strictly increasing sequence in (0,1)); the wall uses this for adaptive knots.

Periodic basis with n functions. The knots are ξk=(k−p)/n for k=0,…,n+2p and basis function j is identified with jmodn, so the spline is Cp−1 across θ=0≡2π. It is used around the vessel, with t=θ/2π.

Basis functions and their derivatives are evaluated with Algorithm A2.3 of Piegl and Tiller [2]. Only p+1 functions are non-zero at any parameter value, so evaluating a curve costs O(p2) and a tensor-product surface O(p2) per direction.

Penalized least squares ​

Given observations (ti,yi) with weights wi, and a basis matrix Bij=Bj(ti), the coefficients c minimize

∥W1/2(Bc−y)∥2+λc⊤Pc,

where P is a symmetric positive semi-definite penalty. Following the P-spline approach of Eilers and Marx [3], the number of coefficients is chosen generously and λ controls smoothness. Two penalties are used:

  • Difference penalty P=D⊤D, with D the second-order difference matrix ((Dc)i=ci−2ci+1+ci+2; circulant for periodic bases), for the centerline fits, whose knots are uniform. For uniform cubic B-splines it is a discrete version of ∫(f″)2.
  • Integral penalty P=Ω, Ωij=∫Bi″Bj″, computed exactly by Gauss–Legendre quadrature with p+1 nodes per span, for the wall. It is exact for any knot placement.

Both pull towards straight lines and never towards zero.

Choosing λ ​

λ is chosen by minimizing the generalized cross-validation score [4]

GCV(λ)=NRSS(λ)(N−edf(λ))2,edf(λ)=tr[(G+λP)−1G],

with G=B⊤WB, N=∑iwi (weights are normalized to mean one) and RSS the weighted residual sum of squares. edf is the effective number of degrees of freedom of the fit.

Fast evaluation ​

The search evaluates GCV at many values of λ, so each evaluation must be cheap. furca uses two exact strategies, depending on the structure of the problem.

Small dense systems (curves, with three outputs). furca computes once the Cholesky factor G=LL⊤ and the symmetric eigendecomposition

L−1PL−⊤=Qdiag(μ1,…,μn)Q⊤.

With z=Q⊤L−1B⊤Wy and si=1/(1+λμi):

c(λ)=L−⊤Qdiag(s)z,edf(λ)=∑isi,RSS(λ)=y⊤Wy−∑izi2(2si−si2).

Each λ then costs O(n), after one O(n3) decomposition.

Block-banded systems (the wall). A sample touches four consecutive longitudinal B-splines, so with the coefficients ordered by τ both G and P are made of nτ×nτ blocks of size nθ that vanish more than three blocks away from the diagonal. The decomposition above would cost O(nτ3nθ3). Instead, each λ factors A=G+λP=LL⊤ in banded form and computes

c=A−1B⊤Wy,RSS=y⊤Wy−2c⊤B⊤Wy+c⊤Gc,edf=tr(A−1G)=∑|i−j|≤3⟨(A−1)ij,Gij⟩.

The trace needs only the blocks of A−1 inside the band of G. The selected inverse [15] computes exactly these blocks from the factor, without forming the rest: since L⊤A−1=L−1 is block lower triangular with diagonal blocks Lii−1,

(A−1)ij=Lii−⊤(δijLii−1−∑k=i+1i+3Lki⊤(A−1)kj),i≤j≤i+3,

which fills the band from the last block row upwards. Every evaluation is exact and costs O(nτnθ3), linear in the length of the vessel.

Search. GCV is evaluated on a 65-point grid over log10⁡(λ/λ0)∈[−10,6], with λ0=trG/trP (in parallel), and the best grid point is refined by golden-section search to 10−4 decades.

If a basis function has no data, G is singular. A ridge of 10−10tr(G)/n is added to its diagonal; the affected directions get μi≫1 and are determined by the penalty, which extrapolates smoothly.

furca — parametric models of blood vessels.