Обобщенное разложение по сингулярным значениям

В линейной алгебре обобщенное разложение по сингулярным значениям ( GSVD ) — это название двух различных методов, основанных на разложении по сингулярным значениям (SVD) . Две версии различаются тем, что одна версия разлагает две матрицы (что-то вроде SVD высшего порядка или тензора ), а другая версия использует набор ограничений, налагаемых на левый и правый сингулярные векторы одноматричной SVD.

Первая версия: двухматричное разложение

Обобщенное сингулярное разложение ( GSVD ) представляет собой матричное разложение на пару матриц, которое обобщает сингулярное разложение . Его представил Ван Лоан. в 1976 году и позже разработанный Пейдж и Сондерс , какая версия описана здесь. В отличие от SVD, GSVD разлагает одновременно пару матриц с одинаковым количеством столбцов. СВД и ГСВД, а также некоторые другие возможные обобщения СВД, широко используются при изучении обусловленности и регуляризации линейных систем относительно квадратичных полунорм . В дальнейшем пусть $\mathbb {F} =\mathbb {R}$, или $\mathbb {F} =\mathbb {C}$.

Определение

Обобщенное по сингулярным значениям разложение матриц $A_{1}\in \mathbb {F} ^{m_{1}\times n}$ и $A_{2}\in \mathbb {F} ^{m_{2}\times n}$ является

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

где

• $U_{1}\in \mathbb {F} ^{m_{1}\times m_{1}}$ является унитарным ,
• $U_{2}\in \mathbb {F} ^{m_{2}\times m_{2}}$ является унитарным,
• $Q\in \mathbb {F} ^{n\times n}$ является унитарным,
• $W\in \mathbb {F} ^{k\times k}$является унитарным,
• $D\in \mathbb {R} ^{k\times k}$ является вещественной диагональю с положительной диагональю и содержит ненулевые сингулярные значения $C={\begin{bmatrix}A_{1}\\A_{2}\end{bmatrix}}$ в порядке убывания,
• $0_{D}=0\in \mathbb {R} ^{k\times (n-k)}$,
• $\Sigma _{1}=\lceil I_{A},S_{1},0_{A}\rfloor \in \mathbb {R} ^{m_{1}\times k}$ действительная неотрицательная блок-диагональ , где $S_{1}=\lceil \alpha _{r+1},\dots ,\alpha _{r+s}\rfloor$ с $1>\alpha _{r+1}\geq \cdots \geq \alpha _{r+s}>0$, $I_{A}=I_{r}$, и $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}$ – действительная неотрицательная блок-диагональ, где $S_{2}=\lceil \beta _{r+1},\dots ,\beta _{r+s}\rfloor$ с $0<\beta _{r+1}\leq \cdots \leq \beta _{r+s}<1$, $I_{B}=I_{k-r-s}$, и $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}}(C)$.

Обозначим $\alpha _{1}=\cdots =\alpha _{r}=1$, $\alpha _{r+s+1}=\cdots =\alpha _{k}=0$, $\beta _{1}=\cdots =\beta _{r}=0$, и $\beta _{r+s+1}=\cdots =\beta _{k}=1$. Пока $\Sigma _{1}$ диагональная, $\Sigma _{2}$ не всегда диагональна из-за ведущей прямоугольной нулевой матрицы; вместо $\Sigma _{2}$ является «нижней правой диагональю».

Вариации

Существует множество вариаций ГСВД. Эти вариации связаны с тем, что всегда можно умножить $Q^{*}$ слева от $EE^{*}=I$ где $E\in \mathbb {F} ^{n\times n}$ — произвольная унитарная матрица. Обозначим

• $X=([W^{*}D,0_{D}]Q^{*})^{*}$
• $X^{*}=[0,R]{\hat {Q}}^{*}$, где $R\in \mathbb {F} ^{k\times k}$ является верхнетреугольным и обратимым, а ${\hat {Q}}\in \mathbb {F} ^{n\times n}$ является унитарным. Такие матрицы существуют посредством RQ-разложения .
• $Y=W^{*}D$. Затем $Y$ является обратимым.

Вот некоторые варианты GSVD:

• МАТЛАБ (гсвд):
  $${\begin{aligned}A_{1}&=U_{1}\Sigma _{1}X^{*},\\A_{2}&=U_{2}\Sigma _{2}X^{*}.\end{aligned}}$$
• ЛАПАК (LA_GGSVD):
  $${\begin{aligned}A_{1}&=U_{1}\Sigma _{1}[0,R]{\hat {Q}}^{*},\\A_{2}&=U_{2}\Sigma _{2}[0,R]{\hat {Q}}^{*}.\end{aligned}}$$
• Упрощенно:
  $${\begin{aligned}A_{1}&=U_{1}\Sigma _{1}[Y,0_{D}]Q^{*},\\A_{2}&=U_{2}\Sigma _{2}[Y,0_{D}]Q^{*}.\end{aligned}}$$

