Инструменты сайта


Сингулярное разложение матрицы

§

Для понимания материалов этого раздела рекомендуется просмотреть материалы разделов СИММЕТРИЧНАЯ МАТРИЦА и ХАРАКТЕРИСТИЧЕСКИЙ ПОЛИНОМ.

В настоящем разделе все матрицы предполагаются вещественными.

Некоторые предварительные сведения

о матрицах $ A\cdot A^{\top} $ и $ A^{\top} A $ для матрицы $ A\in \mathbb R^{m\times n} $.

1. Обе матрицы — симметричны (хотя и не обязательно одинаковых порядков).

2. Матрица $ A\cdot A^{\top} $ — матрица Грама системы строк, а $ A^{\top} A $ — матрица Грама системы столбцов матрицы $ A $. Так если представить матрицу $ A $ как результат конкатенации ее столбцов $ A=[A_{[1]}|A_{[2]}|\dots |A_{[n]} ] $, то $$ A^{\top} A = G(A_{[1]},A_{[2]},\dots ,A_{[n]}) \, ; $$ здесь скалярное произведение задано стандартным способом.

Отсюда, в частности, следует, что если $ \operatorname{rank} (A) = \mathfrak r $, то $$ \operatorname{rank} ( A\cdot A^{\top}) = \operatorname{rank} (A^{\top} A) = \mathfrak r \, . $$

3. Характеристические полиномы этих матриц могут различаться только лишь на степень переменной: $$ (-\lambda)^n \det (A \cdot A^{\top} - \lambda E_{m\times m})\equiv (-\lambda)^m \det ( A^{\top} A - \lambda E_{n\times n}) \ . $$

4. Собственные числа обеих матриц вещественны и неотрицательны. Количество ненулевых совпадает с $ \operatorname{rank} (A) = \mathfrak r $. Условимся обозначать положительные в виде $ \lambda_1^2,\dots,\lambda_{\mathfrak r}^2 $. Таким образом спектры матриц: $$ \begin{array}{c|c} A\cdot A^{\top} & A^{\top} A \\ \hline \{\lambda_1^2,\dots,\lambda_{\mathfrak r}^2,\underbrace{0,\dots,0}_{m-\mathfrak r}\} & \{\lambda_1^2,\dots,\lambda_{\mathfrak r}^2,\underbrace{0,\dots,0}_{n-\mathfrak r}\} \, . \end{array} $$

5. Существуют положительно полуопределенные квадратные корни из матриц $ A\cdot A^{\top} $ и $ A^{\top} A $, т.е. вещественные симметричные матрицы $ X $ и $ Y $ такие, что $$ X^2= A\cdot A^{\top},\ Y^2=A^{\top} A \, . $$

Полярное разложение

Т

Теорема 1. Пусть задана матрица $ A \in \mathbb R^{m\times n} $, причем $ m\le n $ и $ \operatorname{rank} (A)=\mathfrak r \le m $. Существует

$$ P \cdot P^{\top} = E \in \mathbb R^{m\times m} \ ; $$

$$ \Lambda= \left(\begin{array}{cccccccc} \lambda_1 & & & & \\ & \lambda_2 & & & \\ & & \ddots & & \\ & & & \lambda_{\mathfrak r} & \\ & & & & 0 &\\ & & & & & 0 & \\ & & & & & & \ddots & \\ & & & & & & & 0 \end{array} \right) $$ с неотрицательными диагональными элементами $$ \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_{\mathfrak r} > \lambda_{\mathfrak r+1}=\dots = \lambda_{m}=0 \ , $$

$$ Q \cdot Q^{\top} = E_{m\times m} \ ,$$ такие, что $$ A = P \Lambda Q \, . $$ При этом

$$ P= \left[\mathfrak X_1|\mathfrak X_2|\dots | \mathfrak X_m \right],\ npu \ ( A \cdot A^{\top}-\lambda_j^2 E) \mathfrak X_j = \mathbb O_{m\times 1} \, . $$

Т

Теорема 2. Пусть задана матрица $ A \in \mathbb R^{m\times n} $, причем $ m \le n $. Тогда $ A $ представима в виде $$ A=PU $$ где

  • симметричная матрица $ P $ положительно полуопределена, $ \operatorname{rank} (P)= \operatorname{rank} (A) $;
  • матрица $ U \in \mathbb R^{m\times n} $ имеет ортонормированные строки, т.е. $ U \cdot U^{\top} = E_{m \times m } $.

Матрица $ P $ определена однозначно: $ P=\sqrt{A\cdot A^{\top}} $. Матрица $ U $ определена однозначно если $ \operatorname{rank} (A) =m $.


Разложение из теоремы называется полярным разложением матрицы $ A $.


Доказательство. Используя теорему 1, запишем матрицу $ A $ в виде $$ A=P_1 \Lambda Q_1=P_1 \Lambda P_1^{\top} P_1 Q_1 $$ и положим $ P=P_1 \Lambda P_1^{\top} $, $ U= P_1 Q_1 $. Тогда $ P $ положительно полуопределена и $$ U\cdot U^{\top}=P_1 Q_1Q_1^{\top} P_1^{\top} = P_1 E P_1^{\top}=P_1 \cdot P_1^{\top}= E \ , $$ так что $ U $ имеет ортонормированные строки. Если $ A=PU $, то $$ A \cdot A^{\top}=PU\cdot U^{\top} P=P^2 $$ и $ P $ должна быть единственным положительно полуопределенным квадратным корнем из $ A \cdot A^{\top} $ (см. ЗДЕСЬ). Если $ \operatorname{rank} (A) =m $, то матрица $ P $ невырожденна, и матрица $ U=P^{-1} A $ определена однозначно.

