主成分分析（Principal Component Analysis,PCA）

  • 主成分分析是一种重要的数据信息提取方法。具体而言，对于Rd\R^d上的数据，我们希望能从中提取出pp维的信息（其中p≪dp\ll d）
    • 在机器学习中，主成分分析可以让成千上万维的数据降到一个合适的范围（甚至可以可视化），以研究其数据结构。
  • 下面进行符号约定：
    1. 记数据为 X≜[x1⃗⊤x2⃗⊤⋮xn⃗⊤]∈Rn×dX\triangleq\begin{bmatrix} \vec{x_1}^\top\\ \vec{x_2}^\top\\ \vdots\\ \vec{x_n}^\top \end{bmatrix}\in\R^{n\times d} 即 X⊤=[x1⃗x2⃗⋯xn⃗]∈Rd×n.X^\top=\begin{bmatrix}\vec{x_1}&\vec{x_2}&\cdots&\vec{x_n}\end{bmatrix}\in\R^{d\times n}.
    2. 定义协方差矩阵 C≜1nX⊤X=1n∑i=1nxi⃗xi⃗⊤∈Rd×dC\triangleq\frac{1}{n}X^\top X=\frac{1}{n}\sum_{i=1}^n\vec{x_i}\vec{x_i}^\top\in\R^{d\times d} 则CC为对称矩阵，即C∈SdC\in\mathbb{S}^d。
  • 实际上，我们需要在Rd\R^d空间中找到pp个标准正交向量w⃗1,⋯ ,w⃗p\vec{w}_1,\cdots,\vec{w}_p，使得数据点在这些向量上的投影能够充分反应其原有的信息。
    • 如果直接取原始坐标系中的pp个坐标轴向量，那么往往会导致很多数据点投影后接近于0⃗\vec{0}，因而损失大量信息。所以我们需要寻找更合适的标准正交向量组。

