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 $\mathbb {F} =\mathbb {R}$ , or $\mathbb {F} =\mathbb {C}$ .

Definition

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

{\begin{aligned}A_{1}&=U_{1}\Sigma _{1}[R,0_{R}]Q^{*},\\A_{2}&=U_{2}\Sigma _{2}[R,0_{R}]Q^{*},\end{aligned}}

where

$U_{1}\in \mathbb {F} ^{m_{1}\times m_{1}}$ is unitary,
$U_{2}\in \mathbb {F} ^{m_{2}\times m_{2}}$ is unitary,
$Q\in \mathbb {F} ^{n\times n}$ is unitary,
$R\in \mathbb {F} ^{k\times k}$ is upper-triangular and invertible,
$0_{R}=0\in \mathbb {F} ^{k\times (n-k)}$ ,
$\Sigma _{1}=\lceil I_{A},S_{1},0_{A}\rfloor \in \mathbb {R} ^{m_{1}\times k}$ is real non-negative block-diagonal, where $S_{1}=\lceil \alpha _{r+1},\dots ,\alpha _{r+s}\rfloor$ with $1>\alpha _{r+1}\geq \cdots \geq \alpha _{r+s}>0$ , $I_{A}=I_{r}$ , and $0_{A}=0\in \mathbb {R} ^{(m_{1}-r-s)\times (k-r-s)}$ ,
$\Sigma _{2}=\lceil 0_{B},S_{2},I_{B}\rfloor \in \mathbb {R} ^{m_{2}\times k}$ is real non-negative block-diagonal, where $S_{2}=\lceil \beta _{r+1},\dots ,\beta _{r+s}\rfloor$ with $0<\beta _{r+1}\leq \cdots \leq \beta _{r+s}<1$ , $I_{B}=I_{k-r-s}$ , and $0_{B}=0\in \mathbb {R} ^{(m_{2}-k+r)\times r}$ ,
$\Sigma _{1}^{*}\Sigma _{1}=\lceil \alpha _{1}^{2},\dots ,\alpha _{k}^{2}\rfloor$ ,
$\Sigma _{2}^{*}\Sigma _{2}=\lceil \beta _{1}^{2},\dots ,\beta _{k}^{2}\rfloor$ ,
$\Sigma _{1}^{*}\Sigma _{1}+\Sigma _{2}^{*}\Sigma _{2}=I_{k}$ ,
$k={\textrm {rank}}\left({\begin{bmatrix}A_{1}\\A_{2}\end{bmatrix}}\right)$ .

We denote $\alpha _{1}=\cdots =\alpha _{r}=1$ , $\alpha _{r+s+1}=\cdots =\alpha _{k}=0$ , $\beta _{1}=\cdots =\beta _{r}=0$ , and $\beta _{r+s+1}=\cdots =\beta _{k}=1$ . While $\Sigma _{1}$ is diagonal, $\Sigma _{2}$ is not always diagonal, because of the leading rectangular zero matrix; instead $\Sigma _{2}$ is "bottom-right-diagonal".

Variations

There are different variations depending on the shape of the $[R,0]$ matrix. Since that matrix can be multiplied with the identity matrix $W^{*}W=I$ from the right, where $W$ is unitary, and $W$ can be combined with $Q$ to produce a new unitary $Q'=WQ$ , different variations include $R$ being lower-triangular (see QR, RQ, LQ, QL decompositions), or being invertible without triangularity, or the matrix might be of the form $[0,R]$ instead.

Properties

Here are some properties of the GSVD. In the following, $+$ denotes the Moore-Penrose inverse, and $Q={\begin{bmatrix}Q_{1}&Q_{2}\end{bmatrix}}$ , where $Q_{1}\in \mathbb {F} ^{n\times k}$ and $Q_{2}\in \mathbb {F} ^{n\times (n-k)}$ .

