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?

  • $\begingroup$ 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. $\endgroup$
    – Anton Menshov
    Sep 8 '18 at 19:58
  • $\begingroup$ 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. $\endgroup$
    – vibe
    Sep 8 '18 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.