Сингулярное разложение

Т

Теорема (о сингулярном разложении). Для матрицы $ A \in \mathbb R^{m\times n} $, $ \operatorname{rank} (A)=\mathfrak r $ существует представление ее в виде произведения $$ A=V \Sigma W^{\top} \, . $$

Схематически при $ m<n $:

а при $ m>n $:

Здесь

  • $ V \in \mathbb R^{m\times m} $ и $ W \in \mathbb R^{n\times n} $ — ортогональные матрицы;
  • матрица $ \Sigma \in \mathbb R^{m\times n} $ имеет ненулевыми только элементы $ \sigma_{jj}=\sigma_j $ при $ j\in \{1,\dots, \mathfrak r \} $:

$$ \Sigma=\left( \begin{array}{cccc|c} \sigma_1 & & & & \\ & \sigma_2 & & &\mathbb O_{{\mathfrak r}\times (n-{\mathfrak r})}\\ & &\ddots& & \\ & & & \sigma_{\mathfrak r} & \\ & & & & \\ \hline &\mathbb O_{(m-{\mathfrak r})\times {\mathfrak r}} & & & \mathbb O_{(m-{\mathfrak r})\times (n-{\mathfrak r})} \end{array} \right) $$ Числа $ \sigma_1, \sigma_2,\dots,\sigma_{\mathfrak r} $ расположены в порядке неубывания: $$ \sigma_1\ge \sigma_2 \ge \dots \ge \sigma_{\mathfrak r} > 0 $$ и равны арифметическим квадратным корням из ненулевых собственных чисел матрицы $ A \cdot A^{\top} $ $$ \{\sigma_j= |\lambda_j| \}_{j=1}^{\mathfrak r} $$ где $ \lambda_1^2, \lambda_2^2,\dots, \lambda_{\mathfrak r}^2 $ — корни уравнения $$ \det ( A \cdot A^{\top}-\lambda E) =0 \, . $$

$$ V= \left[ V_{[1]}| V_{[2]}|\dots | V_{[m]} \right],\ npu \ ( A \cdot A^{\top}-\lambda_j^2 E) V_{[j]} = \mathbb O_{m\times 1} \, . $$

$$ W= \left[ W_{[1]}|W_{[2]}|\dots | W_{[n]} \right],\ npu \ ( A^{\top} A -\lambda_j^2 E) W_{[j]} = \mathbb O_{n\times 1} \, . $$

Доказательство. Предположим, для определенности, что $ m \le n $. Воспользуемся теоремой $ 1 $ из предыдущего пункта. $$ A=P\Lambda Q \quad npu \ \{P,\Lambda\} \subset \mathbb R^{m\times m}, Q \in \mathbb R^{m\times n} \, . $$ Положим $$ V=P, \Sigma=\left[\Lambda \mid \mathbb O_{m\times (n-m)} \right] , $$ и определим матрицу $ W $ как матрицу вида $$ W=\left[Q^{\top} \mid S^{\top} \right] \, , $$ столбцы которой составляют ортонормированный базис пространства $ \mathbb R^n $. Столбцы матрицы $ Q^{\top} $ уже ортонормированы, поэтому при $ m < n $ можно подобрать столбцы матрицы $ S^{\top} \in \mathbb R^{n\times (n-m)} $ так, чтобы матрица $ W $ стала ортогональной. Очевидно, $$ =V \Sigma W^{\top}=P \left[\Lambda \mid \mathbb O \right] \left[\begin{array}{c} Q \\ S \end{array} \right]=P \Lambda Q = A \, . $$


Диагональные элементы матрицы $ \Sigma=[\sigma_{ij} ]_{i=1,\dots, m; j=1,\dots, n} $, т.е. элементы с одинаковыми индексами $$ \big\{\sigma_1, \sigma_2,\dots,\sigma_{\mathfrak r}, \underbrace{0, \dots, 0}_{\min \{m,n\} - \mathfrak r} \big\} $$ называются сингулярными числами матрицы1) $ A $. Столбцы матрицы $ V $ называют левыми сингулярными векторами, а столбцы матрицы $ W $ — правыми сингулярными векторами матрицы $ A $. Левый и правый сингулярные векторы, соответствующие одному и тому же сингулярному числу $ \sigma_j $, связаны соотношениями $$ A W_{[j]} = \sigma_j V_{[j]}, \ A^{\top} V_{[j]} = \sigma_j W_{[j]} \, . $$ Действительно, если вектор $ W_{[j]} $ является собственным для матрицы $ A^{\top} A $, то, домножив равенство $$ A^{\top} A W_{[j]} =\sigma_j^2 W_{[j]} $$ слева на матрицу $ A $, получим: $$ A\cdot A^{\top} A W_{[j]} =\sigma_j^2 A W_{[j]} \, . $$ Но это равенство означает, что вектор $ A W_{[j]} $ является собственным вектором матрицы $ A\cdot A^{\top} $, соответствующим собственному числу $ \sigma_j^2 $. Представление матрицы $ A $ в виде произведения из теоремы называется сингулярным разложением2) матрицы $ A $.

П

Пример 1. Для симметричной матрицы $ A \in \mathbb R^{n\times n} $ в случае неотрицательности ее собственных чисел сингулярное разложение имеет вид:

$$ A=P \left(\begin{array}{cccc} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots & & \\ & & & \lambda_{\mathfrak n} \end{array} \right) P^{\top} \, , $$ где $ \lambda_1\ge \lambda_2 \ge \dots \ge \lambda_n $ означают собственные числа матрицы $ A $, а матрица $$ P=[\mathfrak X_1 | \mathfrak X_2| \dots | \mathfrak X_n ] $$ имеет столбцами соответствующие этим собственным числам собственные векторы единичной длины3). Фактически, это утверждение — следствие теоремы о приводимости симметричной матрицы к диагональному виду с помощью ортогональной матрицы.

П

Пример 2. Для произвольной симметричной матрицы $ A \in \mathbb R^{n\times n} $ результат предыдущего примера слегка модифицируется. Из представления, полученного в том примере:

$$ A=[\mathfrak X_1 | \mathfrak X_2| \dots | \mathfrak X_n ]\left(\begin{array}{cccc} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots & & \\ & & & \lambda_{\mathfrak n} \end{array} \right) [\mathfrak X_1 | \mathfrak X_2| \dots | \mathfrak X_n ]^{\top} \ , $$ в котором собственные числа $ \lambda_1,\lambda_2,\dots,\lambda_n $ занумерованы теперь по убыванию модулей, делаем сингулярное разложение в виде $$ = [\mathfrak X_1 | \mathfrak X_2| \dots | \mathfrak X_n ]\left(\begin{array}{cccc} |\lambda_1| & & & \\ & |\lambda_2| & & \\ & & \ddots & & \\ & & & |\lambda_{\mathfrak n}| \end{array} \right) [\operatorname{sign}(\lambda_1) \mathfrak X_1 | \operatorname{sign}(\lambda_2)\mathfrak X_2| \dots | \operatorname{sign}(\lambda_n)\mathfrak X_n ]^{\top} \, . $$ Ортогональность крайних матриц сохраняется. Так, для матрицы $$ A=\left(\begin{array}{cccc} 1 & 2 & 3 & 2 \\ 2 & 1 & 2 & 3 \\ 3 & 2 & 1 & 2 \\ 2 & 3 & 2 & 1 \end{array}\right) $$ ее спектром является набор $ \{8,-2,-2,0\} $. Матрица $$ P=\left(\begin{array}{rrrr} 1/2 & 1/\sqrt{2} & 0 & 1/2 \\ 1/2 & 0 & 1/\sqrt{2} & -1/2 \\ 1/2& -1/\sqrt{2}& 0 & 1/2 \\ 1/2& 0& -1/\sqrt{2} &-1/2 \end{array}\right) \, , $$ столбцами которой являются собственные векторы матрицы $ A $ (упорядоченные в соответствии с указанным выше порядком собственных чисел), приводит матрицу $ A $ к диагональному виду: $$P^{\top}AP= \left(\begin{array}{cccc} 8 & & & \\ & -2 & & \\ & & -2 & \\ & & & 0 \end{array}\right) \, . $$ Тогда сингулярное разложение матрицы $ A $ имеет вид: $$ A=P \left(\begin{array}{cccc} 8 & & & \\ & +2 & & \\ & & +2 & \\ & & & 0 \end{array}\right) \left(\begin{array}{rrrr} 1/2 & -1/\sqrt{2} & 0 & 1/2 \\ 1/2 & 0 & -1/\sqrt{2} & -1/2 \\ 1/2& 1/\sqrt{2}& 0 & 1/2 \\ 1/2& 0& 1/\sqrt{2} &-1/2 \end{array}\right)^{\top} \, . $$

П

Пример 3. Для произвольной квадратной матрицы $ A \in \mathbb R^{n\times n} $ связь ее собственных чисел с сингулярными становится непрозрачной. Характеристический полином матрицы

$$ A= \left(\begin{array}{rrr} 7 & 2 & -5 \\ -9 & 8 & -5 \\ 24 & -6 & 8 \end{array} \right) $$ равен $$ -\lambda^3+23\,\lambda^2-284\, \lambda+832 \, , $$ и он имеет корни $$ \mu_1=4, \mu_{2,3} = \frac{19}{2} \pm \frac{\sqrt{471}}{2} \mathbf{i} \approx 9.5\pm 10.851267 \mathbf{i} \, . $$ Характеристические полиномы матриц $$ A \cdot A^{\top}= \left(\begin{array}{rrr} 78 & -22 & 116 \\ -22 & 170 & -304 \\ 116 & -304 & 676 \end{array} \right) \quad u \quad A^{\top}A = \left(\begin{array}{rrr} 706 & -202 & 202 \\ -202 & 104 & -98 \\ 202 & -98 & 114 \end{array} \right) $$ идентичны и равны $$ -\lambda^3-924\, \lambda^2+74552\, \lambda -692224 \, . $$ Корни полинома третьей степени можно выразить в радикалах от его коэффициентов, но эти формулы слишком громоздки. Поэтому находим приближенные их значения (например, по методу Ньютона): $$ \lambda_1^2 \approx 835.791687,\ \lambda_2^2 \approx 77.524974, \ \lambda_3^2 \approx 10.683338 \, . $$ Для поиска же сингулярных векторов матрицы $ A $ применяем процедуру, изложенную ЗДЕСЬ. Строим матрицу, взаимную матрице $ A \cdot A^{\top} - \lambda E $, впрочем, нам достаточно знания одного ее столбца, например, первого: $$ \left(\begin{array}{ccc} \lambda^2-846\, \lambda +22504 & \ast & \ast \\ -22\, \lambda -20392 & \ast & \ast \\ 116\, \lambda-13032 & \ast & \ast \end{array} \right) \, . $$ Подстановка в этот столбец любого из $ \lambda_1^2, \lambda_2^2,\lambda_3^2 $ даст величину соответствующего собственного вектора матрицы $ A \cdot A^{\top} $: $$ \approx \left(\begin{array}{r} 13971.977125 \\ -38779.417121 \\ 83919.835730 \end{array} \right), \ \approx \left(\begin{array}{r} -37072.006810 \\ -22097.549441 \\ -4039.102949 \end{array} \right), \ \approx \left(\begin{array}{r} 13580.029684 \\ -20627.033438 \\ -11792.732781 \end{array} \right) . $$ Эти векторы попарно ортогональны, но не нормированы. Нормируем их, и составим из полученных столбцов ортогональную матрицу: $$ V \approx \left( \begin{array}{rrr} 0.149438 & -0.855241 & 0.496217 \\ -0.414768 & -0.509784 & -0.753715\\ 0.897572 & -0.093181 & -0.430908 \end{array} \right) \, . $$ Один из сомножителей сингулярного разложения получен. Получение другого сомножителя — матрицы $ W $, столбцами которой являются собственные векторы матрицы $ A^{\top} A $, возможно тем же способом: построением матрицы, взаимной матрице $ A^{\top} A - \lambda E $: $$ \left(\begin{array}{ccc} \lambda^2-218\, \lambda +2252 & \ast & \ast \\ -202\, \lambda+ 3232 & \ast & \ast \\ 202\, \lambda-1212 & \ast & \ast \end{array} \right) \, . $$