$[R,0]^{+}={\begin{bmatrix}R^{-1}\\0\end{bmatrix}}$
$\Sigma _{1}^{+}=\lceil I_{A},S_{1}^{-1},0_{A}^{T}\rfloor$
$\Sigma _{2}^{+}=\lceil 0_{B}^{T},S_{2}^{-1},I_{B}\rfloor$
$\Sigma _{i}\Sigma _{j}^{+}=\lceil 0,S_{i}S_{j}^{-1},0\rfloor$
$\Sigma _{i}^{+}\Sigma _{j}=\lceil 0,S_{i}^{-1}S_{j},0\rfloor$
$A_{i}^{*}A_{j}=Q{\begin{bmatrix}R^{*}\Sigma _{i}^{*}\Sigma _{j}R&0\\0&0\end{bmatrix}}Q^{*}=Q_{1}R^{*}\Sigma _{i}^{*}\Sigma _{j}RQ_{1}^{*}$
$A_{i}^{+}A_{j}=Q{\begin{bmatrix}R^{-1}\Sigma _{i}^{+}\Sigma _{j}R&0\\0&0\end{bmatrix}}Q^{*}=Q_{1}R^{-1}\Sigma _{i}^{+}\Sigma _{j}RQ_{1}^{*}$
$A_{i}A_{j}^{*}=U_{i}\Sigma _{i}RR^{*}\Sigma _{j}^{*}U_{j}^{*}$
$A_{i}A_{j}^{+}=U_{i}\Sigma _{i}\Sigma _{j}^{+}U_{j}^{*}$

Generalized singular values

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

{\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})&=0,\\a^{2}+b^{2}&=1,\\a,b&\geq 0.\end{aligned}}

Using the properties above, we can show that the generalized singular values are exactly the pairs $(\alpha _{i},\beta _{i})$ :

{\begin{aligned}&\det(b^{2}A_{1}^{*}A_{1}-a^{2}A_{2}^{*}A_{2}+\delta I_{n})\\&=\det \left(Q{\begin{bmatrix}R^{*}(b^{2}\Sigma _{1}^{*}\Sigma _{1}-a^{2}\Sigma _{2}^{*}\Sigma _{2})R+\delta I_{k}&0\\0&\delta I_{n-k}\end{bmatrix}}Q^{*}\right)\\&=\det(\delta I_{n-k})\det(R)^{2}\det(b^{2}\Sigma _{1}^{*}\Sigma _{1}-a^{2}\Sigma _{2}^{*}\Sigma _{2}+\delta I_{k})\\&=\det(\delta I_{n-k})\det(R)^{2}\prod _{i=1}^{k}(b^{2}\alpha _{i}^{2}-a^{2}\beta _{i}^{2}+\delta ).\end{aligned}}

Therefore

\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})=\det(R)^{2}\prod _{i=1}^{k}(b^{2}\alpha _{i}^{2}-a^{2}\beta _{i}^{2}).

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

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

Generalized singular ratios

A generalized singular ratio of $A_{1}$ and $A_{2}$ is $\sigma _{i}=\alpha _{i}\beta _{i}^{+}$ . By the above properties, $A_{1}A_{2}^{+}=U_{1}\Sigma _{1}\Sigma _{2}^{+}U_{2}^{*}$ . Note that $\Sigma _{1}\Sigma _{2}^{+}$ is diagonal, even if $\Sigma _{2}$ is not, and that the ratios are ordered in decreasing order. Therefore, the generalized singular ratios are the singular values, and $U_{1}$ and $U_{2}$ are the matrices of singular vectors, of the matrix $A_{1}A_{2}^{+}$ . In fact, computing the SVD of $A_{1}A_{2}^{+}$ is one of the motivations for the GSVD, as "forming $AB^{-1}$ and finding its SVD can lead to unnecessary and large numerical errors when $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.

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

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

where

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

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

