Triangular Least Squares Problems

Definition

By using an orthogonal matrix, we are able to transform our problem without changing the least squares solution. Now we need a suitable target for simplifying a least squares problem so that it becomes easy to solve.

Let's consider least squares problems having an upper triangular matrix. In the overdetermined case, we have the equation of the form

\[ \begin{bmatrix} \mathbf{R} \\ \mathbf{O} \end{bmatrix} \mathbf{x} \cong \begin{bmatrix} \mathbf{c_{1}} \\ \mathbf{c_{2}} \end{bmatrix}, \]

where \(\mathbf{O}\) is the zero matrix and \(\mathbf{R}\) is an \(n\times n\) upper triangular matrix. The right side is partitioned the same way. The least squares residual is then given by

\[ ||\mathbf{r}||^{2}_{2} = ||\mathbf{c_{1}-Rx}||^{2}_{2} + ||\mathbf{c}_{2}||_{2}^{2}. \]

Because it is independent of \(\mathbf{x}\), we have no control over \(||\mathbf{c}_{2}||_{2}^{2}\), but the first term can go to zero by solving \(\mathbf{x}\) such that it satisfies the triangular system

\[ \mathbf{Rx} = \mathbf{c}_{1}. \]

We have therefore found the solution, and can determine that the residual error \(||\mathbf{r}||_{2}^{2} = ||\mathbf{c}_{2}||_{2}^{2}\).

References

Orthogonal Transformations with Matrices (numerical analysis) Linear Least Squares Problems