寻找标准正交向量组

  • 首先我们来寻找第一个向量w⃗1\vec{w}_1。根据主成分分析的原则，我们希望每个向量x⃗i\vec{x}_i在w⃗1\vec{w}_1上的投影都尽量接近x⃗i\vec{x}_i本身，同时∥w⃗1∥=1\|\vec{w}_1\|=1。于是，我们考虑以下误差函数 err(x⃗1)=1n∑i=1n∥x⃗i−w⃗1(w⃗1⊤xi)∥22.\text{err}(\vec{x}_1)=\frac{1}{n}\sum_{i=1}^n\|\vec{x}_i-\vec{w}_1(\vec{w}_1^\top x_i)\|_2^2. 即所有数据点到w⃗1\vec{w}_1的垂直距离取平均。将其展开得 err(x⃗1)=1n∑i=1n(x⃗i−w⃗1(w⃗1⊤xi))⊤(x⃗i−w⃗1(w⃗1⊤xi))=1n∑i=1n(x⃗i⊤x⃗i−x⃗i⊤w⃗1(w⃗1⊤x⃗i)−(w⃗1(w⃗1⊤x⃗i))⊤x⃗i+(w⃗1(w⃗1⊤x⃗i))⊤(w⃗1(w⃗1⊤x⃗i)))=1n∑i=1n(∥x⃗i∥22−2(x⃗i⊤w⃗1)2+(w⃗1⊤x⃗i)2)=1n∑i=1n(∥x⃗i∥22−(x⃗i⊤w⃗1)2).\begin{aligned} \text{err}(\vec{x}_1)&=\frac{1}{n}\sum_{i=1}^n(\vec{x}_i-\vec{w}_1(\vec{w}_1^\top x_i))^\top(\vec{x}_i-\vec{w}_1(\vec{w}_1^\top x_i))\\ &= \frac{1}{n} \sum_{i=1}^{n} \left( \vec{x}_i^\top \vec{x}_i - \vec{x}_i^\top \vec{w}_1 (\vec{w}_1^\top \vec{x}_i) - (\vec{w}_1 (\vec{w}_1^\top \vec{x}_i))^\top \vec{x}_i + (\vec{w}_1 (\vec{w}_1^\top \vec{x}_i))^\top (\vec{w}_1 (\vec{w}_1^\top \vec{x}_i)) \right) \\ &= \frac{1}{n} \sum_{i=1}^{n} \left( \|\vec{x}_i\|_2^2 - 2(\vec{x}_i^\top \vec{w}_1)^2 + (\vec{w}_1^\top \vec{x}_i)^2 \right) \\ &= \frac{1}{n} \sum_{i=1}^{n} \left( \|\vec{x}_i\|_2^2 - (\vec{x}_i^\top \vec{w}_1)^2 \right). \end{aligned} 接着我们对这个函数进行最小优化： min⁡w⃗1∈Rd∥w⃗1∥2=1err(w⃗1)=min⁡w⃗1∈Rd∥w⃗1∥2=11n∑i=1n(∥x⃗i∥22−(x⃗i⊤w⃗1)2)=1n∑i=1n∥x⃗i∥22−max⁡w⃗1∈Rd∥w⃗1∥2=11n∑i=1n(x⃗i⊤w⃗1)2=1n∑i=1n∥x⃗i∥22−max⁡w⃗1∈Rd∥w⃗1∥2=1w⃗1⊤(1n∑i=1nx⃗ix⃗i⊤)w⃗1=1n∑i=1n∥x⃗i∥22−max⁡w⃗1∈Rd∥w⃗1∥2=1w⃗1⊤(1nX⊤X)w⃗1=1n∑i=1n∥x⃗i∥22−max⁡w⃗1∈Rd∥w⃗1∥2=1w⃗1⊤Cw⃗1=1n∑i=1n∥x⃗i∥22−λmax⁡{C}\begin{aligned} \min_{\substack{\vec w_1\in\mathbb R^d\\ \|\vec w_1\|_2=1}} \mathrm{err}(\vec w_1) &= \min_{\substack{\vec w_1\in\mathbb R^d\\ \|\vec w_1\|_2=1}} \frac1n\sum_{i=1}^n\big(\|\vec x_i\|_2^2 - (\vec x_i^\top \vec w_1)^2\big) \\ &= \frac1n\sum_{i=1}^n \|\vec x_i\|_2^2 - \max_{\substack{\vec w_1\in\mathbb R^d\\ \|\vec w_1\|_2=1}} \frac1n\sum_{i=1}^n (\vec x_i^\top \vec w_1)^2 \\ &= \frac1n\sum_{i=1}^n \|\vec x_i\|_2^2 - \max_{\substack{\vec w_1\in\mathbb R^d\\ \|\vec w_1\|_2=1}} \vec w_1^\top \left( \frac1n\sum_{i=1}^n \vec x_i \vec x_i^\top \right)\vec w_1 \\ &= \frac1n\sum_{i=1}^n \|\vec x_i\|_2^2 - \max_{\substack{\vec w_1\in\mathbb R^d\\ \|\vec w_1\|_2=1}} \vec w_1^\top \left( \frac1n X^\top X \right)\vec w_1 \\ &= \frac1n\sum_{i=1}^n \|\vec x_i\|_2^2 - \max_{\substack{\vec w_1\in\mathbb R^d\\ \|\vec w_1\|_2=1}} \vec w_1^\top C \vec w_1 \\ &= \frac1n\sum_{i=1}^n \|\vec x_i\|_2^2 - \lambda_{\max}\{C\} \end{aligned} 其中λmax⁡{C}\lambda_{\max}\{C\}表示协方差矩阵CC的最大特征值。由此可知当函数取最小值时，w⃗1\vec{w}_1为CC最大特征值对应的特征向量。
  • 类似地，我们也可以得到第二个，第三个，以及所有的特征向量。根据谱定理（见Chapter 3），协方差矩阵CC的各特征值对应的特征向量相互正交，因而只需要根据特征值从大到小排序，再进行归一化即可。

    注：在实际使用中，协方差矩阵一般使用1n−1X⊤X\dfrac{1}{n-1}X^\top X，以保证无偏性。