Van Loan CF (1976). "Generalizing the Singular Value Decomposition". SIAM J. Numer. Anal. 13 (1): 76–83. Bibcode:1976SJNA...13...76V. doi:10.1137/0713009.
Paige CC, Saunders MA (1981). "Towards a Generalized Singular Value Decomposition". SIAM J. Numer. Anal. 18 (3): 398–405. Bibcode:1981SJNA...18..398P. doi:10.1137/0718026.
Hansen PC (1997). Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion. SIAM Monographs on Mathematical Modeling and Computation. ISBN 0-89871-403-6.
de Moor BL, Golub GH (1989). "Generalized Singular Value Decompositions A Proposal for a Standard Nomenclauture" (PDF).
de Moor BL, Zha H (1991). "A tree of generalizations of the ordinary singular value decomposition". Linear Algebra and Its Applications. 147: 469–500. doi:10.1016/0024-3795(91)90243-P.
Jolliffe IT (2002). Principal Component Analysis. Springer Series in Statistics (2nd ed.). NY: Springer. ISBN 978-0-387-95442-4.
Greenacre M (1983). Theory and Applications of Correspondence Analysis. London: Academic Press. ISBN 978-0-12-299050-2.
Abdi H, Williams LJ (2010). "Principal component analysis". Wiley Interdisciplinary Reviews: Computational Statistics. 2 (4): 433–459. doi:10.1002/wics.101.
Abdi H (2007). "Singular Value Decomposition (SVD) and Generalized Singular Value Decomposition (GSVD).". In Salkind NJ (ed.). Encyclopedia of Measurement and Statistics. Thousand Oaks (CA): Sage. pp. 907–912.
Alter O, Brown PO, Botstein D (March 2003). "Generalized singular value decomposition for comparative analysis of genome-scale expression data sets of two different organisms". Proceedings of the National Academy of Sciences of the United States of America. 100 (6): 3351–6. Bibcode:2003PNAS..100.3351A. doi:10.1073/pnas.0530258100. PMC 152296. PMID 12631705.
Lee CH, Alpert BO, Sankaranarayanan P, Alter O (January 2012). "GSVD comparison of patient-matched normal and tumor aCGH profiles reveals global copy-number alterations predicting glioblastoma multiforme survival". PLOS ONE. 7 (1): e30098. Bibcode:2012PLoSO...730098L. doi:10.1371/journal.pone.0030098. PMC 3264559. PMID 22291905.
Aiello KA, Ponnapalli SP, Alter O (September 2018). "Mathematically universal and biologically consistent astrocytoma genotype encodes for transformation and predicts survival phenotype". APL Bioengineering. 2 (3): 031909. doi:10.1063/1.5037882. PMC 6215493. PMID 30397684.
Ponnapalli SP, Bradley MW, Devine K, Bowen J, Coppens SE, Leraas KM, Milash BA, Li F, Luo H, Qiu S, Wu K, Yang H, Wittwer CT, Palmer CA, Jensen RL, Gastier-Foster JM, Hanson HA, Barnholtz-Sloan JS, Alter O (May 2020). "Retrospective Clinical Trial Experimentally Validates Glioblastoma Genome-Wide Pattern of DNA Copy-Number Alterations Predictor of Survival". APL Bioeng. 4 (2): 026106. doi:10.1063/1.5142559. PMC 7229984. PMID 32478280. Press Release.
Ponnapalli SP, Saunders MA, Van Loan CF, Alter O (December 2011). "A higher-order generalized singular value decomposition for comparison of global mRNA expression from multiple organisms". PLOS ONE. 6 (12): e28072. Bibcode:2011PLoSO...628072P. doi:10.1371/journal.pone.0028072. PMC 3245232. PMID 22216090.
Sankaranarayanan P, Schomay TE, Aiello KA, Alter O (April 2015). "Tensor GSVD of patient- and platform-matched tumor and normal DNA copy-number profiles uncovers chromosome arm-wide patterns of tumor-exclusive platform-consistent alterations encoding for cell transformation and predicting ovarian cancer survival". PLOS ONE. 10 (4): e0121396. Bibcode:2015PLoSO..1021396S. doi:10.1371/journal.pone.0121396. PMC 4398562. PMID 25875127.
Bradley MW, Aiello KA, Ponnapalli SP, Hanson HA, Alter O (September 2019). "GSVD- and tensor GSVD-uncovered patterns of DNA copy-number alterations predict adenocarcinomas survival in general and in response to platinum". APL Bioengineering. 3 (3): 036104. doi:10.1063/1.5099268. PMC 6701977. PMID 31463421. Supplementary Material.