Error Bounds for the Singular Value Decomposition

The singular value decomposition (SVD) of a real m-by-n matrix A is defined as follows. Let $r = \min (m,n)$. The SVD of A is $A=U \Sigma V^T$ ( $A=U \Sigma V^H$ in the complex case), where U and V are orthogonal (unitary) matrices and $\Sigma = {\mbox {\rm diag}}( \sigma_1 , \ldots , \sigma_r )$ is diagonal, with $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_{r} \geq 0$. The $\sigma _ i$ are the singular values of A and the leading r columns u_i of U and v_i of V the left and right singular vectors, respectively. The SVD of a general matrix is computed by xGESVD or xGESDD (see subsection 2.3.4).

The approximate error bounds^4.10for the computed singular values $\hat{\sigma}_1 \geq \cdots \geq \hat{\sigma}_{r}$ are

$$\vert \hat{\sigma}_i - \sigma_i \vert \leq {\tt SERRBD} \; \; .$$

The approximate error bounds for the computed singular vectors $\hat{v}_i$ and $\hat{u}_i$, which bound the acute angles between the computed singular vectors and true singular vectors v_i and u_i, are

$$\begin{eqnarray*} \theta ( \hat{v}_i , v_i ) & \leq & {\tt VERRBD}(i) \\ \theta ( \hat{u}_i , u_i ) & \leq & {\tt UERRBD}(i) \; \; . \end{eqnarray*}$$

These bounds can be computing by the following code fragment.

      EPSMCH = SLAMCH( 'E' )
*     Compute singular value decomposition of A
*     The singular values are returned in S
*     The left singular vectors are returned in U
*     The transposed right singular vectors are returned in VT
      CALL  SGESVD( 'S', 'S', M, N, A, LDA, S, U, LDU, VT, LDVT,
     $              WORK, LWORK, INFO )
      IF( INFO.GT.0 ) THEN
         PRINT *,'SGESVD did not converge'
      ELSE IF ( MIN(M,N) .GT. 0 ) THEN
         SERRBD  = EPSMCH * S(1)
*        Compute reciprocal condition numbers for singular vectors
         CALL SDISNA( 'Left', M, N, S, RCONDU, INFO )
         CALL SDISNA( 'Right', M, N, S, RCONDV, INFO )
         DO 10 I = 1, MIN(M,N)
            VERRBD( I ) = EPSMCH*( S(1)/RCONDV( I ) )
            UERRBD( I ) = EPSMCH*( S(1)/RCONDU( I ) )
10       CONTINUE
      END IF

For example^4.11, if ${\tt SLAMCH('E')} = 2^{-24} = 5.961 \cdot 10^{-8}$ and

$$A = \left( \begin{array}{ccc} 4 & 3 & 5 \\ 2 & 5 & 8 \\ 3 & 6 & 10 \\ 4 & 5 & 11 \end{array} \right) \; ,$$

then the singular values, approximate error bounds, and true errors are given below.

i	$\hat{\sigma}_i$	SERRBD	true $\vert \hat{\sigma}_i - \sigma_i \vert$	VERRBD(i)	true $\theta ( \hat{v}_i , v_i )$	UERRBD(i)	true $\theta ( \hat{u}_i , u_i )$
1	21.05	$1.3 \cdot 10^{-6}$	$1.7 \cdot 10^{-6}$	$6.7 \cdot 10^{-8}$	$8.1 \cdot 10^{-8}$	$6.7 \cdot 10^{-8}$	$1.5 \cdot 10^{-7}$
2	2.370	$1.3 \cdot 10^{-6}$	$5.8 \cdot 10^{-7}$	$1.0 \cdot 10^{-6}$	$2.9 \cdot 10^{-7}$	$1.0 \cdot 10^{-6}$	$2.4 \cdot 10^{-7}$
3	1.143	$1.3 \cdot 10^{-6}$	$3.2 \cdot 10^{-7}$	$1.0 \cdot 10^{-6}$	$3.0 \cdot 10^{-7}$	$1.1 \cdot 10^{-6}$	$2.4 \cdot 10^{-7}$