Обобщенные сингулярные значения

Обобщенное сингулярное значение $A_{1}$ и $A_{2}$ это пара $(a,b)\in \mathbb {R} ^{2}$ такой, что

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

У нас есть

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

Благодаря этим свойствам мы можем показать, что обобщенные сингулярные значения — это в точности пары $(\alpha _{i},\beta _{i})$. У нас есть

$${\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 QQ^{*})\\=&\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}}$$

Поэтому

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

Это выражение равно нулю именно тогда, когда $a=\alpha _{i}$ и $b=\beta _{i}$ для некоторых $i$.

В, утверждается, что обобщенные сингулярные значения — это те, которые решают $\det(b^{2}A_{1}^{*}A_{1}-a^{2}A_{2}^{*}A_{2})=0$. Однако это утверждение справедливо только тогда, когда $k=n$, так как в противном случае определитель равен нулю для каждой пары $(a,b)\in \mathbb {R} ^{2}$; это можно увидеть, заменив $\delta =0$ выше.

Обобщенное обратное

Определять $E^{+}=E^{-1}$ для любой обратимой матрицы $E\in \mathbb {F} ^{n\times n}$ , $0^{+}=0^{*}$ для любой нулевой матрицы $0\in \mathbb {F} ^{m\times n}$, и $\left\lceil E_{1},E_{2}\right\rfloor ^{+}=\left\lceil E_{1}^{+},E_{2}^{+}\right\rfloor$ для любой блочно-диагональной матрицы. Затем определите

$$A_{i}^{+}=Q{\begin{bmatrix}Y^{-1}\\0\end{bmatrix}}\Sigma _{i}^{+}U_{i}^{*}$$

Можно показать, что $A_{i}^{+}$ как определено здесь, является обобщенной инверсией $A_{i}$; в частности $\{1,2,3\}$-обратный $A_{i}$. Поскольку это в целом не удовлетворяет $(A_{i}^{+}A_{i})^{*}=A_{i}^{+}A_{i}$, это не инверсия Мура-Пенроуза ; в противном случае мы могли бы вывести $(AB)^{+}=B^{+}A^{+}$ для любого выбора матриц, что справедливо только для определенного класса матриц .

Предполагать $Q={\begin{bmatrix}Q_{1}&Q_{2}\end{bmatrix}}$, где $Q_{1}\in \mathbb {F} ^{n\times k}$ и $Q_{2}\in \mathbb {F} ^{n\times (n-k)}$. Это обобщенное обратное имеет следующие свойства:

• $\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 _{1}\Sigma _{1}^{+}=\lceil I,I,0\rfloor$
• $\Sigma _{2}\Sigma _{2}^{+}=\lceil 0,I,I\rfloor$
• $\Sigma _{1}\Sigma _{2}^{+}=\lceil 0,S_{1}S_{2}^{-1},0\rfloor$
• $\Sigma _{1}^{+}\Sigma _{2}=\lceil 0,S_{1}^{-1}S_{2},0\rfloor$
• $A_{i}A_{j}^{+}=U_{i}\Sigma _{i}\Sigma _{j}^{+}U_{j}^{*}$
• $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}^{*}$

Частное СВД

Обобщенное сингулярное отношение $A_{1}$ и $A_{2}$ является $\sigma _{i}=\alpha _{i}\beta _{i}^{+}$. По вышеуказанным свойствам, $A_{1}A_{2}^{+}=U_{1}\Sigma _{1}\Sigma _{2}^{+}U_{2}^{*}$. Обратите внимание, что $\Sigma _{1}\Sigma _{2}^{+}=\lceil 0,S_{1}S_{2}^{-1},0\rfloor$ является диагональным и, если игнорировать ведущие нули, содержит сингулярные отношения в порядке убывания. Если $A_{2}$ обратимо, то $\Sigma _{1}\Sigma _{2}^{+}$ не имеет ведущих нулей, а обобщенные сингулярные отношения являются сингулярными значениями, а $U_{1}$ и $U_{2}$ – матрицы сингулярных векторов матрицы $A_{1}A_{2}^{+}=A_{1}A_{2}^{-1}$. Фактически, вычисление SVD $A_{1}A_{2}^{-1}$ является одной из мотиваций ГСВД, поскольку «формирование $AB^{-1}$ и нахождение его СВД может привести к ненужным и большим численным ошибкам при $B$ плохо обусловлен для решения уравнений». Отсюда иногда используемое название «частное СВД», хотя это не единственная причина использования ГСВД. Если $A_{2}$ не обратимо, то $U_{1}\Sigma _{1}\Sigma _{2}^{+}U_{2}^{*}$все еще СВД $A_{1}A_{2}^{+}$ если мы ослабим требование иметь сингулярные значения в порядке убывания. Альтернативно, SVD в порядке убывания можно найти, переместив ведущие нули назад: $U_{1}\Sigma _{1}\Sigma _{2}^{+}U_{2}^{*}=(U_{1}P_{1})P_{1}^{*}\Sigma _{1}\Sigma _{2}^{+}P_{2}(P_{2}^{*}U_{2}^{*})$, где $P_{1}$ и $P_{2}$ являются соответствующими матрицами перестановок. Поскольку ранг равен количеству ненулевых сингулярных значений, $\mathrm {rank} (A_{1}A_{2}^{+})=s$.

