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. The two versions differ because one version decomposes two (or more) matrices (much like higher order PCA) and the other version uses a set of constraints imposed on the left and right singular vectors.

Higher order version[]

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 ^[1] in 1976 and later developed by Paige and Saunders,^[2] which is the version described here. In contrast to the SVD, the GSVD decomposes simultaneously a pair of matrices with the same number of columns. The SVD and the GSVD, as well as some other possible generalizations of the SVD,^[3][4][5] are extensively used in the study of the conditioning and regularization of linear systems with respect to quadratic semi-norms. In the following, let ${\displaystyle \mathbb {F} =\mathbb {R} }$, or ${\displaystyle \mathbb {F} =\mathbb {C} }$.

Definition[]

The generalized singular value decomposition of matrices ${\displaystyle A_{1}\in \mathbb {F} ^{m_{1}\times n}}$ and ${\displaystyle A_{2}\in \mathbb {F} ^{m_{2}\times n}}$ is

where

• ${\displaystyle U_{1}\in \mathbb {F} ^{m_{1}\times m_{1}}}$ is unitary,
• ${\displaystyle U_{2}\in \mathbb {F} ^{m_{2}\times m_{2}}}$ is unitary,
• ${\displaystyle Q\in \mathbb {F} ^{n\times n}}$ is unitary,
• ${\displaystyle W\in \mathbb {F} ^{k\times k}}$is unitary,
• ${\displaystyle D\in \mathbb {R} ^{k\times k}}$ is real diagonal with positive diagonal, and contains the non-zero singular values of ${\displaystyle C={\begin{bmatrix}A_{1}\\A_{2}\end{bmatrix}}}$ in decreasing order,
• ${\displaystyle 0_{D}=0\in \mathbb {R} ^{k\times (n-k)}}$,
• ${\displaystyle \Sigma _{1}=\lceil I_{A},S_{1},0_{A}\rfloor \in \mathbb {R} ^{m_{1}\times k}}$ is real non-negative block-diagonal, where ${\displaystyle S_{1}=\lceil \alpha _{r+1},\dots ,\alpha _{r+s}\rfloor }$ with ${\displaystyle 1>\alpha _{r+1}\geq \cdots \geq \alpha _{r+s}>0}$, ${\displaystyle I_{A}=I_{r}}$, and ${\displaystyle 0_{A}=0\in \mathbb {R} ^{(m_{1}-r-s)\times (k-r-s)}}$,
• ${\displaystyle \Sigma _{2}=\lceil 0_{B},S_{2},I_{B}\rfloor \in \mathbb {R} ^{m_{2}\times k}}$ is real non-negative block-diagonal, where ${\displaystyle S_{2}=\lceil \beta _{r+1},\dots ,\beta _{r+s}\rfloor }$ with ${\displaystyle 0<\beta _{r+1}\leq \cdots \leq \beta _{r+s}<1}$, ${\displaystyle I_{B}=I_{k-r-s}}$, and ${\displaystyle 0_{B}=0\in \mathbb {R} ^{(m_{2}-k+r)\times r}}$,
• ${\displaystyle \Sigma _{1}^{*}\Sigma _{1}=\lceil \alpha _{1}^{2},\dots ,\alpha _{k}^{2}\rfloor }$,
• ${\displaystyle \Sigma _{2}^{*}\Sigma _{2}=\lceil \beta _{1}^{2},\dots ,\beta _{k}^{2}\rfloor }$,
• ${\displaystyle \Sigma _{1}^{*}\Sigma _{1}+\Sigma _{2}^{*}\Sigma _{2}=I_{k}}$,
• ${\displaystyle k={\textrm {rank}}(C)}$.

We denote ${\displaystyle \alpha _{1}=\cdots =\alpha _{r}=1}$, ${\displaystyle \alpha _{r+s+1}=\cdots =\alpha _{k}=0}$, ${\displaystyle \beta _{1}=\cdots =\beta _{r}=0}$, and ${\displaystyle \beta _{r+s+1}=\cdots =\beta _{k}=1}$. While ${\displaystyle \Sigma _{1}}$ is diagonal, ${\displaystyle \Sigma _{2}}$ is not always diagonal, because of the leading rectangular zero matrix; instead ${\displaystyle \Sigma _{2}}$ 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 ${\displaystyle Q^{*}}$ from the left by ${\displaystyle EE^{*}=I}$ where ${\displaystyle E\in \mathbb {F} ^{n\times n}}$ is an arbitrary unitary matrix. We denote

• ${\displaystyle X=([W^{*}D,0_{D}]Q^{*})^{*}}$
• ${\displaystyle X^{*}=[0,R]{\hat {Q}}^{*}}$, where ${\displaystyle R\in \mathbb {F} ^{k\times k}}$ is upper-triangular and invertible, and ${\displaystyle {\hat {Q}}\in \mathbb {F} ^{n\times n}}$ is unitary. Such matrices exist by RQ-decomposition.
• ${\displaystyle Y=W^{*}D}$. Then ${\displaystyle Y}$ is invertible.

Here are some variations of the GSVD:

