Overview

In this chapter we discuss numerical methods that are suited for regularization of problems with a numerically rank-deficient coefficient matrix A, i.e., problems for which there is a well-determined gap between the large and small singular values of A.

Such problems come in two "flavors": those that involve the solution of a (possibly overdetermined) system of linear equations, and those that involve the computation of a rank- k matrix approximation to a given matrix. As we shall see, these two problems are strongly connected although the applications in which the problems arise can be very different.

We start with a discussion of the numerical rank of a matrix, as defined via the singular value decomposition (SVD). Next we describe various solutions to rank-deficient problems, defined in terms of the SVD and generalized SVD (GSVD), and we give some perturbation bounds for these solutions. Finally, we focus on algorithms that use rank-revealing decompositions as computational alternatives to the SVD, and we relate the corresponding solutions to the SVD-based solutions.

While the difference between two vectors is naturally measured as the norm of their differences, it is perhaps not intuitively clear how to compare two subspaces. The subspace angle is a convenient tool for measuring the difference between two subspaces. Given the two subspaces and of the same dimension, spanned by the orthonormal columns of the matrices V ₁ and V ₂, the subspace angle ? between and is defined via the...