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


§

Вспомогательный раздел к разделу СИНГУЛЯРНОЕ РАЗЛОЖЕНИЕ МАТРИЦЫ


Т

Теорема. Пусть матрица A \in \mathbb R^{m\times n} ранга \mathfrak r>0 имеет сингулярное разложение вида

A= V \Sigma W^{\top} \quad npu \quad \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) \, .

Матрицей ранга {\color{Red}{k}} , 0< {\color{Red}{k}} < \mathfrak r, наилучшим образом приближающей A в евклидовой норме:

\min_{\widetilde A\in \mathbb R^{m\times n}, \operatorname{rank} (\widetilde A)= k} || A- \widetilde A|| \, ,

является матрица

A_k= V \Sigma_k W^{\top}

где

\Sigma_k =\left( \begin{array}{cccc|c} \sigma_1 & & & & \\ & \sigma_2 & & &\mathbb O_{k\times (n-k)}\\ & &\ddots& & \\ & & & \sigma_{\color{Red}{k}} & \\ & & & & \\ \hline &\mathbb O_{(m-k)\times k} & & & \mathbb O_{(m-k)\times (n-k)} \end{array} \right)

т.е. имеет на диагонали k наибольших по величине и упорядоченных по убыванию сингулярных чисел матрицы A, а все остальные элементы — нулевыми. При такой матрице A_k величина указанного минимума равна

\sqrt{\sum_{j=k+1}^{\mathfrak r} \sigma_j^2} \, .

Доказательство существенно основывается на утверждении, что евклидова норма матрицы не меняется при ее домножении на ортогональную. Из этого, в частности, следует, что указанная в формулировке теоремы величина минимума на матрице A_k достигается:

\|A-A_k \|=\| V (\Sigma-\Sigma_k) W^{\top} \| = \| \Sigma-\Sigma_k \| = \sqrt{ \sigma_{k+1}^2 + \dots + \sigma_{\mathfrak r}^2 } \, .

Докажем теперь, что ни для какой другой матрицы \widetilde A_k ранга k < \mathfrak r разность \|A- \widetilde A_k \| не может быть меньшей \|A- A_k \|. Пусть на некоторой матрице \widetilde A_k достигается минимум разности, и при этом ее сингулярное разложение имеет вид

\widetilde A_k = \widetilde V \widetilde \Sigma_k \widetilde W^{\top}

при

\widetilde \Sigma_k= \left( \begin{array}{ll} \widetilde S_{k \times k} & \mathbb O_{k \times (n - k) } \\ \mathbb O_{(m-k) \times k} & \mathbb O_{(m-k) \times (n -k) } \end{array} \right) \quad u \quad \widetilde S= \left(\begin{array}{cccc} \widetilde \sigma_1 & 0 & \dots & 0 \\ 0 & \widetilde \sigma_2 & \dots & 0 \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \dots & \widetilde \sigma_k \end{array}\right)

— диагональной матрице сингулярных чисел матрицы \widetilde A_k.

Матрица

\widetilde V^{\top} A \widetilde W

имеет блочную структуру

\left( \begin{array}{ll} H_{k \times k} & L_{k \times (n - k) } \\ M_{(m-k) \times k} & N_{(m-k) \times (n -k) } \end{array} \right) \, .

Если при этом L\ne \mathbb O, то матрица

\widetilde A= \widetilde V \left( \begin{array}{ll} \widetilde S & L\\ \mathbb O_{(m-k) \times k} & \mathbb O_{(m-k) \times (n -k) } \end{array} \right) \widetilde W^{\top}

имеет ранг k, но при этом обеспечивает меньшую величину для нормы разности

\left\|A- \widetilde A \right\|= \left\|A- \widetilde V \left( \begin{array}{ll} \widetilde S & L\\ \mathbb O_{(m-k) \times k} & \mathbb O_{(m-k) \times (n -k) } \end{array} \right) \widetilde W^{\top} \right\| =
= \left\| \widetilde V \left( \begin{array}{ll} H & L \\ M& N \end{array} \right) \widetilde W^{\top} - \widetilde V \left( \begin{array}{ll} \widetilde S & L\\ \mathbb O_{(m-k) \times k} & \mathbb O_{(m-k) \times (n -k) } \end{array} \right) \widetilde W^{\top} \right\|=\left\| \left( \begin{array}{cl} H-\widetilde S & \mathbb O\\ M & N \end{array} \right) \right\| ,

