第 4 次作业¶

理论部分¶

习题 1¶

利用 QR 分解求解下述线性方程组的解（最终结果可只需写出具体矩阵与向量的乘积形式即可）：

\[ \left[ \begin{array}{c c c} 1 & 2 & 2 \\ 2 & 1 & 2 \\ 1 & 2 & 1 \end{array} \right] \left[ \begin{array}{c} x _ {1} \\ x _ {2} \\ x _ {3} \end{array} \right] = \left[ \begin{array}{c} 1 \\ 2 \\ 3 \end{array} \right] \]

解.

\[ A = \left[ \begin{array}{c c c} {\frac {1}{\sqrt {6}}} & {\frac {1}{\sqrt {3}}} & {\frac {1}{\sqrt {2}}} \\ {\frac {2}{\sqrt {6}}} & {- \frac {1}{\sqrt {3}}} & 0 \\ {\frac {1}{\sqrt {6}}} & {\frac {1}{\sqrt {3}}} & {- \frac {1}{\sqrt {2}}} \end{array} \right] \left[ \begin{array}{c c c} {\sqrt {6}} & {\sqrt {6}} & {\frac {7}{\sqrt {6}}} \\ {0} & {\sqrt {3}} & {\frac {1}{\sqrt {3}}} \\ {0} & 0 & {\sqrt {2}} \end{array} \right] = Q R \]

因此，

\[ \boldsymbol {x} = \left[ \begin{array}{c c c} \sqrt {6} & \sqrt {6} & \frac {7}{\sqrt {6}} \\ 0 & \sqrt {3} & \frac {1}{\sqrt {3}} \\ 0 & 0 & \sqrt {2} \end{array} \right] ^ {- 1} \left[ \begin{array}{c c c} \frac {1}{\sqrt {6}} & \frac {1}{\sqrt {3}} & \frac {1}{\sqrt {2}} \\ \frac {2}{\sqrt {6}} & - \frac {1}{\sqrt {3}} & 0 \\ \frac {1}{\sqrt {6}} & \frac {1}{\sqrt {3}} & - \frac {1}{\sqrt {2}} \end{array} \right] ^ {\top} \left[ \begin{array}{c} 1 \\ 2 \\ 3 \end{array} \right] \]

习题 2¶

求矩阵 $A=\begin{pmatrix} 0& 1\\ 1& 1\\ 1& 0\end{pmatrix}$ 的SVD分解。

解

$A^TA=\begin{pmatrix}2&1\\1&2\end{pmatrix}$

特征值为 $1$ 对应的特征向量为 $(1,-1)^T$

特征值为 $3$ 对应的特征向量为 $(1,1)^T$

所以 $\Sigma=\begin{pmatrix} \sqrt{3}&0\\ 0&1\\ 0&0 \end{pmatrix}, V^T=\begin{pmatrix} \frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}} \end{pmatrix}$

$U_1=AV\Sigma^{\dagger}=\begin{pmatrix} \frac{1}{\sqrt{6}}&-\frac{1}{\sqrt{2}}&0\\ \frac{2}{\sqrt{6}}&0&0\\ \frac{1}{\sqrt{6}}&\frac{1}{\sqrt{2}}&0 \end{pmatrix}$

所以 $$ A= \begin{pmatrix} \frac{1}{\sqrt{6}}&-\frac{1}{\sqrt{2}}\ \frac{2}{\sqrt{6}}&0\ \frac{1}{\sqrt{6}}&\frac{1}{\sqrt{2}} \end{pmatrix} \begin{pmatrix} \sqrt{3}&0\ 0&1\ \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\ \frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}} \end{pmatrix} $$

习题3¶

求矩阵 $A=\begin{pmatrix} 0& 1\\ 1& 1\\ 1& 0\end{pmatrix}$ 在F范数下秩为 $1$ 的最优近似。（注：根据 Eckart-Young-Mirsky 定理，即为只保留最大的秩所对应的矩阵）

解

最佳秩1近似： $$ \begin{pmatrix} \frac{1}{\sqrt{6}}&-\frac{1}{\sqrt{2}}\ \frac{2}{\sqrt{6}}&0\ \frac{1}{\sqrt{6}}&\frac{1}{\sqrt{2}} \end{pmatrix} \begin{pmatrix} {\sqrt{3}}&0\ 0&{0}\ \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\ \frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}} \end{pmatrix} $$

习题 4¶

假设 $D$ 是一个 $n \times d$ 的矩阵，矩阵 $B$ 是 $( n + d ) \times ( n + d )$ 定义为

\[ B = \left( \begin{array}{c c} 0 & D ^ {\mathrm {T}} \\ D & 0 \end{array} \right) \]

显然 $B$ 是对称矩阵。请证明矩阵 $B$ 的对角化会产生 $D$ 的奇异值分解所需要的所有信息。

解. $D$ 的奇异值分解所需要的信息为 $D ^ { T } D$ 的特征向量和 $D D ^ { T }$ 的特征向量，以及对应的特征值。现假设对应于特征值为 $\lambda ^ { 2 } ( \lambda > 0 )$ 的 $D ^ { T } D$ 的特征向量为 $\pmb { x } _ { 1 } ( | \pmb { x } _ { 1 } | _ { 2 } = 1 ) $， $D D ^ { T }$ 的特征向量为 $x _ { 2 } ( \| x _ { 2 } \| _ { 2 } = 1 )$ . 因此， $D ^ { T } D \pmb { x } _ { 1 } = \lambda ^ { 2 } \pmb { x } _ { 1 }$ 以及 $D D ^ { T } { \pmb x } _ { 2 } = \lambda ^ { 2 } { \pmb x } _ { 2 }$ 。故

\[ \left(D D ^ {T}\right) D \boldsymbol {x} _ {1} = \lambda^ {2} D \boldsymbol {x} _ {1} \]

所以存在 $k$ 使得 $D \pmb { x } _ { 1 } = k \pmb { x } _ { 2 }$ 。由于 $\| \pmb { x } _ { 1 } \| _ { 2 } = \| \pmb { x } _ { 2 } \| _ { 2 } = 1$ ，可得 $k = \lambda$ ，即 $D \pmb { x } _ { 1 } = \lambda \pmb { x } _ { 2 }$ 。同理有$D ^ { T } x _ { 2 } = \lambda x _ { 1 }$ 。

下面证明 $ \mathbf { { \boldsymbol { x } } }=\left( \begin{array}{c} \boldsymbol {x} _ {1} \ \boldsymbol {x} _ {2} \end{array} \right) $ 是矩阵 $B$ 的特征值为 $\lambda$ 的特征向量。易计算

\[ B \boldsymbol {x} = \left( \begin{array}{c c} 0 & D ^ {\mathrm {T}} \\ D & 0 \end{array} \right) \left( \begin{array}{c} \boldsymbol {x} _ {1} \\ \boldsymbol {x} _ {2} \end{array} \right) = \left( \begin{array}{c} D ^ {T} \boldsymbol {x} _ {2} \\ D \boldsymbol {x} _ {1} \end{array} \right) = \lambda \left( \begin{array}{c} \boldsymbol {x} _ {1} \\ \boldsymbol {x} _ {2} \end{array} \right) \]

因此， $D$ 的奇异值分解信息包含在 $B$ 的对角化过程中。

实践部分¶

习题 5¶

任选一张图片，使用SVD分解对图片进行压缩，分别展示取 $1 \%$ 、 $2 \%$ 、 $10 \%$ 、 $50 \%$ 奇异值的结果。提示：可在 numpy 包中可以使用 'np.linalg.svd'对一个'np.matrix'对象进行SVD分解。需要上传代码和结果。