Английская Википедия:Generalized singular value decomposition

Шаблон:Short description Шаблон:Use dmy dates 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 ^[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 <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>

Y </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 (LA_GGSVD):<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

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

<math display="block"> \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>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,^[2] the generalized singular values are claimed to be those which solve <math>\det(b^2 A_1^* A_1 - a^2 A_2^* A_2) = 0</math>. However, this claim only holds when <math>k = n</math>, since otherwise the determinant is zero for every pair <math>(a, b) \in \mathbb{R}^2</math>; this can be seen by substituting <math>\delta = 0</math> above.

Generalized inverse

Define <math>E^+ = E^{-1}</math> for any invertible matrix <math>E \in \mathbb{F}^{n \times n}</math> , <math>0^+ = 0^*</math> for any zero matrix <math>0 \in \mathbb{F}^{m \times n}</math>, and <math>\left\lceil E_1, E_2 \right\rfloor^+ = \left\lceil E_1^+, E_2^+ \right\rfloor</math> for any block-diagonal matrix. Then define<math display="block">A_i^+ = Q \begin{bmatrix} Y^{-1} \\ 0 \end{bmatrix} \Sigma_i^+ U_i^*</math>It can be shown that <math>A_i^+</math> as defined here is a generalized inverse of <math>A_i</math>; in particular a <math>\{1, 2, 3\}</math>-inverse of <math>A_i</math>. Since it does not in general satisfy <math>(A_i^+ A_i)^* = A_i^+ A_i</math>, this is not the Moore–Penrose inverse; otherwise we could derive <math>(AB)^+ = B^+ A^+</math> for any choice of matrices, which only holds for certain class of matrices.

Suppose <math> Q = \begin{bmatrix}Q_1 & Q_2\end{bmatrix} </math>, where <math>Q_1 \in \mathbb{F}^{n \times k}</math> and <math>Q_2 \in \mathbb{F}^{n \times (n - k)}</math>. This generalized inverse has the following properties:

<math> \Sigma_1^+ = \lceil I_A, S_1^{-1}, 0_A^T \rfloor </math>
<math> \Sigma_2^+ = \lceil 0^T_B, S_2^{-1}, I_B \rfloor </math>
<math> \Sigma_1 \Sigma_1^+ = \lceil I, I, 0 \rfloor </math>
<math> \Sigma_2 \Sigma_2^+ = \lceil 0, I, I \rfloor </math>
<math> \Sigma_1 \Sigma_2^+ = \lceil 0, S_1 S_2^{-1}, 0 \rfloor </math>
<math> \Sigma_1^+ \Sigma_2 = \lceil 0, S_1^{-1} S_2, 0 \rfloor </math>
<math> A_i A_j^+ = U_i \Sigma_i \Sigma_j^+ U_j^*</math>
<math> 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 Y Q_1^* </math>

Quotient SVD

A generalized singular ratio of <math>A_1</math> and <math>A_2</math> is <math>\sigma_i=\alpha_i \beta_i^+</math>. By the above properties, <math> A_1 A_2^+ = U_1 \Sigma_1 \Sigma_2^+ U_2^*</math>. Note that <math> \Sigma_1 \Sigma_2^+ = \lceil 0, S_1 S_2^{-1}, 0 \rfloor </math> is diagonal, and that, ignoring the leading zeros, contains the singular ratios in decreasing order. If <math>A_2</math> is invertible, then <math> \Sigma_1 \Sigma_2^+ </math> has no leading zeros, and the generalized singular ratios are the singular values, and <math>U_1</math> and <math>U_2</math> are the matrices of singular vectors, of the matrix <math>A_1 A_2^+ = A_1 A_2^{-1}</math>. In fact, computing the SVD of <math>A_1 A_2^{-1}</math> is one of the motivations for the GSVD, as "forming <math>AB^{-1}</math> and finding its SVD can lead to unnecessary and large numerical errors when <math>B</math> 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 <math>A_2</math> is not invertible, then <math> U_1 \Sigma_1 \Sigma_2^+ U_2^*</math>is still the SVD of <math> A_1 A_2^+</math> 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: <math> U_1 \Sigma_1 \Sigma_2^+ U_2^* = (U_1 P_1) P_1^* \Sigma_1 \Sigma_2^+ P_2 (P_2^* U_2^*)</math>, where <math> P_1</math> and <math> P_2</math> are appropriate permutation matrices. Since rank equals the number of non-zero singular values, <math> \mathrm{rank}(A_1 A_2^+)=s</math>.

Construction

Let

<math>C = P \lceil D, 0 \rfloor Q^*</math> be the SVD of <math>C = \begin{bmatrix} A_1 \\ A_2 \end{bmatrix}</math>, where <math>P \in \mathbb{F}^{(m_1 + m_2) \times (m_1 \times m_2)}</math> is unitary, and <math>Q</math> and <math>D</math> are as described,
<math>P = [P_1, P_2]</math>, where <math>P_1 \in \mathbb{F}^{(m_1 + m_2) \times k}</math> and <math>P_2 \in \mathbb{F}^{(m_1 + m_2) \times (n - k)}</math>,
<math>P_1 = \begin{bmatrix} P_{11} \\ P_{21} \end{bmatrix}</math>, where <math>P_{11} \in \mathbb{F}^{m_1 \times k}</math> and <math>P_{21} \in \mathbb{F}^{m_2 \times k}</math>,
<math>P_{11} = U_1 \Sigma_1 W^*</math> by the SVD of <math>P_{11}</math>, where <math>U_1</math>, <math>\Sigma_1</math> and <math>W</math> are as described,
<math>P_{21} W = U_2 \Sigma_2</math> by a decomposition similar to a QR-decomposition, where <math>U_2</math> and <math>\Sigma_2</math> are as described.

Then<math display="block">\begin{aligned} C & = P \lceil D, 0 \rfloor Q^* \\ {} & = [P_1 D, 0] Q^* \\ {} & = \begin{bmatrix} U_1 \Sigma_1 W^* D & 0 \\ U_2 \Sigma_2 W^* D & 0 \end{bmatrix} Q^* \\ {} & = \begin{bmatrix} U_1 \Sigma_1 [W^* D, 0] Q^* \\ U_2 \Sigma_2 [W^* D, 0] Q^* \end{bmatrix} . \end{aligned}</math>We also have<math display="block">\begin{bmatrix} U_1^* & 0 \\ 0 & U_2^* \end{bmatrix} P_1 W = \begin{bmatrix} \Sigma_1 \\ \Sigma_2 \end{bmatrix}.</math>Therefore<math display="block">\Sigma_1^* \Sigma_1 + \Sigma_2^* \Sigma_2 = \begin{bmatrix} \Sigma_1 \\ \Sigma_2 \end{bmatrix}^* \begin{bmatrix} \Sigma_1 \\ \Sigma_2 \end{bmatrix} = W^* P_1^* \begin{bmatrix} U_1 & 0 \\ 0 & U_2 \end{bmatrix} \begin{bmatrix} U_1^* & 0 \\ 0 & U_2^* \end{bmatrix} P_1 W = I.</math>Since <math>P_1</math> has orthonormal columns, <math>||P_1||_2 \leq 1</math>. Therefore<math display="block">||\Sigma_1||_2 = ||U_1^* P_1 W||_2 = ||P_1||_2 \leq 1.</math>We also have for each <math>x \in \mathbb{R}^k</math> such that <math>||x||_2 = 1</math> that<math display="block">||P_{21} x||_2^2 \leq ||P_{11} x||_2^2 + ||P_{21} x||_2^2 = ||P_{1} x||_2^2 \leq 1.</math>Therefore <math>||P_{21}||_2 \leq 1</math>, and<math display="block">||\Sigma_2||_2 = || U_2^* P_{21} W ||_2 = ||P_{21}||_2 \leq 1.</math>

Applications

Файл:Tensor Generalized Singular Value Decomposition following et int. Alter PLoS One 2015 and Alter NCI Physical Sciences in Oncology 2015.jpg

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,^[6] has been successfully applied to signal processing and data science, e.g., in genomic signal processing.^[7]^[8]^[9]

These applications inspired several additional comparative spectral decompositions, i.e., the higher-order GSVD (HO GSVD)^[10] and the tensor GSVD.^[11] ^[12]

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

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.^[14]^[15]^[16] 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

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).^[17]

References

Шаблон:Reflist

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Английская Википедия:Generalized singular value decomposition

Содержание

First version: two-matrix decomposition

Definition

Variations

Generalized singular values

Generalized inverse

Quotient SVD

Construction

Applications

Second version: weighted single-matrix decomposition

References

Further reading

Навигация

Действия на странице

Действия на странице

Персональные инструменты

Навигация

Поиск

Инструменты