Тем не менее, отработанная процедура потребует модификации. Дело в том, что каждому собственному числу матрицы $ A^{\top} A $ соответствует два нормированных собственных вектора, различающиеся направлением. Так, к примеру, числу $ \lambda_1^2 $ соответствуют векторы $$ \approx \pm [ 0.910434, -0.290719, 0.294265 ]^{\top} \, . $$ Какой из них взять первым столбцом матрицы $ W $? Напомним, что для левый и правый сингулярные векторы матрицы должны быть согласованными соотношением $ A^{\top} V_{[j]} = \sigma_j W_{[j]} $. Фактически, его можно было бы использовать для нахождения вектора $ W_{[j]} $ по уже найденному $ V_{[j]} $, и не связываться с дорогостоящей процедурой вычисления взаимной матрицы. Окончательно: $$ W\approx \left( \begin{array}{rrr} 0.910434 & -0.412838 & -0.025959 \\ -0.290719 & -0.593955 & -0.750133\\ 0.294265 & 0.690494 & -0.660777 \end{array} \right) \quad u \quad \Sigma \approx \left( \begin{array}{rrr} 28.910062 & & \\ & 8.804827 & \\ & & 3.268538 \end{array} \right) . $$ Проверка. $$ V \Sigma W^{\top} \approx \left( \begin{array}{rrr} 6.999983 & 2.000003 & -5.000007 \\ -8.999986 & 7.999992 & -4.999991\\ 23.999998 & -6.000005 & 7.999995 \end{array} \right) \, . $$

?

Пусть сингулярное разложение матрицы $ A \in \mathbb R^{n\times n} $ известно. Какое условие надо наложить на сингулярные числа матрицы, чтобы она была обратимой? Как в этом случае найти сингулярное разложение $ A^{-1} $?

П

Пример 4. Пусть теперь матрица $ A $ не является квадратной:

$$ A=\left( \begin{array}{rrr} 1 & -1 & -2 \\ -7/3 & 1/3 & 2/3\\ 1/3 & -7/3 & -2/3 \\ -5/3 & 5/3 & -2/3 \end{array} \right) \, . $$ Для такой матрицы понятие собственного числа отсутствует. Имеем: $$ A\cdot A^{\top}= \left( \begin{array}{rrrr} 6 & -4 & 4 & -2 \\ -4 & 6 & -2 & 4\\ 4 & -2 & 6 & -4 \\ -2 & 4 & -4 & 6 \end{array} \right),\ A^{\top} A = \left( \begin{array}{rrr} 28/3 & -16/3 & -8/3 \\ -16/3 & 28/3 & 8/3\\ -8/3 & 8/3 & 16/3 \end{array} \right) $$ и характеристические полиномы эти матриц равны соответственно $$ \lambda (\lambda-16)(\lambda-4)^2 \quad u \quad -(\lambda-16)(\lambda-4)^2 \, . $$ Следовательно сингулярными числами матрицы $ A $ являются $ \sigma_1=4,\sigma_2=2,\sigma_3=2 $, а $$ \Sigma =\left( \begin{array}{rrr} 4 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \\ 0 & 0 & 0 \end{array} \right) \, . $$ Ищем ортонормированные собственные векторы матрицы $ A^{\top} A $. Матрица, взаимная матрице $ A \cdot A^{\top} - \lambda E $ имеет структуру $$ \left( \begin{array}{crr} (\lambda-32/3)(\lambda-4) & * & * \\ 16/3(4-\lambda) & * & * \\ 8/3(4-\lambda) & * & * \end{array} \right) $$ При $ \lambda=16 $ первый столбец дает величину собственного вектора в виде $ [64,-64,-32]^{\top} $, который после нормирования становится равным $ [2/3,-2/3,-1/3]^{\top} $ . Однако при значении кратного корня $ \lambda = 4 $ столбец вырождается в нулевой, т.е. поиск двух линейно независимых собственных векторов посредством взаимной матрицы принципиально неразрешим. На помощь приходит минимальный аннулирующий полином матрицы $ A^{\top} A $. Таким является $ (\lambda-16)(\lambda-4) $. Матрица $$ A^{\top} A - 16 E= \left( \begin{array}{rrr} -20/3 & -16/3 & -8/3 \\ -16/3 & -20/3 & 8/3 \\ -8/3 & 8/3 & -32/3 \end{array} \right) $$ имеет ранг равный $ 2 $, и любая пара ее столбцов будет линейно независимой системой собственных векторов матрицы, принадлежащих собственному числу $ \lambda=4 $. Возьмем, например, второй и третий столбцы и проведем с ними процедуру ортогонализации Грама-Шмидта. Получим столбцы $$ [-16/3,-20/3, 8/3]^{\top} \ ; \ [-12,0,-24]^{\top} \, . $$ Нормируя все полученные столбцы, составим ортогональную матрицу $$ W= \left( \begin{array}{rrr} 2/3& -4/(3\sqrt{5}) &1/\sqrt{5}\\ -2/3 & -\sqrt{5}/3 & 0 \\ -1/3 & 2/(3\sqrt{5}) & 2/\sqrt{5} \end{array} \right) \, . $$ Нахождение левых сингулярных векторов производится с помощью формулы $ V_{[j]}= 1/\sigma_j A W_{[j]} $: $$ V_{[1]}=\left[\frac{1}{2},-\frac{1}{2},\frac{1}{2},-\frac{1}{2}\right]^{\top},\ V_{[2]}=\left[-\frac{1}{2\sqrt{5}},\frac{3}{2\sqrt{5}},\frac{3}{2\sqrt{5}},-\frac{1}{2\sqrt{5}}\right]^{\top},\ V_{[3]}=\left[-\frac{3}{2\sqrt{5}},-\frac{1}{2\sqrt{5}},-\frac{1}{2\sqrt{5}},-\frac{3}{2\sqrt{5}}\right]^{\top} \, . $$ Но матрица $ V $ должна быть квадратной! А у нас получилось только $ 3 $ вектора порядка $ 4 \times 1 $. Четвертый столбец выбираем так, чтобы он был ортогонален всем уже построенным: $$ V_{[4]}=\left[\frac{1}{2},\frac{1}{2},-\frac{1}{2},-\frac{1}{2}\right]^{\top} \, . $$ Можно взять и противоположный вектор. Окончательно: $$ V= \left( \begin{array}{rrrr} \frac{1}{2} & -\frac{1}{2\sqrt{5}} & -\frac{3}{2\sqrt{5}} & \frac{1}{2} \\ -\frac{1}{2} & \frac{3}{2\sqrt{5}} & -\frac{1}{2\sqrt{5}} & \frac{1}{2}\\ \frac{1}{2} & \frac{3}{2\sqrt{5}} & -\frac{1}{2\sqrt{5}} & -\frac{1}{2} \\ -\frac{1}{2} & -\frac{1}{2\sqrt{5}} & -\frac{3}{2\sqrt{5}} & -\frac{1}{2} \end{array} \right) \, . $$

§

Единственность сингулярного разложения матрицы не гарантирована. Однозначно определена только матрица $ \Sigma $ (при условии упорядочения сингулярных чисел по убыванию). Так, в предыдущем примере ответом являются также матрицы

$$ V=\frac{1}{2} \left( \begin{array}{rrrr} 1 & 1 & 1 & 1 \\ -1 & 1 &-1 & 1 \\ 1 & 1 & -1 & -1 \\ -1 & 1 & 1 & -1 \end{array} \right) , \quad W=\frac{1}{3} \left( \begin{array}{rrr} 2& -2 &1\\ -2 & -1 & 2 \\ -1 & -2 & -2 \end{array} \right) \, . $$

=>

Для матрицы $ A \in \mathbb R^{m\times n} $, $ \operatorname{rank} (A)=\mathfrak r>0 $ ее сингулярное разложение означает представление ее в виде суммы $ \mathfrak r $ матриц ранга 1: $$ A=\sum_{j=1}^{\mathfrak r} \sigma_j V_{[j]} W_{[j]}^{\top} \, . $$

Так, матрицу из последнего примера можно представить в виде суммы: $$ \left( \begin{array}{rrr} 1 & -1 & -2 \\ -7/3 & 1/3 & 2/3\\ 1/3 & -7/3 & -2/3 \\ -5/3 & 5/3 & -2/3 \end{array} \right)= $$ $$ = 4 \left( \begin{array}{rrr} 1/3 & -1/3 & -1/6 \\ -1/3 & 1/3 & 1/6 \\ 1/3 & -1/3 & -1/6 \\ -1/3 & 1/3 & 1/6 \end{array} \right)+2 \left( \begin{array}{rrr} -1/3 & -1/6 & -1/3 \\ -1/3 & -1/6 & -1/3 \\ -1/3 & -1/6 & -1/3 \\ -1/3 & -1/6 & -1/3 \end{array} \right) + 2 \left( \begin{array}{rrr} 1/6 & 1/3 & -1/3 \\ -1/6 & -1/3 & 1/3 \\ -1/6 & -1/3 & 1/3 \\ 1/6 & 1/3 & -1/3 \end{array} \right) \, . $$ Впрочем, на практике экономнее хранить не матрицы с фактически одинаковыми строками (столбцами), а именно их представления в виде произведений столбцов $ V_{[j]} W_{[j]}^{\top} $.


Из последнего представления сингулярного разложения следует также, что в нем участвуют только те столбцы матриц $ V $ и $ W $ которые соответствуют ненулевым сингулярным числам матрицы $ A $. Фактически для любой матрицы $ A $ порядка $ m \times n $ ее сингулярное разложение в виде суммы матриц ранга $ 1 $ будет содержать не более $ \min \{ m, n\} $ слагаемых. Этот вывод приводит к альтернативной матричной форме сингулярного разложения: $$ A=\widetilde V \widetilde \Sigma \widetilde W^{\top} \, . $$ Здесь матрица $ \widetilde \Sigma $ теперь квадратная и диагональная, а матрицы $ \widetilde V $ и $ \widetilde W $ теперь не обязательно квадратные. Они получаются из матриц $ V $ и $ W $ отбрасыванием их последних (после $ \mathfrak r $-го) столбцов. Для случая $ m>n=\mathfrak r $ структура произведения отражена на схеме