Строительство

Позволять

• $C=P\lceil D,0\rfloor Q^{*}$ быть СВД $C={\begin{bmatrix}A_{1}\\A_{2}\end{bmatrix}}$, где $P\in \mathbb {F} ^{(m_{1}+m_{2})\times (m_{1}\times m_{2})}$ является унитарным, и $Q$ и $D$ как описано,
• $P=[P_{1},P_{2}]$, где $P_{1}\in \mathbb {F} ^{(m_{1}+m_{2})\times k}$ и $P_{2}\in \mathbb {F} ^{(m_{1}+m_{2})\times (n-k)}$,
• $P_{1}={\begin{bmatrix}P_{11}\\P_{21}\end{bmatrix}}$, где $P_{11}\in \mathbb {F} ^{m_{1}\times k}$ и $P_{21}\in \mathbb {F} ^{m_{2}\times k}$,
• $P_{11}=U_{1}\Sigma _{1}W^{*}$ со стороны СВД $P_{11}$, где $U_{1}$, $\Sigma _{1}$ и $W$ как описано,
• $P_{21}W=U_{2}\Sigma _{2}$ путем разложения, аналогичного QR-разложению , где $U_{2}$ и $\Sigma _{2}$ как описано.

Затем

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

У нас также есть

$${\begin{bmatrix}U_{1}^{*}&0\\0&U_{2}^{*}\end{bmatrix}}P_{1}W={\begin{bmatrix}\Sigma _{1}\\\Sigma _{2}\end{bmatrix}}.$$

Поэтому

$$\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.$$

С $P_{1}$ имеет ортонормированные столбцы, $||P_{1}||_{2}\leq 1$. Поэтому

$$||\Sigma _{1}||_{2}=||U_{1}^{*}P_{1}W||_{2}=||P_{1}||_{2}\leq 1.$$

У нас также есть для каждого $x\in \mathbb {R} ^{k}$ такой, что $||x||_{2}=1$ что

$$||P_{21}x||_{2}^{2}\leq ||P_{11}x||_{2}^{2}+||P_{21}x||_{2}^{2}=||P_{1}x||_{2}^{2}\leq 1.$$

Поэтому $||P_{21}||_{2}\leq 1$, и

$$||\Sigma _{2}||_{2}=||U_{2}^{*}P_{21}W||_{2}=||P_{21}||_{2}\leq 1.$$

Приложения

Тензор GSVD — это одно из сравнительных спектральных разложений, мультитензорных обобщений SVD, изобретенное для одновременного выявления похожего и непохожего среди и создания единой когерентной модели из любых типов данных, любого количества и размерностей.

GSVD, сформулированный как сравнительное спектральное разложение, был успешно применен в обработке сигналов и науке о данных, например, при обработке геномных сигналов.

Эти приложения вдохновили на создание нескольких дополнительных сравнительных спектральных разложений, то есть GSVD более высокого порядка (HO GSVD). и тензор ГСВД.

Он также нашел применение для оценки спектральных разложений линейных операторов, когда собственные функции параметризованы с помощью линейной модели, то есть воспроизводящего ядра гильбертова пространства .

одноматричное

Взвешенная версия обобщенного сингулярного разложения ( GSVD ) представляет собой матричное разложение с ограничениями, налагаемыми на левый и правый сингулярные векторы сингулярного разложения . Эта форма БСВД является продолжением СВД как таковой. Учитывая SVD действительной m × n или комплексной матрицы M

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

где

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

Где I — единичная матрица , а где $U$ и $V$ ортонормированы с учетом их ограничений ( $W_{u}$ и $W_{v}$). Кроме того, $W_{u}$ и $W_{v}$ являются положительно определенными матрицами (часто диагональными матрицами весов). Эта форма GSVD является основой некоторых методов, таких как обобщенный анализ главных компонентов и анализ соответствия .

Взвешенная форма БСВД называется так потому, что при правильном выборе весов она обобщает многие методы (такие как многомерное масштабирование и линейный дискриминантный анализ ).

Дальнейшее чтение

• Голуб Г., Ван Лоан С. (1996). Матричные вычисления (Третье изд.). Балтимор: Издательство Университета Джонса Хопкинса. ISBN  0-8018-5414-8 .
• LAPACK Инструкция по эксплуатации [1]