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

$$ A= U \Sigma V^{\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_{\color{Red}{k}}= U \Sigma_{\color{Red}{k}} V^{\top} $$ где $$ \Sigma_{\color{Red}{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) $$ т.е. имеет на диагонали $ {\color{Red}{k}} $ наибольших по величине и упорядоченных по убыванию сингулярных чисел матрицы $ A $, а все остальные элементы — нулевыми. При такой матрице $ A_{\color{Red}{k}} $ величина указанного минимума равна $$ \sqrt{\sum_{j={\color{Red}{k}}+1}^{\mathfrak r} \sigma_j^2} \, . $$

Доказательство существенно основывается на утверждении, что евклидова норма матрицы не меняется при ее домножении на ортогональную. Из этого, в частности, следует, что указанная в формулировке теоремы величина минимума на матрице $ A_k $ достигается: $$ \|A-A_k \|=\| U (\Sigma-\Sigma_k) V^{\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 U \widetilde \Sigma_k \widetilde V^{\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 U^{\top} A \widetilde V $$ имеет блочную структуру $$ \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 U \left( \begin{array}{ll} \widetilde S & L\\ \mathbb O_{(m-k) \times k} & \mathbb O_{(m-k) \times (n -k) } \end{array} \right) \widetilde V^{\top} $$ имеет ранг $ k $, но при этом обеспечивает меньшую величину для нормы разности $$ \left\|A- \widetilde A \right\|= \left\|A- \widetilde U \left( \begin{array}{ll} \widetilde S & L\\ \mathbb O_{(m-k) \times k} & \mathbb O_{(m-k) \times (n -k) } \end{array} \right) \widetilde V^{\top} \right\| = $$ $$ = \left\| \widetilde U \left( \begin{array}{ll} H & L \\ M& N \end{array} \right) \widetilde V^{\top} - \widetilde U \left( \begin{array}{ll} \widetilde S & L\\ \mathbb O_{(m-k) \times k} & \mathbb O_{(m-k) \times (n -k) } \end{array} \right) \widetilde V^{\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 U \left( \begin{array}{ll} H & \mathbb O \\ \mathbb O & N \end{array} \right) \widetilde V^{\top} \, . $$ Если при этом $ H \ne \widetilde S $, то матрица $$ \widetilde A= \widetilde U \left( \begin{array}{ll} H & \mathbb O \\ \mathbb O & \mathbb O \end{array} \right) \widetilde V^{\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 U $ и $ \widetilde V $, одновременно обеспечивающие сингулярные разложения матриц $ A $ и $ \widetilde A_k $. Но тогда минимум разности $ \| A - \widetilde A_k \| $ может достигаться только когда на диагонали $ \widetilde A_k $ стоят первые $ k $ сингулярных чисел матрицы $ A $, упорядоченные по убыванию. ♦

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

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

$$ A_k = U_k \cdot U_k^{\top} A \, . $$ Аналогично, обозначив $ V_k $ матрицу, состоящую из $ k $ первых столбцов матрицы $ V $, получим равенство $$ A_k = A V_k \cdot V_k^{\top} \, . $$

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