Приложения

?

Показать, что евклидова норма (норма Фробениуса) матрицы $ A $ равна арифметическому корню из суммы квадратов ее сингулярных чисел: $$ ||A|| = \sqrt{\sum_{j,k} a_{jk}^2} =\sqrt{\sum_{j=1}^{\mathfrak r} \sigma_j^2} \, . $$

Решение. Если воспользоваться представлением нормы матрицы с помощью следа $$ ||A|| = \sqrt{\operatorname{Sp}(A \cdot A^{\top})} \, , $$ то требуемый результат вытекает из структуры спектров матриц $ A \cdot A^{\top} $ и $ A^{\top} A $ (см. свойство 4 ЗДЕСЬ и теорему 1 ЗДЕСЬ).

Приведем отдельное доказательство, рассчитывая применить его идею в дальнейшем. Подставим вместо $ A $ сингулярное представление: $$ =\sqrt{\operatorname{Sp}\left[V\Sigma W^{\top} \cdot (V\Sigma W^{\top})^{\top}\right]}=\sqrt{\operatorname{Sp} \left[V\Sigma W^{\top} \cdot W \Sigma^{\top} V^{\top}\right]} $$ (при транспонировании произведения сомножители переставляются местами и транспонируются); $$ =\sqrt{\operatorname{Sp} \left[V\Sigma \cdot \Sigma^{\top} V^{\top}\right]} $$ (матрица $ W $ — ортогональная); $$ =\sqrt{\operatorname{Sp} \left[\Sigma \cdot \Sigma^{\top} V^{\top}V\right]} $$ (под знаком следа сомножители можно переставлять местами: $ \operatorname{Sp}(A_1A_2)=\operatorname{Sp}(A_2A_1) $); $$ =\sqrt{\operatorname{Sp} \left[\Sigma \cdot \Sigma^{\top}\right]} $$ (матрица $ V $ — ортогональная). В квадратной матрице $ \Sigma \cdot \Sigma^{\top} $ все ненулевые элементы оказываются на главной диагонали: $$ \Sigma \cdot \Sigma^{\top}=\left(\begin{array}{ccccc} \sigma_1^2 & & & & \\ & \sigma_2^2 & & & \\ & & \ddots & & \\ & & & \sigma_{\mathfrak r}^2 & \\ & & & & \end{array} \right)_{m\times m} $$

Т

Теорема. Пусть матрица $ A \in \mathbb R^{m\times n} $ имеет ранг $ \mathfrak r>0 $. Матрицей $ \widetilde A \in \mathbb R^{m\times n} $ ранга $ k , 0<k < \mathfrak r $, наилучшим образом приближающей $ A $ в евклидовой норме:

$$ \min_{\widetilde A\in \mathbb R^{m\times n}, \operatorname{rank} (\widetilde A)= k} || A- \widetilde A|| \, , $$ является матрица $$ A_k=\sum_{j=1}^{k} \sigma_j V_{[j]} W_{[j]}^{\top} \, . $$ Иными словами $$ A_k= V \Sigma_k W^{\top} $$ где матрицы $ V $ и $ W $ — из сингулярного разложения матрицы $ A $, а $$ \Sigma_k =\left( \begin{array}{cccc|c} \sigma_1 & & & & \\ & \sigma_2 & & &\mathbb O_{k\times (n-k)}\\ & &\ddots& & \\ & & & \sigma_k & \\ & & & & \\ \hline &\mathbb O_{(m-k)\times k} & & & \mathbb O_{(m-k)\times (n-k)} \end{array} \right) $$ т.е. имеет на диагонали $ k $ наибольших по величине сингулярных чисел матрицы $ A $, а все остальные элементы — нулевыми. При такой матрице $ \widetilde A $ величина указанного минимума равна $$ \sqrt{\sum_{j=k+1}^{\mathfrak r} \sigma_j^2} \, . $$

Доказательство ЗДЕСЬ.

П

Пример 5. Для матрицы $$ A= \left( \begin{array}{rrrr} -29 & 95 & 11 & -49 \\ -47 & 40 &-81 & 91 \\ 68 & -10 & 31 & -51 \\ 77 & 95 & -56 & 1 \end{array} \right) $$ найти ближайшую к ней вырожденную матрицу.

