Generalized Singular Value Decomposition (GSVD)

The generalized (or quotient) singular value decomposition of an m-by-n matrix A and a p-by-n matrix B is given by the pair of factorizations

$$A = U \Sigma_1 [0,\; R ] Q^T \;\;\; {\rm and} \;\;\; B = V \Sigma_2 [0, \; R ] Q^T \;.$$

The matrices in these factorizations have the following properties:

• U is m-by-m, V is p-by-p, Q is n-by-n, and all three matrices are orthogonal. If A and B are complex, these matrices are unitary instead of orthogonal, and Q^T should be replaced by Q^H in the pair of factorizations.
• R is r-by-r, upper triangular and nonsingular. [0,R] is r-by-n (in other words, the 0 is an r-by-n-r zero matrix). The integer r is the rank of $\left( \begin{array}{c} A \\ B \end{array} \right)$, and satisfies $r \leq n$.
• $\Sigma_1$ is m-by-r, $\Sigma_2$ is p-by-r, both are real, nonnegative and diagonal, and $\Sigma_1^T \Sigma_1 + \Sigma_2^T \Sigma_2 = I$. Write $\Sigma_1^T \Sigma_1 = {\rm diag} ( \alpha_1^2 , \ldots , \alpha_r^2 )$ and $\Sigma_2^T \Sigma_2 = {\rm diag} ( \beta_1^2 , \ldots , \beta_r^2 )$, where $\alpha_i$ and $\beta_i$ lie in the interval from 0 to 1. The ratios $\alpha_1 / \beta_1 , \ldots , \alpha_r / \beta_r$ are called the generalized singular values of the pair A, B. If $\beta_i = 0$, then the generalized singular value $\alpha_i / \beta_i$ is infinite.

$\Sigma_1$ and $\Sigma_2$ have the following detailed structures, depending on whether $m-r \geq 0$ or m-r < 0. In the first case, $m-r \geq 0$, then

$$\Sigma_1 = \bordermatrix{ & k & l \cr \hfill k & I & 0 \cr ... ...rmatrix{ & k & l \cr \hfill l & 0 & S \cr p-l & 0 & 0 } \; .$$

Here l is the rank of B, k=r-l, C and S are diagonal matrices satisfying C² + S² = I, and S is nonsingular. We may also identify $\alpha_1 = \cdots = \alpha_k = 1$, $\alpha_{k+i} = c_{ii}$ for $i=1, \ldots , l$, $\beta_1 = \cdots = \beta_k = 0$, and $\beta_{k+i} = s_{ii}$ for $i=1, \ldots , l$. Thus, the first k generalized singular values $\alpha_1 / \beta_1 , \ldots , \alpha_k / \beta_k$ are infinite, and the remaining l generalized singular values are finite.

In the second case, when m-r < 0,

$$\Sigma_1 = \bordermatrix{ & k & m-k & k+l-m \cr \hfill k & I & 0 & 0 \cr m-k & 0 & C & 0 }$$

and

$$\Sigma_2 = \bordermatrix{ & k & m-k & k+l-m \cr \hfill m-k ... ... & 0 \cr k+l-m & 0 & 0 & I \cr \hfill p-l & 0 & 0 & 0 } \; .$$

Again, l is the rank of B, k=r-l, C and S are diagonal matrices satisfying C² + S² = I, S is nonsingular, and we may identify $\alpha_1 = \cdots = \alpha_k = 1$, $\alpha_{k+i} = c_{ii}$ for $i=1, \ldots , m-k$, $\alpha_{m+1} = \cdots = \alpha_r = 0$, $\beta_1 = \cdots = \beta_k = 0$, $\beta_{k+i} = s_{ii}$ for $i=1, \ldots , m-k$, and $\beta_{m+1} = \cdots = \beta_r = 1$. Thus, the first k generalized singular values $\alpha_1 / \beta_1 , \ldots , \alpha_k / \beta_k$ are infinite, and the remaining l generalized singular values are finite.

Here are some important special cases of the generalized singular value decomposition. First, if B is square and nonsingular, then r=n and the generalized singular value decomposition of A and B is equivalent to the singular value decomposition of AB^-1, where the singular values of AB^-1 are equal to the generalized singular values of the pair A, B:

$$AB^{-1} = (U \Sigma_1 R Q^T)(V \Sigma_2 R Q^T)^{-1} = U ( \Sigma_1 \Sigma_2^{-1} ) V^T \; \; .$$

Second, if the columns of $(A^T \; B^T)^T$ are orthonormal, then r=n, R=I and the generalized singular value decomposition of A and B is equivalent to the CS (Cosine-Sine) decomposition of $(A^T \; B^T)^T$ [55]:

$$\left( \begin{array}{c} A \\ B \end{array} \right) = \left( ... ...array}{c} \Sigma_1 \\ \Sigma_2 \end{array} \right) Q^T \; \; .$$

Third, the generalized eigenvalues and eigenvectors of $A^TA - \lambda B^TB$ can be expressed in terms of the generalized singular value decomposition: Let

$$X = Q \left( \begin{array}{cc} I & 0 \\ 0 & R^{-1} \end{array} \right) \; \; .$$

Then

$$X^T A^T A X = \left( \begin{array}{cc} 0 & 0 \\ 0 & \Sigm... ...{cc} 0 & 0 \\ 0 & \Sigma^T_2 \Sigma_2 \end{array} \right).$$

Therefore, the columns of X are the eigenvectors of $A^TA - \lambda B^TB$, and the ``nontrivial'' eigenvalues are the squares of the generalized singular values (see also section 2.3.5.1). ``Trivial'' eigenvalues are those corresponding to the leading n-r columns of X, which span the common null space of A^T A and B^T B. The ``trivial eigenvalues'' are not well defined^2.1.

A single driver routine xGGSVD computes the generalized singular value decomposition of A and B (see Table 2.6). The method is based on the method described in [83,10,8].

Table 2.6: Driver routines for generalized eigenvalue and singular value problems

Type of	Function and storage scheme	Single precision		Double precision
problem		real	complex	real	complex
GSEP	simple driver	SSYGV	CHEGV	DSYGV	ZHEGV
	divide and conquer driver	SSYGVD	CHEGVD	DSYGVD	ZHEGVD
	expert driver	SSYGVX	CHEGVX	DSYGVX	ZHEGVX
	simple driver (packed storage)	SSPGV	CHPGV	DSPGV	ZHPGV
	divide and conquer driver	SSPGVD	CHPGVD	DSPGVD	ZHPGVD
	expert driver	SSPGVX	CHPGVX	DSPGVX	ZHPGVX
	simple driver (band matrices)	SSBGV	CHBGV	DSBGV	ZHBGV
	divide and conquer driver	SSBGVD	CHBGVD	DSBGV	ZHBGVD
	expert driver	SSBGVX	CHBGVX	DSBGVX	ZHBGVX
GNEP	simple driver for Schur factorization	SGGES	CGGES	DGGES	ZGGES
	expert driver for Schur factorization	SGGESX	CGGESX	DGGESX	ZGGESX
	simple driver for eigenvalues/vectors	SGGEV	CGGEV	DGGEV	ZGGEV
	expert driver for eigenvalues/vectors	SGGEVX	CGGEVX	DGGEVX	ZGGEVX
GSVD	singular values/vectors	SGGSVD	CGGSVD	DGGSVD	ZGGSVD