Approximating minimum norm solutions of rank-deficient least squares problems
✍ Scribed by Achiya Dax; Lars Eldén
- Publisher
- John Wiley and Sons
- Year
- 1998
- Tongue
- English
- Weight
- 133 KB
- Volume
- 5
- Category
- Article
- ISSN
- 1070-5325
No coin nor oath required. For personal study only.
✦ Synopsis
In this paper we consider the solution of linear least squares problems min x Ax -b 2 2 where the matrix A ∈ R m×n is rank deficient. Put p = min{m, n}, let σ i , i = 1, 2, . . . , p, denote the singular values of A, and let u i and v i denote the corresponding left and right singular vectors. Then the minimum norm solution of the least squares problem has the form x * = r i=1 (u T i b/σ i )v i , where r ≤ p is the rank of A.
The Riley-Golub iteration,
converges to the minimum norm solution if x 0 is chosen equal to zero. The iteration is implemented so that it takes advantage of a bidiagonal decomposition of A. Thus modified, the iteration requires only O(p) flops (floating point operations). A further gain of using the bidiagonalization of A is that both the singular values σ i and the scalar products u T i b can be computed at marginal extra cost. Moreover, we determine the regularization parameter, λ, and the number of iterations, k, in a way that minimizes the difference x * -x k with respect to a certain norm. Explicit rules are derived for calculating these parameters.
One advantage of our approach is that the numerical rank can be easily determined by using the singular values. Furthermore, by the iterative procedure, x * is approximated without computing the singular vectors of A. This gives a fast and reliable method for approximating minimum norm solutions of well-conditioned rankdeficient least squares problems. Numerical experiments illustrate the viability of our ideas, and demonstrate that the new method gives more accurate approximations than an approach based on a QR decomposition with column pivoting.