УказательРазделыОбозначенияАвторО проекте


§

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


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

!

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

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

о матрицах 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 определена однозначно: 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:

Здесь

\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) Вообще говоря, не обязательно первых, а произвольных фиксированных

2018/05/09 16:01 редактировал au