Решение. Согласно теореме, речь идет о нахождении матрицы $ A_3 $ ранга $ 3 $, ближайшей к матрице $ A $. С помощью подхода из предыдущего пункта находим сингулярное разложение: $$ A \approx \left( \begin{array}{rrrr} -0.182542 &-0.483712 & -0.840358 & -0.162785 \\ -0.781558 & 0.321665 & 0.086784 & -0.527416 \\ 0.394451 & -0.394342 & 0.291816 & -0.777011 \\ -0.447497 & -.7120736 & 0.448453 & 0.302634 \end{array} \right) \times $$ $$ \times \left( \begin{array}{rrrr} 163.660469 & & & \\ & 146.509667 & & \\ & & 95.739999 & \\ & & & \color{Red}{0.145034} \end{array} \right) \times $$ $$ \times \left( \begin{array}{rrrr} 0.210144 & -0.564711 & 0.779882 & -0.169486 \\ -0.580840 & -0.660636 & -0.3830988 & -0.281816 \\ 0.602382 & -0.025419 & -0.337795 & -0.722762 \\ -0.505569 & 0.493980 & 0.361821 & -0.607840 \end{array} \right)^{\top} \, . $$ Удаляем из матрицы $ \Sigma $ минимальное сингулярное число (выделено красным). Результатом умножения становится матрица $$ A_3=V \widetilde \Sigma W^{\top} \approx \left( \begin{array}{rrrr} -29.004001 & 94.993346 & 10.982936 & -49.014351 \\ -47.012965 & 39.978443 & -81.055286 & 90.953504 \\ 67.980900 & -10.031759 & 30.918550 & -51.068499 \\ 77.007439 & 95.012369 & -55.968276 & 1.026679 \end{array} \right) \, . $$ с определителем $ \approx -0.160086 $. Фактически погрешность в представлении элементов матрицы в $ 0.1 $ может превратить ее (с $ \det (A)=332945 $) в особенную!

Проверка. В евклидовом $ 16 $-мерном пространстве матриц четвертого порядка со скалярням произведением, определяемым по правилу $ \langle A,B \rangle=\sum_{i,j=1}^4 a_{ij}b_{ij} $, подмножество вырожденных матриц образует некоторое алгебраическое многообразие, задаваемое нелинейным уравнением $ \det B = 0 $. Можно утверждать, что экстремумы функции расстояния до этого многообразия от данной матрицы $ A $ достигаются на матрице $ \widetilde A $ такой, что матрица $ A- \widetilde A $ ортогональна этому многообразию в «точке» $ \widetilde A $. Иначе говоря, градиент функции $ \det $, вычисленный в точке $ \widetilde A $ и представленный в виде матрицы, состоящей из алгебраических дополнений к элементам матрицы $ \widetilde A $, должен быть коллинеарен $ A- \widetilde A $. Эти две матрицы должны различаться лишь скалярным множителем. Для матрицы $ \widetilde A= A_3 $ это свойство выполняется.

?

Найти вырожденные матрицы, ближайшие к матрицам $$ \left(\begin{array}{rr} 1 & -3 \\ 3 & -1 \end{array} \right) \quad u \quad \left(\begin{array}{rr} 1 & -6 \\ 3 & 2 \end{array} \right) \, . $$

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

П

Пример 6. Для передачи матрицы

