Generalized singular value decomposition

Short description: Name of two different techniques based on the 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.

## Contents

* 1 First version: two-matrix decomposition
* 1.1 Definition
* 1.2 Variations
* 1.3 Generalized singular values
* 1.4 Generalized inverse
* 1.5 Quotient SVD
* 1.6 Construction
* 2 Applications
* 3 Second version: weighted single-matrix decomposition
* 4 References
* 5 Further reading

## 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 [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 𝔽=ℝ, or 𝔽=ℂ.

### Definition

The generalized singular value decomposition of matrices A1∈𝔽m1×n and A2∈𝔽m2×n isA1=U1Σ1[W*D,0D]Q*,A2=U2Σ2[W*D,0D]Q*,where

* U1∈𝔽m1×m1 is unitary,
* U2∈𝔽m2×m2 is unitary,
* Q∈𝔽n×n is unitary,
* W∈𝔽k×kis unitary,
* D∈ℝk×k is real diagonal with positive diagonal, and contains the non-zero singular values of C=[A1A2] in decreasing order,
* 0D=0∈ℝk×(n−k),
* Σ1=⌈IA,S1,0A⌋∈ℝm1×k is real non-negative block-diagonal, where S1=⌈αr+1,…,αr+s⌋ with 1>αr+1≥⋯≥αr+s>0, IA=Ir, and 0A=0∈ℝ(m1−r−s)×(k−r−s),
* Σ2=⌈0B,S2,IB⌋∈ℝm2×k is real non-negative block-diagonal, where S2=⌈βr+1,…,βr+s⌋ with 0<βr+1≤⋯≤βr+s<1, IB=Ik−r−s, and 0B=0∈ℝ(m2−k+r)×r,
* Σ1*Σ1=⌈α12,…,αk2⌋,
* Σ2*Σ2=⌈β12,…,βk2⌋,
* Σ1*Σ1+Σ2*Σ2=Ik,
* k=rank(C).

We denote α1=⋯=αr=1, αr+s+1=⋯=αk=0, β1=⋯=βr=0, and βr+s+1=⋯=βk=1. While Σ1 is diagonal, Σ2 is not always diagonal, because of the leading rectangular zero matrix; instead Σ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 Q* from the left by EE*=I where E∈𝔽n×n is an arbitrary unitary matrix. We denote

* X=([W*D,0D]Q*)*
* X*=[0,R]Q^*, where R∈𝔽k×k is upper-triangular and invertible, and Q^∈𝔽n×n is unitary. Such matrices exist by RQ-decomposition.
* Y=W*D. Then Y is invertible.

Here are some variations of the GSVD:

* MATLAB (gsvd):A1=U1Σ1X*,A2=U2Σ2X*.
* LAPACK (ggsvd3):A1=U1Σ1[0,R]Q^*,A2=U2Σ2[0,R]Q^*.
* Simplified:A1=U1Σ1[Y,0D]Q*,A2=U2Σ2[Y,0D]Q*.

### 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 A1 and A2 is a pair (a,b)∈ℝ2 such that

limδ->0det⁡(b2A1*A1−a2A2*A2+δIn)/det⁡(δIn−k)=0,a2+b2=1,a,b≥0.Other sources call such (a,b)∈ℝ2 generalized singular value pairs and use generalized singular value to refer to the ratio a/b.[6][7][8]

Regardless of the naming convention, we have

* AiAj*=UiΣiYY*Σj*Uj*
* Ai*Aj=Q[Y*Σi*ΣjY000]Q*=Q1Y*Σi*ΣjYQ1*

By these properties we can show that the generalized singular values are exactly the pairs (αi,βi). We havedet⁡(b2A1*A1−a2A2*A2+δIn)=det⁡(b2A1*A1−a2A2*A2+δQQ*)=det⁡(Q[Y*(b2Σ1*Σ1−a2Σ2*Σ2)Y+δIk00δIn−k]Q*)=det⁡(δIn−k)det⁡(Y*(b2Σ1*Σ1−a2Σ2*Σ2)Y+δIk).Therefore

limδ->0det⁡(b2A1*A1−a2A2*A2+δIn)/det⁡(δIn−k)=limδ->0det⁡(Y*(b2Σ1*Σ1−a2Σ2*Σ2)Y+δIk)=det⁡(Y*(b2Σ1*Σ1−a2Σ2*Σ2)Y)=|det⁡(Y)|2∏i=1k(b2αi2−a2βi2).

This expression is zero exactly when a=αi and b=βi for some i.

