Generalized singular value decomposition

In linear algebra, the generalized singular value decomposition (GSVD) is the name of two different techniques based on the singular value decomposition (SVD). The two versions differ because one version decomposes two matrices (somewhat like the higher-order or tensor SVD) and the other version uses a set of constraints imposed on the left and right singular vectors of a single-matrix SVD.

First version: two-matrix decomposition

The generalized singular value decomposition (GSVD) is a matrix decomposition on a pair of matrices which generalizes the singular value decomposition. It was introduced by Van Loan are extensively used in the study of the conditioning and regularization of linear systems with respect to quadratic semi-norms. In the following, let <math>\mathbb{F} = \mathbb{R}</math>, or <math>\mathbb{F} = \mathbb{C}</math>.

Definition

The generalized singular value decomposition of matrices <math>A_1 \in \mathbb{F}^{m_1 \times n}</math> and <math>A_2 \in \mathbb{F}^{m_2 \times n}</math> is<math display="block">

\begin{align}

A_1 & = U_1\Sigma_1 [ W^* D, 0_D] Q^*, \\

A_2 & = U_2\Sigma_2 [ W^* D, 0_D] Q^*,

\end{align}

</math>where

<math>U_1 \in \mathbb{F}^{m_1 \times m_1}</math> is unitary,
<math>U_2 \in \mathbb{F}^{m_2 \times m_2}</math> is unitary,
<math>Q \in \mathbb{F}^{n \times n}</math> is unitary,
<math>

W \in \mathbb{F}^{k \times k}

</math>is unitary,

<math>

D \in \mathbb{R}^{k \times k}

</math> is real diagonal with positive diagonal, and contains the non-zero singular values of <math>C = \begin{bmatrix} A_1 \\ A_2 \end{bmatrix}</math> in decreasing order,

<math>0_D = 0 \in \mathbb{R}^{k \times (n - k)} </math>,
<math>\Sigma_1 = \lceil I_A, S_1, 0_A \rfloor \in \mathbb{R}^{m_1 \times k}</math> is real non-negative block-diagonal, where <math>S_1 = \lceil \alpha_{r + 1}, \dots, \alpha_{r + s} \rfloor</math> with <math> 1 > \alpha_{r + 1} \ge \cdots \ge \alpha_{r + s} > 0</math>, <math>I_A = I_r</math>, and <math>0_A = 0 \in \mathbb{R}^{(m_1 - r - s) \times (k - r - s)} </math>,
<math>\Sigma_2 = \lceil 0_B, S_2, I_B \rfloor \in \mathbb{R}^{m_2 \times k}</math> is real non-negative block-diagonal, where <math>S_2 = \lceil \beta_{r + 1}, \dots, \beta_{r + s} \rfloor </math> with <math> 0 < \beta_{r + 1} \le \cdots \le \beta_{r + s} < 1</math>, <math>I_B = I_{k - r - s}</math>, and <math>0_B = 0 \in \mathbb{R}^{(m_2 - k + r) \times r} </math>,
<math>\Sigma_1^* \Sigma_1 = \lceil\alpha_1^2, \dots, \alpha_k^2\rfloor</math>,
<math>\Sigma_2^* \Sigma_2 = \lceil\beta_1^2, \dots, \beta_k^2\rfloor</math>,
<math>\Sigma_1^* \Sigma_1 + \Sigma_2^* \Sigma_2 = I_k</math>,
<math>k = \textrm{rank}(C)</math>.

We denote <math>\alpha_1 = \cdots = \alpha_r = 1</math>, <math>\alpha_{r + s + 1} = \cdots = \alpha_k = 0</math>, <math>\beta_1 = \cdots = \beta_r = 0</math>, and <math>\beta_{r + s + 1} = \cdots = \beta_k = 1</math>. While <math>\Sigma_1</math> is diagonal, <math>\Sigma_2 </math> is not always diagonal, because of the leading rectangular zero matrix; instead <math>\Sigma_2</math> is "bottom-right-diagonal".

Variations

There are many variations of the GSVD. These variations are related to the fact that it is always possible to multiply <math>Q^*</math> from the left by <math>E E^* = I</math> where <math>E \in \mathbb{F}^{n \times n}</math> is an arbitrary unitary matrix. We denote

<math>X = ([W^* D, 0_D] Q^*)^*</math>
<math>

X^* = [0, R] \hat{Q}^*

</math>, where <math>

R \in \mathbb{F}^{k \times k}

</math> is upper-triangular and invertible, and <math>

\hat{Q} \in \mathbb{F}^{n \times n}

</math> is unitary. Such matrices exist by RQ-decomposition.

<math>Y = W^* D</math>. Then <math>

</math> is invertible.

Here are some variations of the GSVD:

MATLAB (gsvd):<math display="block">

\begin{aligned}

