surface approximation using least squares

Question

I am studying the following problem. Soppose you have two Bezièr patches with a common curve; suppose that the control points of the two patches are given by some initial guess (they are all known). According to the objective I want to reach, I imposed some constraints on the common curve to achieve the regularity that I want in the joint of the two paches. These contraints are given as a linear underdetermined system, with control points of the patches unknowns (the starting ones were given without any accuracy on the regularity of the joint). This is my problem: the article I follows says: we can determine a solution of the underdetermined linear system with least squares method, finding the solution which is as close as possible to the initial guess. How can I do this? Thank you.

Answer 1

You can start by establishing the linear subspace of solutions that satisfy your linear constraints. Suppose your constraints on the vector $X \in \mathbb{R}^n$ are

$AX = B$

where $A$ is a matrix of rank $m < n$ and $B$ is also a matrix of size $m \times 1$. You can find the homogeneous solution to these equations to be on the form

$X = Q\lambda \quad \text{with} \quad \lambda\in \mathbb{R}^{n - m}$

with $\lambda$ being free variables, so that

$AQ\lambda = B \quad \text{for} \quad \lambda \in \mathbb{R}^{n - m}$.

The particular solution is given by $q = A^T(AA^T)^{-1}B$, so that

$AX = B \quad \text{with} \quad X = Q\lambda + q \quad \forall \lambda \in \mathbb{R}^{n - m}$.

In Matlab, you get $Q$ and $q$ as

Q = null(A);

q = A\B;

Suppose you have a constrained least-squares problem

If you are given matrices $G$ and $H$ and would like to minimize $\left\| GX - H\right\|^2$ subject to $AX = B$, all you need to do is to plug in $X = Q\lambda + q$ and solve w.r.t. $\lambda$:

Minimizing $\left\| G(Q\lambda + q) - H\right\|^2$ w.r.t. $\lambda$ yields $\lambda = (Q^T G^TGQ)^{-1}Q^TG^T(H - Gq)$ and from this you get

$X = Q(Q^T G^TGQ)^{-1}Q^TG^T(H - Gq) + q$