нежели матрица \widetilde A_k. Противоречие доказывает, что L= \mathbb O. Аналогично доказывается, что M=\mathbb O. Таким образом имеем:

A=\widetilde V \left( \begin{array}{ll} H & \mathbb O \\ \mathbb O & N \end{array} \right) \widetilde W^{\top} \, .

Если при этом H \ne \widetilde S, то матрица

\widetilde A= \widetilde V \left( \begin{array}{ll} H & \mathbb O \\ \mathbb O & \mathbb O \end{array} \right) \widetilde W^{\top}

ранга k обеспечивает меньшую величину для нормы разности \left\|A- \widetilde A \right\| нежели матрица \widetilde A_k. Следовательно H = \widetilde S.

Матрица

\widetilde \Sigma_k= \left( \begin{array}{ll} \widetilde S_{k\times k} & \mathbb O_{k \times (n - k) } \\ \mathbb O_{(m-k) \times k} & \mathbb O_{(m-k) \times (n -k) } \end{array} \right)

не изменится, если мы умножим ее слева на матрицу

\widetilde P_{m \times m} =\left( \begin{array}{ll} E_{k\times k} & \mathbb O_{k \times (m - k) } \\ \mathbb O_{(m-k) \times k} & P^{\top}_{(m-k) \times (m -k) } \end{array} \right) \ ;

и справа на матрицу

\widetilde Q_{n \times n} = \left( \begin{array}{ll} E_{k\times k} & \mathbb O_{k \times (n - k) } \\ \mathbb O_{(n-k) \times k} & Q_{(n-k) \times (n -k) } \end{array} \right) \ ;

здесь E — единичная матрица, а P и Q — произвольные ортогональные матрицы соответствующих порядков. Очевидно, что \widetilde P и \widetilde Q — ортогональные матрицы.

\widetilde P \left( \begin{array}{ll} H & L \\ M & N \end{array} \right) \widetilde Q= \left( \begin{array}{ll} E & \mathbb O \\ \mathbb O & P^{\top} \end{array} \right) \left( \begin{array}{ll} \widetilde S & \mathbb O \\ \mathbb O & N \end{array} \right) \left( \begin{array}{ll} E & \mathbb O \\ \mathbb O & Q \end{array} \right) = \left( \begin{array}{ll} \widetilde S & \mathbb O \\ \mathbb O & P^{\top} N Q \end{array} \right) \, .

По теореме о сингулярном разложении, матрицы P и Q можно подобрать так, чтобы произведение P^{\top} N Q стало матрицей, имеющей ненулевые элементы только на диагонали.

Следовательно, существуют ортогональные матрицы \widetilde V и \widetilde W, одновременно обеспечивающие сингулярные разложения матриц A и \widetilde A_k. Но тогда минимум разности \| A - \widetilde A_k \| может достигаться только когда на диагонали \widetilde A_k стоят первые k сингулярных чисел матрицы A, упорядоченные по убыванию.

§

При условии \sigma_k \ne \sigma_{k+1} матрица A_k из теоремы будет единственной матрицей, решающей поставленную оптимизационную задачу.

=>

Обозначим V_k матрицу, состоящую из k первых столбцов матрицы V: V_k=[V_{[1]}|\dots | V_{[k]}] \in \mathbb R^{n\times k}. Тогда матрица A_k из теоремы представима в виде

A_k = V_k \cdot V_k^{\top} A \, .

Аналогично, обозначив W_k матрицу, состоящую из k первых столбцов матрицы W, получим равенство

A_k = A W_k \cdot W_k^{\top} \, .

Источник

Householder A.S., Young G. Matrix approximation and latent roots. Amer. Math. Monthly. V.45, N 3, 1938, pp. 165–171


2017/06/27 22:18 редактировал au