A_1 & = U_1 \Sigma_1 X^*, \\

A_2 & = U_2 \Sigma_2 X^*.

\end{aligned}

</math>

LAPACK (ggsvd3):<math display="block">

\begin{aligned}

A_1 & = U_1 \Sigma_1 [0, R] \hat{Q}^*, \\

A_2 & = U_2 \Sigma_2 [0, R] \hat{Q}^*.

\end{aligned}

</math>

Simplified:<math display="block">

\begin{align}

A_1 & = U_1\Sigma_1 [ Y, 0_D] Q^*, \\

A_2 & = U_2\Sigma_2 [ Y, 0_D] Q^*.

\end{align}

</math>

Generalized singular values

The phrase generalized singular value can be used in reference to slightly different things. In this article, a generalized singular value of <math>A_1</math> and <math>A_2</math> is a pair <math>(a, b) \in \mathbb{R}^2</math> such that

\begin{align}

\lim_{\delta \to 0} \det(b^2 A_1^* A_1 - a^2 A_2^* A_2 + \delta I_n) / \det(\delta I_{n - k}) & = 0, \\

a^2 + b^2 & = 1, \\

a, b & \geq 0.

\end{align}

</math>Other sources call such <math>(a, b) \in \mathbb{R}^2</math> generalized singular value pairs and use generalized singular value to refer to the ratio <math>a/b</math>.'

Regardless of the naming convention, we have

<math> A_i A_j^* = U_i \Sigma_i Y Y^* \Sigma_j^* U_j^*</math>
<math> A_i^* A_j = Q \begin{bmatrix} Y^* \Sigma_i^* \Sigma_j Y & 0 \\ 0 & 0 \end{bmatrix} Q^* = Q_1 Y^* \Sigma_i^* \Sigma_j Y Q_1^* </math>

By these properties we can show that the generalized singular values are exactly the pairs <math>(\alpha_i, \beta_i)</math>. We have<math display="block">

\begin{aligned}

& \det(b^2 A_1^* A_1 - a^2 A_2^* A_2 + \delta I_n) \\

= & \det(b^2 A_1^* A_1 - a^2 A_2^* A_2 + \delta Q Q^*) \\

= & \det\left(Q \begin{bmatrix} Y^* (b^2 \Sigma_1^* \Sigma_1 - a^2 \Sigma_2^* \Sigma_2) Y + \delta I_k & 0 \\ 0 & \delta I_{n - k} \end{bmatrix} Q^*\right) \\

= & \det(\delta I_{n - k}) \det(Y^* (b^2 \Sigma_1^* \Sigma_1 - a^2 \Sigma_2^* \Sigma_2) Y + \delta I_k).

\end{aligned}

</math>Therefore

:<math>

\begin{aligned}

{} & \lim_{\delta \to 0} \det(b^2 A_1^* A_1 - a^2 A_2^* A_2 + \delta I_n) / \det(\delta I_{n - k}) \\

= & \lim_{\delta \to 0} \det(Y^* (b^2 \Sigma_1^* \Sigma_1 - a^2 \Sigma_2^* \Sigma_2) Y + \delta I_k) \\

= & \det(Y^* (b^2 \Sigma_1^* \Sigma_1 - a^2 \Sigma_2^* \Sigma_2) Y) \\

= & |\det(Y)|^2 \prod_{i = 1}^k (b^2 \alpha_i^2 - a^2 \beta_i^2).

\end{aligned}

</math>

This expression is zero exactly when <math>a = \alpha_i</math> and <math>b = \beta_i</math> for some <math>i</math>.

In, has been successfully applied to signal processing and data science, e.g., in genomic signal processing.

These applications inspired several additional comparative spectral decompositions, i.e., the higher-order GSVD (HO GSVD)

Second version: weighted single-matrix decomposition

The weighted version of the generalized singular value decomposition (GSVD) is a constrained matrix decomposition with constraints imposed on the left and right singular vectors of the singular value decomposition. This form of the GSVD is an extension of the SVD as such. Given the SVD of an m×n real or complex matrix M

:<math>M = U\Sigma V^* \,</math>

where

:<math>U^* W_u U = V^* W_v V = I.</math>

Where I is the identity matrix and where <math>U</math> and <math>V</math> are orthonormal given their constraints (<math>W_u</math> and <math>W_v</math>). Additionally, <math>W_u</math> and <math>W_v</math> are positive definite matrices (often diagonal matrices of weights). This form of the GSVD is the core of certain techniques, such as generalized principal component analysis and Correspondence analysis.

The weighted form of the GSVD is called as such because, with the correct selection of weights, it generalizes many techniques (such as multidimensional scaling and linear discriminant analysis).

Generalized singular value decomposition

First version: two-matrix decomposition

Definition

Variations

Generalized singular values

Second version: weighted single-matrix decomposition

References

Further reading