$$ A= \left( \begin{array}{rrrrrrrrrr} 72&-24&0&569&356&-63&278&-404&464&-148&497&425\\ 301&337& -335 & -41 & 78 & -308 & 414 & 321 & -362 & 394 & 337 & 325\\ 215& -191 & -243 & 563 & 327 & 264 & 426 & -65 & 264 & -240 & 738 & 425\\ -168& -79 & 136 & -389 & -263 & 111 & -323 & 149 & -197 & -6 & -483 &-398\\ 74 & 96 & -83 & -214 & -216 & -10 & -207 & 196 & -184 & 42 & -141 & -174\\ -70 & -290 & 104 & 26 & -302 & 453 & -664 & -111 & 307 & -542 & -207 & -439\\ 434 & 443& -248& 670 & 184 & -433 & 11 & -420 & 536 & -73 & 714 &540\\ -61 & 105 & 172 & 118 & -39 & -172 & -308 & -349 & 325 & -108 &-129 &-48\\ -255 & 78 & 251 & -260 & 71 & -273 & 133 & -73 & -160 & 311 & -386 & -34\\ -297 & -275 & 225 & -423 & -233 & 292 & -289 & 155 & -203 & -84 & -573 & -480 \end{array} \right)_{10\times 12} $$ по каналу связи требуется переслать $ 120 $ ее элементов. Попробуем уменьшить это количество за счет предварительного сингулярного разложения матрицы. Имеем $$ A \approx 2700.156919 \left( \begin{array}{r} -0.390369\\ -0.193164 \\ -0.412283 \\ 0.337413 \\ 0.140855 \\ 0.222348 \\ -0.524734 \\ 0.001110\\ 0.131021 \\ 0.405810 \end{array} \right) \left(\begin{array}{r} -0.229044 \\ -0.143812 \\ 0.176558 \\ -0.429270 \\ -0.243324 \\ 0.156198 \\ -0.279937 \\ 0.166302 \\ -0.232733 \\ 0.003274 \\ -0.537057 \\ -0.423297 \end{array} \right)^{\top} + 1599.933523 \left( \begin{array}{r} 0.240669 \\ -0.572289 \\0.171253 \\ 0.011588 \\ -0.095070 \\ 0.637038 \\ 0.160932 \\ 0.269379 \\ -0.250291 \\0.095578 \end{array} \right) \left(\begin{array}{r} -0.051775 \\ -0.232734 \\ 0.119333 \\ 0.283435\\ -0.061748 \\ 0.298356 \\ -0.403913\\ -0.317640\\ 0.480821\\ -0.486426 \\ 0.031925 \\ -0.151288 \end{array} \right)^{\top} $$ $$ + 999.456577 V_{[3]} W_{[3}^{\top} + 799.790045 V_{[4]} W_{[4]}^{\top} + $$ $$ +{\color{Red}{2.945378}} V_{[5]} W_{[5]}^{\top} + {\color{Red}{2.305654}} V_{[6]} W_{[6]}^{\top} + {\color{Red}{2.087323}} V_{[7]} W_{[7]}^{\top} + {\color{Red}{1.898662}} V_{[8]} W_{[8]}^{\top} + {\color{Red}{1.235953}} V_{[9]} W_{[9]}^{\top}+ {\color{Red}{0.539705}} V_{[10]} W_{[10]}^{\top} \, . $$ Если отбросить в этом разложении все слагаемые, соответствующие $ 6 $ минимальным сингулярным значениям (обозначены красным), то получим приближение матрицы $ A $ в виде матрицы ранга $ 4 $: $$ A_4 \approx \left( \begin{array}{rrrrrrrrrr} 71.26 & -23.70 & -0.53 & 568.70 & 356.77 & -62.66 & 277.37 & -403.65 & 464.44 & -147.54 & 497.19 & 425.11 \\ \dots & & & &&&&&&&& \dots \end{array} \right) $$ Эта матрица отличается от $ A $. Однако, последняя «узнаваема» из $ A_4 $. Если в ходе корреспонденции предполагается, что отправляемая матрица имеет только целочисленные элементы, то при получении матрицы $ A_4 $ мы вправе округлить ее элементы до ближайшего целого. Сделав это, увидим, что в $ 88 $ элементах из $ 120 $ ошибок не будет, а оставшиеся имеют ошибку в последней цифре в пределах $ 1 $ по абсолютной величине.

Но тогда, в предположении, что такая погрешность допустима для нашей цели, имеет смысл пересылать именно матрицу $ A_4 $, потому что это позволит сэкономить на количестве пересылаемых элементов. В самом деле, правая часть равенства $$ A_4=\sigma_1 V_{[1]} W_{[1]}^{\top} + \sigma_2 V_{[2]} W_{[2]}^{\top}+ \sigma_3 V_{[3]} W_{[3]}^{\top}+\sigma_4 V_{[4]} W_{[4]}^{\top} $$ включает в себя $$ 4(1+10+12) = 88 $$ элементов (координат векторов $ V_{[j]}, W_{[j]} $ и сингулярных чисел). Таким образом, добиваемся $ \approx 30 \% $ экономии в количестве пересылаемого по сравнению с пересылкой всех элементов матрицы $ A $.

Использованный в предыдущем примере трюк и составляет основную идею, лежащую в основе практических приложений сингулярного разложения. Сохранить только те слагаемые в разложении, что отвечают за требуемую точность и отбросить все остальные. Как определить что еще можно отбрасывать, а что — уже нет? — Для ответа на этот вопрос у нас есть оценка из теоремы начала пункта: $$ ||A- A_4 ||=\sqrt{\sigma_5^2+\sigma_6^2+ \dots + \sigma_{10}^2 }\approx 4.875652 \, . $$ Евклидова норма сразу же дает точную верхнюю грань для величины ошибки каждого элемента: $$ |a_{jk} - a_{jk}^{[4]}| \le \sqrt{6} \sigma_5 \, . $$ Вместе с тем, совершенно невероятно, чтобы эта ошибка обеспечивалась малым количеством элементов; более правдоподобно, что эта ошибка является кумулятивным эффектом малых возмущений всех (или достаточно большого числа из) $ 120 $ элементов. Именно это и случилось в рассмотренном примере.

Вычислительные аспекты

Изложенная в примерах ПУНКТА схема нахождения сингулярного разложения имеет исключительно теоретическое значение. При больших порядках матрицы, уже проблема вычисления ее характеристического полинома весьма ресурсозатратна, а также чувствительна к ошибкам представления элементов: см. ЗДЕСЬ. Выручает то обстоятельство, что практические приложения сингулярного разложения не требуют знания всех сингулярных чисел, а только лишь наибольших из них в количестве, существенно меньшем порядка матрицы. Для этой же задачи можно привлечь методы линейной алгебры, применяемые в так называемой, частичной проблеме собственных чисел. Например, максимальное по модулю собственное число матрицы $ B \in \mathbb C^{n\times n} $, как правило, может быть получено из последовательности $$ Y_1=B\cdot Y_0,\ Y_2=B\cdot Y_1, \dots,\ Y_{K}=B\cdot Y_{K-1},\dots , $$ при практически любом стартовом столбце $ Y_0 \in \mathbb C^n, Y_0 \ne \mathbb O $, как предел отношения первых4) элементов этих векторов: $$ \lim_{K\to +\infty}\frac{y_{1}^{[K+1]}}{y_{1}^{[K]}} \ . $$ Соответствующий собственный вектор может быть выражен с помощью предельного перехода в последовательности $ \{Y_K /|Y_K|\}_{K=0}^{\infty} $.

Для симметричных матриц (с которыми и приходится иметь дело в сингулярном разложении) метод обобщается ЗДЕСЬ для поиска $ s $-го по убыванию модуля собственного числа $ \lambda_s $ $$ |\lambda_1|>|\lambda_2|>\dots>|\lambda_{s-1}|>|\lambda_{s}| $$ в предположении, что все собственные числа $ \lambda_1,\lambda_2,\dots,\lambda_{s-1} $ и соответствующие им собственные векторы уже вычислены.

Если все же требуется построить полное сингулярное разложение, т.е. найти все сингулярные числа матрицы, то можно воспользоваться QR-алгоритмом.

.

Задачи

ЗДЕСЬ.

Источники

Хорн Р., Джонсон Ч. Матричный анализ. М.Мир.1989

1)
Часто к сингулярным относят только положительные из указанных чисел.
2)
(англ.) Singular Value Decomposition, SVD
3)
Причем векторы, принадлежащие различным собственным числам, будут ортогональными автоматически, а принадлежащие кратному собственному числу можно ортогонализовать.
4)
Вообще говоря, не обязательно первых, а произвольных фиксированных
algebra2/svd.txt · Последние изменения: 2020/10/16 17:49 — au