next up previous contents index
Next: Generalized Linear Least Squares Up: Driver Routines Previous: Linear Equations   Contents   Index


Linear Least Squares (LLS) Problems

The linear least squares problem is:

\begin{displaymath} \mathop{\mbox{minimize }}_{x} \Vert b - A x {\Vert}_2 \end{displaymath} (2.1)

where $A$ is an $m \times n$ matrix, $b$ is a given $m$ element vector and $x$ is the $n$ element solution vector.
In the most usual case $m \ge n$ and $\mbox{rank}(A) = n$, and in this case the solution to problem (2.1) is unique, and the problem is also referred to as finding a least squares solution to an overdetermined system of linear equations.
When $m < n$ and $\mbox{rank}(A) = m$, there are an infinite number of solutions $x$ which exactly satisfy $b-Ax=0$. In this case it is often useful to find the unique solution $x$ which minimizes $\Vert x\Vert _2$, and the problem is referred to as finding a minimum norm solution to an underdetermined system of linear equations.
The driver routine LA_GELS solves problem (2.1) on the assumption that $\mbox{rank}(A) = \min(m,n)$ -- in other words, $A$ has full rank -- finding a least squares solution of an overdetermined system when $m > n$, and a minimum norm solution of an underdetermined system when $m < n$. LA_GELS uses a $QR$ or $LQ$ factorization of $A$, and also allows $A$ to be replaced by $A^T$ in the statement of the problem (or by $A^H$ if $A$ is complex).
In the general case when we may have $\mbox{rank}(A) < \min(m,n)$ -- in other words, $A$ may be rank-deficient -- we seek the minimum norm least squares solution $x$ which minimizes both $\Vert x\Vert _2$ and $\Vert b - Ax{\Vert}_2$.
The driver routines LA_GELSY, LA_GELSS, and LA_GELSD, solve this general formulation of problem (2.1), allowing for the possibility that $A$ is rank-deficient; LA_GELSY uses a complete orthogonal factorization of $A$, while LA_GELSS uses the singular value decomposition of $A$, and LA_GELSD uses the singular value decomposition of $A$ with an algorithm based on divide and conquer.
The subroutine LA_GELSD is significantly faster than its older counterpart LA_GELSS, especially for large problems, but may require somewhat more workspace depending on the matrix dimensions.
The LLS driver routines are listed in Table 2.3.
All four routines allow several right hand side vectors $b$ and corresponding solutions $x$ to be handled in a single call, storing these vectors as columns of matrices $B$ and $X$, respectively. Note however that problem (2.1) is solved for each right hand side vector independently; this is not the same as finding a matrix $X$ which minimizes $\Vert B - A X \Vert _2$.

Table 2.3: Driver routines for linear least squares problems
Operation real/complex
solve LLS using $QR$ or $LQ$ factorization LA_GELS
solve LLS using complete orthogonal factorization LA_GELSY
solve LLS using SVD LA_GELSS
solve LLS using divide-and-conquer SVD LA_GELSD

next up previous contents index
Next: Generalized Linear Least Squares Up: Driver Routines Previous: Linear Equations   Contents   Index
Susan Blackford 2001-08-19