• MATLAB (gsvd):
  $${\displaystyle {\begin{aligned}A_{1}&=U_{1}\Sigma _{1}X^{*},\\A_{2}&=U_{2}\Sigma _{2}X^{*}.\end{aligned}}}$$

  
• LAPACK (LA_GGSVD):
  $${\displaystyle {\begin{aligned}A_{1}&=U_{1}\Sigma _{1}[0,R]{\hat {Q}}^{*},\\A_{2}&=U_{2}\Sigma _{2}[0,R]{\hat {Q}}^{*}.\end{aligned}}}$$

  
• Simplified:
  $${\displaystyle {\begin{aligned}A_{1}&=U_{1}\Sigma _{1}[Y,0_{D}]Q^{*},\\A_{2}&=U_{2}\Sigma _{2}[Y,0_{D}]Q^{*}.\end{aligned}}}$$

  

Generalized singular values[]

A generalized singular value of ${\displaystyle A_{1}}$ and ${\displaystyle A_{2}}$ is a pair ${\displaystyle (a,b)\in \mathbb {R} ^{2}}$ such that

We have

• ${\displaystyle A_{i}A_{j}^{*}=U_{i}\Sigma _{i}YY^{*}\Sigma _{j}^{*}U_{j}^{*}}$
• ${\displaystyle 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}YQ_{1}^{*}}$

By these properties we can show that the generalized singular values are exactly the pairs ${\displaystyle (\alpha _{i},\beta _{i})}$. We have

Therefore

${\displaystyle {\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}}}$

This expression is zero exactly when ${\displaystyle a=\alpha _{i}}$ and ${\displaystyle b=\beta _{i}}$ for some ${\displaystyle i}$.

In,^[2] the generalized singular values are claimed to be those which solve ${\displaystyle \det(b^{2}A_{1}^{*}A_{1}-a^{2}A_{2}^{*}A_{2})=0}$. However, this claim only holds when ${\displaystyle k=n}$, since otherwise the determinant is zero for every pair ${\displaystyle (a,b)\in \mathbb {R} ^{2}}$; this can be seen by substituting ${\displaystyle \delta =0}$ above.

Generalized inverse[]

Define ${\displaystyle E^{+}=E^{-1}}$ for any invertible matrix ${\displaystyle E\in \mathbb {F} ^{n\times n}}$ , ${\displaystyle 0^{+}=0^{*}}$ for any zero matrix ${\displaystyle 0\in \mathbb {F} ^{m\times n}}$, and ${\displaystyle \left\lceil E_{1},E_{2}\right\rfloor ^{+}=\left\lceil E_{1}^{+},E_{2}^{+}\right\rfloor }$ for any block-diagonal matrix. Then define

It can be shown that ${\displaystyle A_{i}^{+}}$ as defined here is a generalized inverse of ${\displaystyle A_{i}}$; in particular a ${\displaystyle \{1,2,3\}}$-inverse of ${\displaystyle A_{i}}$. Since it does not in general satisfy ${\displaystyle (A_{i}^{+}A_{i})^{*}=A_{i}^{+}A_{i}}$, this is not the Moore–Penrose inverse; otherwise we could derive ${\displaystyle (AB)^{+}=B^{+}A^{+}}$ for any choice of matrices, which only holds for certain class of matrices.

Suppose ${\displaystyle Q={\begin{bmatrix}Q_{1}&Q_{2}\end{bmatrix}}}$, where ${\displaystyle Q_{1}\in \mathbb {F} ^{n\times k}}$ and ${\displaystyle Q_{2}\in \mathbb {F} ^{n\times (n-k)}}$. This generalized inverse has the following properties:

• ${\displaystyle \Sigma _{1}^{+}=\lceil I_{A},S_{1}^{-1},0_{A}^{T}\rfloor }$
• ${\displaystyle \Sigma _{2}^{+}=\lceil 0_{B}^{T},S_{2}^{-1},I_{B}\rfloor }$
• ${\displaystyle \Sigma _{1}\Sigma _{1}^{+}=\lceil I,I,0\rfloor }$
• ${\displaystyle \Sigma _{2}\Sigma _{2}^{+}=\lceil 0,I,I\rfloor }$
• ${\displaystyle \Sigma _{1}\Sigma _{2}^{+}=\lceil 0,S_{1}S_{2}^{-1},0\rfloor }$
• ${\displaystyle \Sigma _{1}^{+}\Sigma _{2}=\lceil 0,S_{1}^{-1}S_{2},0\rfloor }$
• ${\displaystyle A_{i}A_{j}^{+}=U_{i}\Sigma _{i}\Sigma _{j}^{+}U_{j}^{*}}$
• ${\displaystyle A_{i}^{+}A_{j}=Q{\begin{bmatrix}Y^{-1}\Sigma _{i}^{+}\Sigma _{j}Y&0\\0&0\end{bmatrix}}Q^{*}=Q_{1}Y^{-1}\Sigma _{i}^{+}\Sigma _{j}YQ_{1}^{*}}$

Quotient SVD[]

