Linear Least Squares (LLS) Problems

The linear least squares problem is:

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

where A is an m-by-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 |x|₂, and the problem is referred to as finding a minimum norm solution to an underdetermined system of linear equations.

The driver routine xGELS 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. xGELS 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 |x|₂ and $\Vert b - Ax{\Vert}_2$.

The driver routines xGELSX, xGELSY, xGELSS, and xGELSD, solve this general formulation of problem 2.1, allowing for the possibility that A is rank-deficient; xGELSX and xGELSY use a complete orthogonal factorization of A, while xGELSS uses the singular value decomposition of A, and xGELSD uses the singular value decomposition of A with an algorithm based on divide and conquer.

The subroutine xGELSY is a faster version of xGELSX, but requires more workspace since it calls blocked algorithms to perform the complete orthogonal factorization. xGELSX has been retained for compatibility with Release 2.0 of LAPACK, but we omit references to this routine in the remainder of this users' guide.

The subroutine xGELSD is significantly faster than its older counterpart xGELSS, 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	Single precision		Double precision
	real	complex	real	complex
solve LLS using QR or LQ factorization	SGELS	CGELS	DGELS	ZGELS
solve LLS using complete orthogonal factorization	SGELSY	CGELSY	DGELSY	ZGELSY
solve LLS using SVD	SGELSS	CGELSS	DGELSS	ZGELSS
solve LLS using divide-and-conquer SVD	SGELSD	CGELSD	DGELSD	ZGELSD