APPROXIMATING MINIMUM NORM SOLUTIONS OF RANK-DEFICIENT LEAST-SQUARES PROBLEMS

In this paper we consider the solution of linear least squares problem s min(x) parallel to Ax -b parallel to(2)(2) where the matrix A is an element of R-mXn is rank deficient. Put p = min(m, n),let sigma(i),i = 1, 2,..., p, denote the singular values of A, and let ui and vi denot e the corresponding left and right singular vectors. Then the minimum norm solution of the least squares problem has the form x = Sigma(i=1 )(r) (u(i)(T)b/sigma(i))nu(i), where r less than or equal to p is the rank of A. The Rirey-Golub iteration, x(k+1) = arg min(x){parallel to Ax -b parallel to(2)(2) + lambda parallel to x-x(k) parallel to(2)(2) converges to the minimum norm solution if xo is chosen equal to zero. The iteration is implemented so that it takes advantage of a bidiagona l decomposition of A. Thus modified, the iteration requires only O (p) flops (floating point operations). A further gain of using the bidiag onalization of A is that both the singular values ai and the scalar pr oducts u(i)(T)b can be computed at marginal extra cost. Moreover, we d etermine the regularization parameter, lambda, and the number of itera tions, k, in a way that minimizes the difference x -x(k) with respect to a certain norm. Explicit rules are derived for calculating these p arameters. One advantage of our approach is that the numerical rank ca n be easily determined by using the singular values. Furthermore, by t he iterative procedure, x is approximated without computing the singu lar vectors of A. This gives a fast and reliable method for approximat ing minimum norm solutions of well-conditioned rank-deficient least sq uares problems. Numerical experiments illustrate the viability of our ideas, and demonstrate that the new method gives more accurate approxi mations than an approach based on a QR decomposition with column pivot ing. (C) 1998 John Wiley & Sons, Ltd.