Least Squares Factorizations
Defining the Problem
The most basic linear algebra problem is to solve the system of equations:
Ax = b
for the case where the matrix A is square and nonsingular. This problem implies that you have the same number of independent equations as unknowns. However, sometimes it happens that you have more equations than unknowns, so that A is taller than it is wide. In this case, there is no longer a unique solution, but you can still find a solution in the least squares sense. Such a solution minimizes the square of the difference between the left side Ax and the right side b so that the residual:
(Ax - b)T(Ax - b)
is made as small as possible.
Other times it happens that there are fewer equations than unknowns. In this case, there are an infinite number of possible solutions to the problem. Often you will want the smallest of these solutions. You may also want enough information to build any of the other possible solutions.
The Linear Algebra Module gives you the ability to solve all these problems, and to solve them several different ways, by providing objects which represent a least squares factorization of a system of equations. A least squares factorization object is an alternate representation of a system of equations designed specifically for solving these problems. Several different implementations are provided, each with an identical interface. You choose the one most suited to your problem.
We begin this chapter by showing how to solve the most basic least squares problem using a least squares factorization object, then describe the implementations available, and finally show how you can dramatically improve the robustness of a nearly singular application by specifying a tolerance factor.
