作业11

提交截至时间：暂定 2022/04/08 下周五 20:00（晚上）

理论部分 (奇异值分解)

定理 0.0.1. 矩阵奇异值分解。矩阵 \(A \in \mathbb { R } ^ { m \times n }\) , 它的奇异值分解为

\[ A = U \Sigma V ^ {\mathrm {T}} = U \left( \begin{array}{c c} \Sigma_ {r} & 0 \\ 0 & 0 \end{array} \right) V ^ {\mathrm {T}} \]

其中: \(U \in R ^ { m \times m }\) 和 \(V \in R ^ { n \times n }\) 均为正交矩阵, 对角矩阵 \(\Sigma _ { r } = d i a g \left( \sigma _ { 1 } , \sigma _ { 2 } , \cdot \cdot \cdot , \sigma _ { r } \right) \in R ^ { r \times r }\) , 且其对角线元素满足 \(\sigma _ { 1 } \geqslant \sigma _ { 2 } \geqslant \dots \geqslant \sigma _ { r } > 0\) 。

矩阵 \(A\) 的秩为 \(\operatorname { r a n k } ( A ) = r\) 。记 \(U = ( u _ { 1 } , u _ { 2 } , \cdot \cdot \cdot , u _ { m } ) , V = ( v _ { 1 } , v _ { 2 } , \cdot \cdot \cdot , v _ { n } )\) , 则 A 可重新表示为

\[ A = \sum_ {i = 1} ^ {r} \sigma_ {i} u _ {i} v _ {i} ^ {\mathrm {T}} \]

\(u _ { i }\) 和 \(v _ { i }\) 分别为奇异值 \(\sigma _ { i }\) 对应的左奇异向量和右奇异向量。易知 \(\begin{array} { r } { \| A \| _ { F } = \sqrt { \sum _ { i = 1 } ^ { r } \sigma _ { i } ^ { 2 } } } \end{array}\) , 矩阵 \(A\) 在Frobenius 范数意义下的最优秩 \(r _ { 0 }\) 逼近为 \(\begin{array} { r } { A _ { r _ { 0 } } = \sum _ { i = 1 } ^ { r _ { 0 } } \sigma _ { i } u _ { i } v _ { i } ^ { \mathrm { T } } , } \end{array}\) , 且 \(\begin{array} { r } { \| A - A _ { r _ { 0 } } \| _ { \mathrm { F } } ^ { 2 } = \sum _ { i = r _ { 0 } + 1 } ^ { r } \sigma _ { i } ^ { 2 } } \end{array}\) , 其中 \(r _ { 0 } < r\) 。

矩阵 \(A\) 的谱范数定义为 \(\| A \| _ { 2 } = \sigma _ { 1 }\) , 核范数定义为

\[ \| A \| = \max _ {U, V} \left\{t r \left(U ^ {\mathrm {T}} A V\right): U ^ {\mathrm {T}} U = I _ {m}, V ^ {T} V = I _ {n} \right\} \]

其中: \(I _ { m }\) 表示 \(m\) 阶单位矩阵。矩阵 \(A\) 的核范数可用它的奇异值来表示, 即 \(\begin{array} { r } { \| A \| _ { * } = \sum _ { i = 1 } ^ { r } \sigma _ { i } } \end{array}\) , 且当 \(A\) 满足 \(\| A \| _ { 2 } \leqslant 1\) 时,此范数是 \(\operatorname { r a n k } ( A )\) 的包络。

由矩阵 A 的 Frobenius 范数

\[ \| A \| _ {F} = \sqrt {\sum_ {i = 1} ^ {m} \sum_ {j = 1} ^ {n} a _ {i j} ^ {2}} = \sqrt {t r (A ^ {\mathrm {T}} A)} = \sqrt {\sum_ {i = 1} ^ {r} \sigma_ {i} ^ {2}} \]

可得假设矩阵A作为图片数据， \(\| A \| _ { F } ^ { 2 }\) 等于所有像素的平方和，等于 \(A ^ { \mathrm { T } } A\) 的迹，等于数据的总方差 (Total Variance)，等于 \(A ^ { \mathrm { T } } A\) 特征值的和，等于 A 奇异值的平方和。

而在 PCA 中，第 i 个主成分的重要性由其在总方差中的比例

\[ \frac {\sigma^ {2}}{\sum_ {j = 1} ^ {r} \sigma_ {j} ^ {2}} \]

决定，矩阵 \(A\) 在 Frobenius 范数意义下的秩 \(r _ { 0 }\) 逼近的压缩比（损失信息率）为

\[ \frac {\sum_ {j = 1} ^ {r _ {0}} \sigma_ {j} ^ {2}}{\sum_ {j = 1} ^ {r} \sigma_ {j} ^ {2}} \]

阅读以上材料理解奇异值分解可得到矩阵在Frobenius范数下的最优逼近，进一步理解Frobenius范数及压缩比，并解答以下问题。

习题 1.

\(A = \left( \begin{array} { l l l l } { 1 } & { 0 } & { 0 } & { 0 } \\ { 0 } & { 0 } & { 0 } & { 4 } \\ { 0 } & { 3 } & { 0 } & { 0 } \\ { 0 } & { 0 } & { 0 } & { 0 } \\ { 2 } & { 0 } & { 0 } & { 0 } \end{array} \right)\) 其秩 \(r = 3\) ,其紧奇异值分解为:

\[ \left( \begin{array}{c c c c} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 4 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 \end{array} \right) = \left( \begin{array}{c c c} 0 & 0 & \sqrt {0 . 2} \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & \sqrt {0 . 8} \end{array} \right) \left( \begin{array}{c c c} 4 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & \sqrt {5} \end{array} \right) \left( \begin{array}{c c c c} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{array} \right) \]

若取 \(k = 2\) , 则其截断奇异值分解为

\[ \left( \begin{array}{c c c c} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 4 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 \end{array} \right) \approx \left( \begin{array}{c c} 0 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 0 \\ 0 & 0 \end{array} \right) \left( \begin{array}{c c} 4 & 0 \\ 0 & 3 \end{array} \right) \left( \begin{array}{c c c c} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{array} \right) = \left( \begin{array}{c c c c} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 4 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right) \]

请问 \(k = 2\) 的截断方式损失了多少信息？（写出压缩比）

解. (30-5)/30=5/6

习题2. 利用习题1中矩阵A的奇异值分解结果求A的Moore-Penrose广义逆。（无需化简）

解.

\[ \left( \begin{array}{c c c c} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 4 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 \end{array} \right) ^ {\dagger} = \left( \begin{array}{c c c c} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{array} \right) ^ {\mathrm {H}} \left( \begin{array}{c c c} 4 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & \sqrt {5} \end{array} \right) ^ {- 1} \left( \begin{array}{c c c} 0 & 0 & \sqrt {0 . 2} \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & \sqrt {0 . 8} \end{array} \right) ^ {\mathrm {H}} \]