Page 426 - Matrix Analysis & Applied Linear Algebra

422 Chapter 5 Norms, Inner Products, and Orthogonality

Problem: Explain why this means that computing the singular values of A
with any stable algorithm (one that returns the exact singular values β k of a
nearby matrix A + E)isa good way to compute rank (A).
Solution: If rank (A)= r, then p − r of the σ k ’s are exactly zero, so the
perturbation result (5.12.15) guarantees that p−r of the computed β k ’s cannot
be larger than E 2 . So if

β 1 ≥· · · ≥ β ˜r > E 2 ≥ β ˜r+1 ≥· · · ≥ β p ,

r
then it’s reasonable to consider ˜ to be the numerical rank of A. For most
algorithms, E 2 is not known exactly, but adequate estimates of E 2 often
can be derived. Considerable effort has gone into the development of stable al-
gorithms for computing singular values, but such algorithms are too involved
to discuss here—consult an advanced book on matrix computations. Gener-
−t
ally speaking, good SVD algorithms have E 2 ≈ 5 × 10 A 2 when t-digit
floating-point arithmetic is used.

Just as the range-nullspace decomposition was used in Example 5.10.5 to
define the Drazin inverse of a square matrix, a URV factorization or an SVD
can be used to define a generalized inverse for rectangular matrices. For a URV
factorization

−1
C 0 T C 0 T
A m×n = U V , we define A † n×m = V U
0 0 0 0
m×n n×m
to be the Moore–Penrose inverse (or the pseudoinverse)of A. (Replace
( ) T by ( ) ∗ when A ∈C m×n . ) Although the URV factors are not uniquely
defined by A, it can be proven that A is unique by arguing that A is the
†
†
unique solution to the four Penrose equations
AA A = A, A AA = A ,
†
†
†
†
T T
†
†
AA † = AA , A A = A A,
†
so A † is the same matrix defined in Exercise 4.5.20. Since it doesn’t matter
which URV factorization is used, we can use the SVD (5.12.2), in which case
C = D = diag (σ 1 ,...,σ r ). Some “inverselike” properties that relate A † to
solutions and least squares solutions for linear systems are given in the following
summary. Other useful properties appear in the exercises.