Introduction to Computational Linear Algebra

Orthogonal Factorizations and Linear Least Squares Problems 99

4.7 Householder QR with Column Pivoting

In order to avoid computing the singular-value decomposition which is

quite expensive for solving rank deficient linear least squares problems, the

factorization (4.17) is often replaced by a similar factorization where S

r

is not

assumed to be diagonal. Such factorizations are called complete orthogonal

factorizations. One way to compute such factorization relies on the procedure

introduced by Businger and Golub [16]. It computes the QR factorization

by Householder reductions with column pivoting. Factorization (4.35) is now

replaced by

H

(q)

···H

(2)

H

(1) ...