In,[2] the generalized singular values are claimed to be those which solve det⁡(b2A1*A1−a2A2*A2)=0. However, this claim only holds when k=n, since otherwise the determinant is zero for every pair (a,b)∈ℝ2; this can be seen by substituting δ=0 above.

### Generalized inverse

Define E+=E−1 for any invertible matrix E∈𝔽n×n , 0+=0* for any zero matrix 0∈𝔽m×n, and ⌈E1,E2⌋+=⌈E1+,E2+⌋ for any block-diagonal matrix. Then defineAi+=Q[Y−10]Σi+Ui*It can be shown that Ai+ as defined here is a generalized inverse of Ai; in particular a {1,2,3}-inverse of Ai. Since it does not in general satisfy (Ai+Ai)*=Ai+Ai, this is not the Moore–Penrose inverse; otherwise we could derive (AB)+=B+A+ for any choice of matrices, which only holds for certain class of matrices.

Suppose Q=[Q1Q2], where Q1∈𝔽n×k and Q2∈𝔽n×(n−k). This generalized inverse has the following properties:

* Σ1+=⌈IA,S1−1,0AT⌋
* Σ2+=⌈0BT,S2−1,IB⌋
* Σ1Σ1+=⌈I,I,0⌋
* Σ2Σ2+=⌈0,I,I⌋
* Σ1Σ2+=⌈0,S1S2−1,0⌋
* Σ1+Σ2=⌈0,S1−1S2,0⌋
* AiAj+=UiΣiΣj+Uj*
* Ai+Aj=Q[Y−1Σi+ΣjY000]Q*=Q1Y−1Σi+ΣjYQ1*

### Quotient SVD

A generalized singular ratio (or just "generalized singular value," depending on one's naming convention[6][7][8]) of A1 and A2 is σi=αiβi+. By the above properties, A1A2+=U1Σ1Σ2+U2*. Note that Σ1Σ2+=⌈0,S1S2−1,0⌋ is diagonal, and that, ignoring the leading zeros, contains the singular ratios in decreasing order. If A2 is invertible, then Σ1Σ2+ has no leading zeros, and the generalized singular ratios are the singular values, and U1 and U2 are the matrices of singular vectors, of the matrix A1A2+=A1A2−1. In fact, computing the SVD of A1A2−1 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. If A2 is not invertible, then U1Σ1Σ2+U2*is still the SVD of A1A2+ 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: U1Σ1Σ2+U2*=(U1P1)P1*Σ1Σ2+P2(P2*U2*), where P1 and P2 are appropriate permutation matrices. Since rank equals the number of non-zero singular values, rank(A1A2+)=s.

### Construction

Let

* C=P⌈D,0⌋Q* be the SVD of C=[A1A2], where P∈𝔽(m1+m2)×(m1×m2) is unitary, and Q and D are as described,
* P=[P1,P2], where P1∈𝔽(m1+m2)×k and P2∈𝔽(m1+m2)×(n−k),
* P1=[P11P21], where P11∈𝔽m1×k and P21∈𝔽m2×k,
* P11=U1Σ1W* by the SVD of P11, where U1, Σ1 and W are as described,
* P21W=U2Σ2 by a decomposition similar to a QR-decomposition, where U2 and Σ2 are as described.

ThenC=P⌈D,0⌋Q*=[P1D,0]Q*=[U1Σ1W*D0U2Σ2W*D0]Q*=[U1Σ1[W*D,0]Q*U2Σ2[W*D,0]Q*].We also have[U1*00U2*]P1W=[Σ1Σ2].ThereforeΣ1*Σ1+Σ2*Σ2=[Σ1Σ2]*[Σ1Σ2]=W*P1*[U100U2][U1*00U2*]P1W=I.Since P1 has orthonormal columns, ||P1||2≤1. Therefore||Σ1||2=||U1*P1W||2=||P1||2≤1.We also have for each x∈ℝk such that ||x||2=1 that||P21x||22≤||P11x||22+||P21x||22=||P1x||22≤1.Therefore ||P21||2≤1, and||Σ2||2=||U2*P21W||2=||P21||2≤1.

## Applications

The tensor GSVD is one of the comparative spectral decompositions, multi-tensor generalizations of the SVD, invented to simultaneously identify the similar and dissimilar among, and create a single coherent model from any data types, of any number and dimensions.

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

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

It has equally found applications to estimate the spectral decompositions of linear operators when the eigenfunctions are parameterized with a linear model, i.e. a reproducing kernel Hilbert space.[16]

## 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.[17][18][19] 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ΣV*

where

U*WuU=V*WvV=I.

Where I is the identity matrix and where U and V are orthonormal given their constraints (Wu and Wv). Additionally, Wu and Wv 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).[20]

## References