奇异值分解（Singular Value Decomposition，SVD）

  • 上面的主成分分析实际上是奇异值分解的特殊情形。一般的奇异值分解形式如下：设A∈Rm×nA\in\R^{m\times n}的秩为rr，则AA的SVD分解为 A=Um×mΣm×nVn×n=[UrUm−r][Σr0r×(n−r)0(m−r)×r0(m−r)×(n−r)][Vr⊤Vn−r⊤]=UrΣrVr⊤=∑i=1rσiu⃗iv⃗i⊤\begin{aligned} A&=U_{m\times m}\Sigma_{m\times n} V_{n\times n}\\ &=\begin{bmatrix} U_r & U_{m-r} \end{bmatrix} \begin{bmatrix} \Sigma_r & 0_{r \times (n-r)} \\ 0_{(m-r) \times r} & 0_{(m-r) \times (n-r)} \end{bmatrix} \begin{bmatrix} V_r^\top \\ V_{n-r}^\top \end{bmatrix}\\ &= U_r \Sigma_r V_r^\top\\ &= \sum_{i=1}^r \sigma_i \vec{u}_i \vec{v}_i^\top \end{aligned} 其中：
    • U,Ur,Um−r,V,Vr,Vn−rU,U_r,U_{m-r},V,V_r,V_{n-r}均为标准正交矩阵，称UU的列向量和VV的行向量为奇异向量；
    • Σr\Sigma_r为对角矩阵，对角线元素（称为奇异值）非负，且从左上到右下依次递减。
    • 上面的最后一个等式是SVD的二元形式（u⃗iv⃗i⊤\vec{u}_i \vec{v}_i^\top被称为二元组），即矩阵AA可表示为若干个二元组的和。
  • 接下来我们讨论如何构造矩阵AA的SVD分解。考虑对称矩阵A⊤A∈Rn×nA^\top A\in\R^{n\times n}，其秩为rr，因而有rr个正特征值（因为A⊤AA^\top A是半正定矩阵）。
    • 记A⊤AA^\top A的所有特征值为λ1≥⋯≥λr>λr+1=⋯=λn=0\lambda_1\geq\cdots\geq\lambda_r>\lambda_{r+1}=\cdots=\lambda_n=0，对应的特征向量为v⃗1,⋯ ,v⃗n\vec{v}_1,\cdots,\vec{v}_n；
    • 然后定义σi=λi,u⃗i=1σiAv⃗i\sigma_i=\sqrt{\lambda_i},\vec{u}_i=\dfrac{1}{\sigma_i}A\vec{v}_i（i=1,⋯ ,ri=1,\cdots,r），最后使用施密特正交化构造u⃗1,⋯ ,u⃗m\vec{u}_1,\cdots,\vec{u}_m。
    • 那么上述{u⃗i},{v⃗i}\{\vec{u}_i\},\{\vec{v}_i\}和{σi}\{\sigma_i\}即对应SVD分解中的U,VU,V和Σ\Sigma。
  • 下面进行简单解释：显然v⃗1,⋯ ,v⃗n\vec{v}_1,\cdots,\vec{v}_n为标准正交基，组成的矩阵为标准正交矩阵；而奇异值矩阵Σ\Sigma的构造也满足题设。所以下面主要证明u⃗1,⋯ ,u⃗m\vec{u}_1,\cdots,\vec{u}_m为标准正交基，且A=UΣV⊤A=U\Sigma V^\top：
    • 因为{u⃗1,⋯ ,u⃗m}\{\vec{u}_1,\cdots,\vec{u}_m\}是在{u⃗1,⋯ ,u⃗r}\{\vec{u}_1,\cdots,\vec{u}_r\}的基础上正交扩展的，如只需要证明{u⃗1,⋯ ,u⃗r}\{\vec{u}_1,\cdots,\vec{u}_r\}两两标准正交即可。推导如下： u⃗i⊤u⃗j=(Av⃗iσi)⊤(Av⃗jσj)=v⃗i⊤A⊤Av⃗jσiσj=λjv⃗i⊤v⃗jσiσj=λjσiσjv⃗i⊤v⃗j⏟=0=0,\begin{aligned} \vec{u}_i^\top \vec{u}_j &= \left( \frac{A \vec{v}_i}{\sigma_i} \right)^\top \left( \frac{A \vec{v}_j}{\sigma_j} \right) \\ &= \frac{\vec{v}_i^\top A^\top A \vec{v}_j}{\sigma_i \sigma_j} \\ &= \frac{\lambda_j \vec{v}_i^\top \vec{v}_j}{\sigma_i \sigma_j} \\ &= \frac{\lambda_j}{\sigma_i \sigma_j}\underbrace{ \vec{v}_i^\top \vec{v}_j}_{=0} \\ &= 0, \end{aligned} ∥u⃗i∥22=∥Av⃗iσi∥22=(Av⃗iσi)⊤(Av⃗iσi)=v⃗i⊤A⊤Av⃗iσi2=λiv⃗i⊤v⃗iσi2=λiσi2⏟=1⋅v⃗i⊤v⃗i⏟=1=1.\begin{aligned} \|\vec{u}_i\|_2^2 &= \left\| \frac{A \vec{v}_i}{\sigma_i} \right\|_2^2 \\ &= \left( \frac{A \vec{v}_i}{\sigma_i} \right)^\top \left( \frac{A \vec{v}_i}{\sigma_i} \right) \\ &= \frac{\vec{v}_i^\top A^\top A \vec{v}_i}{\sigma_i^2} \\ &= \frac{\lambda_i \vec{v}_i^\top \vec{v}_i}{\sigma_i^2} \\ &= \underbrace{\frac{\lambda_i}{\sigma_i^2}}_{=1}\cdot\underbrace{\vec{v}_i^\top \vec{v}_i}_{=1} \\ &= 1. \end{aligned}
    • 然后证明A=UΣV⊤A=U\Sigma V^\top：由构造可知 Av⃗i={σiu⃗i,1≤i≤r0⃗,r+1≤i≤mA\vec{v}_i=\begin{cases} \sigma_i\vec{u}_i,&1\leq i\leq r\\ \vec{0},&r+1\leq i\leq m \end{cases} 因此有 AV=A[v⃗1⋯v⃗rv⃗r+1⋯v⃗n]=[Av⃗1⋯Av⃗rAv⃗r+1⋯Av⃗n]=[σ1u⃗1⋯σru⃗r0⃗⋯0⃗]=[UrΣr0],UΣ=[UrUm−r][Σr000]=[UrΣr+Um−r⋅0Ur⋅0+Um−r⋅0]=[UrΣr0].\begin{aligned} AV &= A \begin{bmatrix} \vec{v}_1 & \cdots & \vec{v}_r & \vec{v}_{r+1} & \cdots & \vec{v}_n \end{bmatrix} \\ &= \begin{bmatrix} A\vec{v}_1 & \cdots & A\vec{v}_r & A\vec{v}_{r+1} & \cdots & A\vec{v}_n \end{bmatrix} \\ &= \begin{bmatrix} \sigma_1 \vec{u}_1 & \cdots & \sigma_r \vec{u}_r & \vec{0} & \cdots & \vec{0} \end{bmatrix} \\ &= \begin{bmatrix} U_r \Sigma_r & 0 \end{bmatrix}, \\[10pt] U\Sigma &= \begin{bmatrix} U_r & U_{m-r}\end{bmatrix}\begin{bmatrix} \Sigma_r & 0 \\ 0 & 0 \end{bmatrix} \\ &= \begin{bmatrix} U_r \Sigma_r + U_{m-r} \cdot 0 & U_r \cdot 0 + U_{m-r} \cdot 0 \end{bmatrix} \\ &= \begin{bmatrix} U_r \Sigma_r & 0 \end{bmatrix}. \end{aligned} 因此AV=UΣAV=U\Sigma，即得A=UΣV−1=UΣV⊤A=U\Sigma V^{-1}=U\Sigma V^\top。
  • 奇异值分解不唯一：施密特正交化可以选取任意的正交基；A⊤AA^\top A可能有相同特征值，对应不同特征向量；特征向量也可以任意取负。

SVD的几何意义

可参考B站上的无痛现代。

  • 下面我们会说明：若A的SVD分解为A=UΣV⊤A=U\Sigma V^\top，那么UU和V⊤V^\top就表示对向量的旋转或反射，而Σ\Sigma则表示对向量的缩放。
  • 对任意向量x⃗∈Rn\vec{x}\in\R^n，Ax⃗A\vec{x}表示对x⃗\vec{x}进行线性变换。设原Rn\R^n空间里的基向量为e⃗1,⋯ ,e⃗n,x⃗=∑i=1nxie⃗i\vec{e}_1,\cdots,\vec{e}_n,\displaystyle \vec{x}=\sum_{i=1}^n x_i\vec{e}_i，则：
    1. V⊤V^\top为标准正交矩阵，因而将e⃗1,⋯ ,e⃗n\vec{e}_1,\cdots,\vec{e}_n映射到另一组标准正交基v⃗1,⋯ ,v⃗n\vec{v}_1,\cdots,\vec{v}_n；
    2. Σ\Sigma矩阵则将v⃗1,⋯ ,v⃗n\vec{v}_1,\cdots,\vec{v}_n进行缩放，得到σ1v⃗1,⋯ ,σnv⃗n\sigma_1\vec{v}_1,\cdots,\sigma_n\vec{v}_n（当r<nr< n时部分基向量缩放为0⃗\vec{0}）；
    3. UU矩阵同样为标准正交矩阵，因而将σ1v⃗1,⋯ ,σnv⃗n\sigma_1\vec{v}_1,\cdots,\sigma_n\vec{v}_n映射到Rm\R^m空间里的标准正交基u⃗1,⋯ ,u⃗m\vec{u}_1,\cdots,\vec{u}_m，最终x⃗\vec{x}被映射到∑i=1rσiu⃗i\displaystyle\sum_{i=1}^r\sigma_i\vec{u}_i。

    若n=m=2n=m=2，x⃗\vec{x}为单位向量，则上述变换可以理解为：先将x⃗\vec{x}绕原点旋转到v⃗1\vec{v}_1所在的方向上（如果x⃗\vec{x}与v⃗1\vec{v}_1同向，则不旋转），然后将其缩放σ1\sigma_1倍，最后再绕原点旋转到u⃗1\vec{u}_1所在的方向上。（这可以模拟任意线性变换）

低秩近似（Low-Rank Approximation）

  • 实际上，SVD可以用于数据压缩，这便是低秩近似。其目标是在控制误差的前提下尽量压缩矩阵数据。
  • 对此，我们首先需要对矩阵误差进行衡量。与向量的范数类似，我们也可以定义矩阵的范数。

    • 一种最典型的矩阵范数就是Frobenius范数，其定义为（设A∈Rm×nA\in\R^{m\times n}）：

      ∥A∥F≔∑i=1m∑j=1naij2.\|A\|_F\coloneqq\sqrt{\sum_{i=1}^m\sum_{j=1}^n a_{ij}^2}.

      Frobenius范数的性质包括：

      1. ∥A∥F2=tr(A⊤A)\|A\|_F^2=\text{tr}(A^\top A)；（tr(A⊤A)\text{tr}(A^\top A)表示A⊤AA^\top A对角线元素之和）
      2. 对于任意标准正交矩阵U∈Rm×m,V∈Rn×nU\in\R^{m\times m},V\in\R^{n\times n}，∥UAV∥F=∥UA∥F=∥AV∥F=∥A∥F\|UAV\|_F=\|UA\|_F=\|AV\|_F=\|A\|_F；
      3. 设A∈Rm×nA\in\R^{m\times n}的秩为rr，对应奇异值为σ1≥⋯≥σr>0\sigma_1\geq\cdots\geq\sigma_r> 0，则∥A∥F2=∑i=1rσi2\displaystyle\|A\|_F^2=\sum_{i=1}^r\sigma_i^2。

      由此可知，当A−BA-B的Frobenius范数较小时，可以说明矩阵AA和BB的每个对应位置元素都比较接近。

    • 另一种矩阵范数是谱范数（Spectral Norm）【也称为矩阵ℓ2\ell^2范数】，其定义为：

      ∥A∥2≔max⁡x⃗∈Rn∥x⃗∥2=1∥Ax⃗∥2.\|A\|_2\coloneqq\max_{\substack{\vec{x}\in\R^n\\\|\vec{x}\|_2=1}}\|A\vec{x}\|_2.

      如果将AA看作线性变换，那么其谱范数就表示这个变换对单位向量的最大缩放因子。

      • 实际上，可以证明谱范数就是矩阵的最大奇异值σ1\sigma_1： ∥A∥2≔max⁡x⃗∈Rn∥x⃗∥2=1∥Ax⃗∥2=max⁡x⃗∈Rn∥x⃗∥2=1∥Ax⃗∥22=max⁡x⃗∈Rn∥x⃗∥2=1x⃗⊤A⊤Ax⃗=λmax⁡{A⊤A}=σ1.\begin{aligned} \|A\|_2 &\coloneqq \max_{\substack{\vec{x} \in \mathbb{R}^n \\ \|\vec{x}\|_2 = 1}} \|A\vec{x}\|_2 \\ &= \sqrt{\max_{\substack{\vec{x} \in \mathbb{R}^n \\ \|\vec{x}\|_2 = 1}} \|A\vec{x}\|_2^2} \\ &= \sqrt{\max_{\substack{\vec{x} \in \mathbb{R}^n \\ \|\vec{x}\|_2 = 1}} \vec{x}^\top A^\top A \vec{x}} \\ &= \sqrt{\lambda_{\max}\{A^\top A\}} \\ &= \sigma_1. \end{aligned} 其中倒数第二个等号可参考Rayleigh商的推导。
  • 在确定了矩阵误差的度量后，我们就可以进行低秩近似了：由上面的SVD分解可知，当AA的秩为r≤p≔min⁡{m,n}r\leq p\coloneqq\min\{m,n\}时，A=∑i=1rσiu⃗iv⃗i⊤\displaystyle A=\sum_{i=1}^r \sigma_i \vec{u}_i \vec{v}_i^\top。记σr+1=⋯=0\sigma_{r+1}=\cdots=0，则有 A=∑i=1pσiu⃗iv⃗i⊤A=\sum_{i=1}^{p} \sigma_i \vec{u}_i \vec{v}_i^\top 那么对任意k≤pk\leq p，记Ak≔∑i=1kσiu⃗iv⃗i⊤A_k\coloneqq\displaystyle\sum_{i=1}^{k} \sigma_i \vec{u}_i \vec{v}_i^\top，则称AkA_k为AA的低秩近似。相比储存AA需要n×mn\times m空间，存储AkA_k就只需要k(m+n+1)k(m+n+1)（两个标准正交矩阵+所有奇异值）空间。
  • 下面我们说明低秩近似在Frobenius范数和谱范数范畴下都是矩阵的一个良好近似。（这一结论也称为埃卡特-杨-米尔斯基定理，Eckart-Young-Mirsky theorem）
    • 首先给出谱定理下的一个结论： Ak∈arg min⁡B∈Rm×nrank(B)≤k∥A−B∥2A_k\in\argmin_{\substack{B\in\R^{m\times n}\\\text{rank}(B)\leq k}}\|A-B\|_2 即对于任意秩不超过kk的矩阵BB，均有∥A−Ak∥2≤∥A−B∥2\|A-A_k\|_2\leq\|A-B\|_2。其证明如下：
      • 首先计算∥A−Ak∥2\|A-A_k\|_2的值：因为A−Ak=∑i=1pσiu⃗iv⃗i⊤−∑i=1kσiu⃗iv⃗i⊤=∑i=k+1pσiu⃗iv⃗i⊤\displaystyle A-A_k=\sum_{i=1}^{p} \sigma_i \vec{u}_i \vec{v}_i^\top-\sum_{i=1}^{k} \sigma_i \vec{u}_i \vec{v}_i^\top=\sum_{i=k+1}^{p} \sigma_i \vec{u}_i \vec{v}_i^\top，所以∥A−Ak∥2\|A-A_k\|_2的值即为最大奇异值σk+1\sigma_{k+1}。
      • 然后证明对于任意秩不超过kk的矩阵BB均有∥A−B∥2≥σk+1\|A-B\|_2\geq\sigma_{k+1}：定义f(x⃗)=∥(A−B)x⃗∥2∥x⃗∥2f(\vec{x})=\dfrac{\|(A-B)\vec{x}\|_2}{\|\vec{x}\|_2}，则根据Rayleigh商的知识，∥A−B∥2=max⁡x⃗≠0⃗f(x⃗)\displaystyle\|A-B\|_2=\max_{\vec{x}\neq\vec{0}}f(\vec{x})，故只要找到一个x⃗0\vec{x}_0使f(x⃗0)≥σk+1f(\vec{x}_0)\geq\sigma_{k+1}即可。
      • 定义N(B)≔{x⃗:Bx⃗=0⃗},Vk+1≔[v⃗1,⋯ ,v⃗k+1]\mathcal{N}(B)\coloneqq\{\vec{x}:B\vec{x}=\vec{0}\},V_{k+1}\coloneqq\begin{bmatrix}\vec{v}_1,\cdots,\vec{v}_{k+1}\end{bmatrix}，则 dim(N(B))+dim(Vk+1)≥(n−k)+k+1>n\text{dim}(\mathcal{N}(B))+\text{dim}(V_{k+1})\geq (n-k)+k+1>n 这说明N(B)∩Vk+1\mathcal{N}(B)\cap V_{k+1}空间一定存在一个单位基向量，将其记为x⃗0\vec{x}_0。
      • 接下来证明f(x⃗0)≥σk+1f(\vec{x}_0)\geq\sigma_{k+1}： f(x⃗0)=∥(A−B)x⃗0∥2∥x⃗0∥2=∥Ax⃗0−Bx⃗0⏟=0∥2=∥A∑i=1k+1αiv⃗i⏟x⃗0∥2=∥(∑i=1pσiu⃗iv⃗i⊤)(∑i=1k+1αiv⃗i)∥=∥∑i=1p∑j=1k+1σiαju⃗iv⃗i⊤v⃗j∥2=∥∑i=1k+1αiσiu⃗i∥2=∥∑i=1k+1αiσiu⃗i∥22=∑i=1k+1αi2σi2≥σk+12∑i=1k+1αi2=σk+1∥x⃗0∥2=σk+1.\begin{aligned} f(\vec{x}_0)&=\frac{\|(A-B)\vec{x}_0\|_2}{\|\vec{x}_0\|_2}=\|A\vec{x}_0-\underbrace{B\vec{x}_0}_{=0}\|_2\\ &=\left\|A\underbrace{\sum_{i=1}^{k+1}\alpha_i\vec{v}_i}_{\vec{x}_0}\right\|_2=\left\|\left(\sum_{i=1}^{p} \sigma_i \vec{u}_i \vec{v}_i^\top\right)\left(\sum_{i=1}^{k+1}\alpha_i\vec{v}_i\right)\right\|\\ &=\left\| \sum_{i=1}^p \sum_{j=1}^{k+1} \sigma_i \alpha_j \vec{u}_i \vec{v}_i^\top \vec{v}_j \right\|_2\\ &=\left\| \sum_{i=1}^{k+1} \alpha_i \sigma_i \vec{u}_i \right\|_2=\sqrt{\left\| \sum_{i=1}^{k+1} \alpha_i \sigma_i \vec{u}_i \right\|_2^2} \\ &=\sqrt{\sum_{i=1}^{k+1} \alpha_i^2 \sigma_i^2}\geq \sqrt{\sigma_{k+1}^2 \sum_{i=1}^{k+1} \alpha_i^2} \\ &=\sigma_{k+1} \left\| \vec{x}_0 \right\|_2= \sigma_{k+1}. \end{aligned}
    • 类似地，Frobenius范数也有如下结论： Ak∈arg min⁡B∈Rm×nrank(B)≤k∥A−B∥F.A_k\in\argmin_{\substack{B\in\R^{m\times n}\\\text{rank}(B)\leq k}}\|A-B\|_F. 其证明如下：
      • 因为A−Ak=∑i=1pσiu⃗iv⃗i⊤−∑i=1kσiu⃗iv⃗i⊤=∑i=k+1pσiu⃗iv⃗i⊤\displaystyle A-A_k=\sum_{i=1}^{p} \sigma_i \vec{u}_i \vec{v}_i^\top-\sum_{i=1}^{k} \sigma_i \vec{u}_i \vec{v}_i^\top=\sum_{i=k+1}^{p} \sigma_i \vec{u}_i \vec{v}_i^\top，这可看作一个SVD分解，因此∥A−Ak∥F=∑i=k+1pσi2\displaystyle\|A-A_k\|_F=\sum_{i=k+1}^p\sigma_i^2。
      • 而对任意秩不超过kk的矩阵BB，记C≔A−BC\coloneqq A-B，并考虑CC的SVD分解C=∑i=1pγiy⃗iz⃗i⊤\displaystyle C=\sum_{i=1}^p\gamma_i\vec{y}_i\vec{z}_i^\top，那么根据上面的推导，γi\gamma_i可用∥C−Ci−1∥2\|C-C_{i-1}\|_2（Ci−1C_{i-1}的秩为i−1i-1）表示，即 γi=∥C−Ci−1∥2=∥A−B−Ci−1∥2=∥A−(B+Ci−1)∥2\gamma_i=\|C-C_{i-1}\|_2=\|A-B-C_{i-1}\|_2=\|A-(B+C_{i-1})\|_2 又因为B+Ci−1B+C_{i-1}的秩不超过k+i−1k+i-1，所以由上面谱范数的结论， γi=∥A−(B+Ci−1)∥2≥∥A−Ai+k−1∥2=σi+k.\gamma_i=\|A-(B+C_{i-1})\|_2\geq\|A-A_{i+k-1}\|_2=\sigma_{i+k}. 对任意i=1,2,⋯ ,pi=1,2,\cdots,p成立。因此 ∥A−B∥F=∑i=1pγi≥∑i=1pσi+k=∑i=k+1pσi2.\|A-B\|_F=\sum_{i=1}^p\gamma_i\geq\sum_{i=1}^p\sigma_{i+k}=\sum_{i=k+1}^p\sigma_i^2.