A generalized singular ratio of ${\displaystyle A_{1}}$ and ${\displaystyle A_{2}}$ is ${\displaystyle \sigma _{i}=\alpha _{i}\beta _{i}^{+}}$. By the above properties, ${\displaystyle A_{1}A_{2}^{+}=U_{1}\Sigma _{1}\Sigma _{2}^{+}U_{2}^{*}}$. Note that ${\displaystyle \Sigma _{1}\Sigma _{2}^{+}=\lceil 0,S_{1}S_{2}^{-1},0\rfloor }$ is diagonal, and that, ignoring the leading zeros, contains the singular ratios in decreasing order. If ${\displaystyle A_{2}}$ is invertible, then ${\displaystyle \Sigma _{1}\Sigma _{2}^{+}}$ has no leading zeros, and the generalized singular ratios are the singular values, and ${\displaystyle U_{1}}$ and ${\displaystyle U_{2}}$ are the matrices of singular vectors, of the matrix ${\displaystyle A_{1}A_{2}^{+}=A_{1}A_{2}^{-1}}$. In fact, computing the SVD of ${\displaystyle A_{1}A_{2}^{-1}}$ is one of the motivations for the GSVD, as "forming ${\displaystyle AB^{-1}}$ and finding its SVD can lead to unnecessary and large numerical errors when ${\displaystyle B}$ is ill-conditioned for solution of equations".^[2] Hence the sometimes used name "quotient SVD", although this is not the only reason for using GSVD. If ${\displaystyle A_{2}}$ is not invertible, then ${\displaystyle U_{1}\Sigma _{1}\Sigma _{2}^{+}U_{2}^{*}}$is still the SVD of ${\displaystyle A_{1}A_{2}^{+}}$ if we relax the requirement of having the singular values in decreasing order. Alternatively, a decreasing order SVD can be found by moving the leading zeros to the back: ${\displaystyle U_{1}\Sigma _{1}\Sigma _{2}^{+}U_{2}^{*}=(U_{1}P_{1})P_{1}^{*}\Sigma _{1}\Sigma _{2}^{+}P_{2}(P_{2}^{*}U_{2}^{*})}$, where ${\displaystyle P_{1}}$ and ${\displaystyle P_{2}}$ are appropriate permutation matrices. Since rank equals the number of non-zero singular values, ${\displaystyle \mathrm {rank} (A_{1}A_{2}^{+})=s}$.

Construction[]

Let

• ${\displaystyle C=P\lceil D,0\rfloor Q^{*}}$ be the SVD of ${\displaystyle C={\begin{bmatrix}A_{1}\\A_{2}\end{bmatrix}}}$, where ${\displaystyle P\in \mathbb {F} ^{(m_{1}+m_{2})\times (m_{1}\times m_{2})}}$ is unitary, and ${\displaystyle Q}$ and ${\displaystyle D}$ are as described,
• ${\displaystyle P=[P_{1},P_{2}]}$, where ${\displaystyle P_{1}\in \mathbb {F} ^{(m_{1}+m_{2})\times k}}$ and ${\displaystyle P_{2}\in \mathbb {F} ^{(m_{1}+m_{2})\times (n-k)}}$,
• ${\displaystyle P_{1}={\begin{bmatrix}P_{11}\\P_{21}\end{bmatrix}}}$, where ${\displaystyle P_{11}\in \mathbb {F} ^{m_{1}\times k}}$ and ${\displaystyle P_{21}\in \mathbb {F} ^{m_{2}\times k}}$,
• ${\displaystyle P_{11}=U_{1}\Sigma _{1}W^{*}}$ by the SVD of ${\displaystyle P_{11}}$, where ${\displaystyle U_{1}}$, ${\displaystyle \Sigma _{1}}$ and ${\displaystyle W}$ are as described,
• ${\displaystyle P_{21}W=U_{2}\Sigma _{2}}$ by a decomposition similar to a QR-decomposition, where ${\displaystyle U_{2}}$ and ${\displaystyle \Sigma _{2}}$ are as described.

Then

We also haveThereforeSince ${\displaystyle P_{1}}$ has orthonormal columns, ${\displaystyle ||P_{1}||_{2}\leq 1}$. ThereforeWe also have for each ${\displaystyle x\in \mathbb {R} ^{k}}$ such that ${\displaystyle ||x||_{2}=1}$ thatTherefore ${\displaystyle ||P_{21}||_{2}\leq 1}$, and

Weighted version[]

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.^[6][7][8] 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

${\displaystyle M=U\Sigma V^{*}\,}$

where

${\displaystyle U^{*}W_{u}U=V^{*}W_{v}V=I.}$

Where I is the identity matrix and where ${\displaystyle U}$ and ${\displaystyle V}$ are orthonormal given their constraints (${\displaystyle W_{u}}$ and ${\displaystyle W_{v}}$). Additionally, ${\displaystyle W_{u}}$ and ${\displaystyle W_{v}}$ 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)^[9]

Applications[]

The GSVD, formulated as a comparative spectral decomposition,^[10] has been successfully applied to signal processing and data science, e.g., in genomic signal processing.^[11][12][13]

These applications inspired several additional comparative spectral decompositions, i.e., the higher-order GSVD (HO GSVD)^[14] and the tensor GSVD.^{[15] [16]}

References[]

Further reading[]