# Total least squares minimization

I've seen some lecture notes about the Total Least Squares, which state the following:

Suppose we have a linear system $Y=XB$, which may be inconsistent. Now change this system to $$(Y+\Delta)=(X+\Xi)B$$ such that the new system is consistent and the perturbations $\Delta$ and $\Xi$ are small.

More precisely, we want to solve
$$\min_{\Xi,\Delta,B} \{\kappa \Vert\Xi\Vert^2 + \lambda \Vert\Delta\Vert^2 \bigm| Y+\Delta=(X+\Xi)B\}$$

where $\kappa$ and $\lambda$ determine the weights of each component. Letting $Z=X+\Xi$ we see this is the same as

$$\min_{Z_,B} \kappa \Vert X-Z \Vert^2 + \lambda \Vert Y-ZB\Vert^2 .$$

I don't understand how to show that the second minimization problem is the same as the first. Is there some simple manipulation I'm missing?

• I believe you are missing one right curly bracket (in the first minimization). Feb 8, 2016 at 7:20
• @Hatshepsut there seems to be an extra inequality sign in the first formulation of the problem. Feb 8, 2016 at 7:42
• @Gumeo Thanks, I think it snuck in there with the quote block symbols >. Feb 8, 2016 at 7:46

We start by noticing that $Z = X + \Xi$ (by definition). So minimizing w.r.t. $Z$ is the same as minimizing w.r.t. $\Xi$.
And by the equality constraint we have that $ZB = Y + \Delta$. So we replace these in the second formulation and get: \begin{align} \min_{Z,B} \kappa ||X-Z||^2 + \lambda||Y-ZB||^2 &= \min_{Z,B}\kappa||X-(X+\Xi)||^2 + \lambda||Y-(Y + \Delta)||^2 \quad (\text{And equality constraint})\\ &= \min_{Z,B}\kappa||\Xi||^2 + \lambda||\Delta||^2 \quad (\text{And equality constraint})\\ &= \min_{\Xi,\Delta,B}\kappa||\Xi||^2 + \lambda||\Delta||^2 \quad (\text{And equality constraint}) \end{align} So by assuming the equality constraint we can go from your second formulation to the first.
So the question is now, how can we show that the equality constraint is not violated in the second formulation? It is in fact the second term in the minimization problem. It defines the residual $\Delta$, and you are minimizing the norm of that term. You see, there is no $\Delta$ in the second formulation, so you can just introduce it to create the equality constraint for the first formulation. Thus solving the second problem is equivalent to solving the first one.