1. ↑ Van Loan, Charles F. (1976). "Generalizing the Singular Value Decomposition". SIAM J. Numer. Anal. 13 (1): 76–83. doi:10.1137/0713009. Bibcode: 1976SJNA...13...76V.
2. ↑ 2.0 2.1 2.2 Paige, C. C.; Saunders, M. A. (1981). "Towards a Generalized Singular Value Decomposition". SIAM J. Numer. Anal. 18 (3): 398–405. doi:10.1137/0718026. Bibcode: 1981SJNA...18..398P.
3. ↑ Hansen, Per Christian (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.
4. ↑ de Moor, Bart L. R.; Golub, Gene H. (1989). "Generalized Singular Value Decompositions A Proposal for a Standard Nomenclauture". https://ftp.esat.kuleuven.be/pub/SISTA/ida/reports/89-10.pdf.
5. ↑ de Moor, Bart L. R.; Zha, Hongyuan (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.
6. ↑ 6.0 6.1 Bai, Zhaojun; Demmel, James W. (1993). "Computing the Generalized Singular Value Decomposition". SIAM Journal on Scientific Computing 14 (6): 1464–1486. doi:10.1137/0914085. ISSN 1064-8275. https://epubs.siam.org/doi/10.1137/0914085.
7. ↑ 7.0 7.1 "Generalized Singular Value Decomposition (GSVD)". https://www.netlib.org/lapack/lug/node36.html.
8. ↑ 8.0 8.1 Golub, Gene H.; Van Loan, Charles F. (2013). Matrix computations. Johns Hopkins studies in the mathematical sciences (4th ed.). Baltimore: The Johns Hopkins University Press. pp. 501-502. ISBN 978-1-4214-0794-4.
9. ↑ "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. March 2003. doi:10.1073/pnas.0530258100. PMID 12631705. Bibcode: 2003PNAS..100.3351A.
10. ↑ "GSVD comparison of patient-matched normal and tumor aCGH profiles reveals global copy-number alterations predicting glioblastoma multiforme survival". PLOS ONE 7 (1). January 2012. doi:10.1371/journal.pone.0030098. PMID 22291905. Bibcode: 2012PLoSO...730098L.
11. ↑ "Mathematically universal and biologically consistent astrocytoma genotype encodes for transformation and predicts survival phenotype". APL Bioengineering 2 (3). September 2018. doi:10.1063/1.5037882. PMID 30397684.
12. ↑ "Retrospective Clinical Trial Experimentally Validates Glioblastoma Genome-Wide Pattern of DNA Copy-Number Alterations Predictor of Survival". APL Bioengineering 4 (2). May 2020. doi:10.1063/1.5142559. Press Release. PMID 32478280.
13. ↑ "A higher-order generalized singular value decomposition for comparison of global mRNA expression from multiple organisms". PLOS ONE 6 (12). December 2011. doi:10.1371/journal.pone.0028072. PMID 22216090. Bibcode: 2011PLoSO...628072P.
14. ↑ "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). April 2015. doi:10.1371/journal.pone.0121396. PMID 25875127. Bibcode: 2015PLoSO..1021396S.
15. ↑ "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). September 2019. doi:10.1063/1.5099268. Supplementary Material. PMID 31463421.
16. ↑ Cabannes, Vivien; Pillaud-Vivien, Loucas; Bach, Francis; Rudi, Alessandro (2021). "Overcoming the curse of dimensionality with Laplacian regularization in semi-supervised learning". arXiv:2009.04324 [stat.ML].
17. ↑ Principal Component Analysis. Springer Series in Statistics (2nd ed.). NY: Springer. 2002. ISBN 978-0-387-95442-4. https://archive.org/details/principalcompone00joll_0.
18. ↑ Greenacre, Michael (1983). Theory and Applications of Correspondence Analysis. London: Academic Press. ISBN 978-0-12-299050-2.
19. ↑ "Principal component analysis.". Wiley Interdisciplinary Reviews: Computational Statistics 2 (4): 433–459. 2010. doi:10.1002/wics.101.
20. ↑ "Singular Value Decomposition (SVD) and Generalized Singular Value Decomposition (GSVD).". Encyclopedia of Measurement and Statistics.. Thousand Oaks (CA): Sage. 2007. pp. 907–912. https://archive.org/details/encyclopediameas00salk.

## Further reading

* Golub, Gene; Van Loan, Charles (1996). Matrix Computation (Third ed.). Baltimore: Johns Hopkins University Press. ISBN 0-8018-5414-8.
* LAPACK manual [1]

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Generalized singular value decomposition. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Generalized_singular_value_decomposition&oldid=4297964"