Generalized Singular Value Decomposition (GSVD)

The generalized (or quotient) singular value decomposition of an $m \times n$ matrix $A$ and a $p \times 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 \times m$, V is $p \times p$, $Q$ is $n\times 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 \times r$, upper triangular and nonsingular. $[0,R]$ is $r \times n$ (in other words, the $0$ is an $r \times (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 \times r$, $\Sigma_2$ is $p \times 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^2 + S^2 = 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^2 + S^2 = 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.

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

Type of	Function and storage scheme	Real/complex	Complex
problem			Hermitian
GSEP	simple driver	LA_SYGV (real only)	LA_HEGV
	divide and conquer driver	LA_SYGVD (real only)	LA_HEGVD
	expert driver	LA_SYGVX (real only)	LA_HEGVX
	simple driver (packed storage)	LA_SPGV (real only)	LA_HPGV
	divide and conquer driver	LA_SPGVD (real only)	LA_HPGVD
	expert driver	LA_SPGVX (real only)	LA_HPGVX
	simple driver (band matrices)	LA_SBGV (real only)	LA_HBGV
	divide and conquer driver	LA_SBGVD (real only)	LA_HBGVD
	expert driver	LA_SBGVX (real only)	LA_HBGVX
GNEP	simple driver for Schur factorization	LA_GGES
	expert driver for Schur factorization	LA_GGESX
	simple driver for eigenvalues/vectors	LA_GGEV
	expert driver for eigenvalues/vectors	LA_GGEVX
GSVD	singular values/vectors	LA_GGSVD

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$ [20]:

$$\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.2.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 LA_GGSVD computes the generalized singular value decomposition of $A$ and $B$ (see Table 2.6). The method is based on the method described in [33,2,3].