# B-splines least squares with equality constraints

Can someone recommend the best way to solve a least squares fitting problem with B-splines, with additional equality constraints? I want to solve: $$\min_x || b - A x ||^2, \textrm{subject to: } C x = d$$ where $A$ is $m \times n$ and $C$ is $p \times n$. Specifically I want to fit B-splines and force the first derivative of the resulting spline to take prescribed values at a certain number of points.

For the unconstrained problem, the standard approach seems to be to solve the normal equations $$A^T A x = A^T b$$ because for a basis of B-splines of order $k$, the normal equations matrix $A^T A$ is symmetric and banded, with lower bandwidth $k-1$. So a banded Cholesky decomposition can be applied to efficiently solve this system.

However I can't find much literature on dealing with constraints and B-spline fitting. For linear equality constrained systems, LAPACK uses the Generalized RQ decomposition, which does not require forming the normal equations matrix. I could of course do this as well, but the Generalized RQ algorithm won't then take advantage of the sparse structure of the matrix $A$. It might be possible to adapt the RQ algorithm to deal with the sparsity of $A$, but there don't appear to be any existing libraries which do this.

Just wondering if anyone has experience with this and/or recommendations?

• How large can be $m,n,p$? If they are relatively small (say <100), dense linear algebra will be probably significantly faster than the sparse one. – Anton Menshov Sep 8 '18 at 19:58
• Yes they are relatively small. Since I was planning to implement everything myself, I wanted to do it the right way in case I need to solve larger systems later. – vibe Sep 8 '18 at 20:44