Further Details: Error Bounds for the Singular Value Decomposition

 

The usual error analysis of the SVD algorithm  PxGESVD in ScaLAPACK (see subsection 3.2.3)is as follows [71]:

The SVD algorithm is backward stable.     This means that the computed SVD, , is nearly the exact SVD of A+E where , and p(m,n) is a modestly growing function of m and n. This means is the true SVD, so that and are both orthogonal, where , and . Each computed singular value differs from true by at most

(we take p(m,n)=1 in the above code fragment). Thus, large singular values (those near ) are computed to high relative accuracy   and small ones may not be.    

The angular difference between the computed left singular vector and a true satisfies the approximate bound

where is the absolute gap   between and the nearest other singular value (we take p(m,n)=1 in the above code fragment). Thus, if is close to other singular values, its corresponding singular vector may be inaccurate. When n < m, then must be redefined as . The gaps may be easily computed from the array of computed singular values using function    SDISNA. The gaps computed by SDISNA are ensured not to be so small as to cause overflow when used as divisors.     The same bound applies to the computed right singular vector and a true vector .

Let be the space spanned by a collection of computed left singular vectors , where is a subset of the integers from 1 to n. Let be the corresponding true space. Then

where

is the absolute gap between the singular values in and the nearest other singular value. Thus, a cluster  of close singular values which is far away from any other singular value may have a well determined space even if its individual singular vectors are ill-conditioned. The same bound applies to a set of right singular vectors .

There is a small possibility that PxGESVD will fail to achieve the above error bounds on a heterogeneous network of processors   for reasons discussed in section 6.2. On a homogeneous network, PxGESVD is as robust as the corresponding LAPACK routine xGESVD. A future release will attempt to detect heterogeneity and warn the user to use an alternative algorithm.

In the special case of bidiagonal matrices, the singular values and singular vectors may be computed much more accurately. A bidiagonal matrix B has nonzero entries only on the main diagonal and the diagonal immediately above it (or immediately below it). PxGESVD computes the SVD of a general      matrix by first reducing it to bidiagonal form B, and then calling xBDSQR (subsection 3.3.6) to compute the SVD of B. Reduction of a dense matrix to bidiagonal form B can introduce additional errors, so the following bounds for the bidiagonal case do not apply to the dense case. For the error analysis of xBDSQR, see the LAPACK manual.