线性代数|机器学习-P18快速下降奇异值

1. 为什么要低秩矩阵

1.1 矩阵A的秩定义

如果矩阵X为n行n列实数矩阵，其有n个特征值如下：
σ 1 ≥ σ 2 ≥ ⋯ ≥ σ k ≥ σ k + 1 ≥ ⋯ ≥ σ n

$$\begin{equation} \sigma_1\ge\sigma_2\ge\cdots\ge\sigma_k\ge\sigma_{k+1}\ge\cdots\ge\sigma_{n} \end{equation}$$ σ1​≥σ2​≥⋯≥σk​≥σk+1​≥⋯≥σn​​​

• 如果满足如下条件
  $$\begin{array}{c}{\sigma }_{k+1}=0,{\sigma }_k>0\end{array}$$
  那么可得：
  $$\begin{array}{c}rank(X)=k,X={\sigma }_1{u}_1{v}_1^T+{\sigma }_2{u}_2{v}_2^T+\cdots +{\sigma }_k{u}_k{v}_k^T\end{array}$$

1.2 矩阵压缩PCA

我们的世界里面有很多数据，如果我们原封不动的发送数据，那么会导致数据量的增大，我们希望对数据进行压缩后再打包压缩，这样的话我们能够在带宽一定的情况下发送更多的数据，举例，假设我们有一个矩阵X，我们可以经过SVD奇异值分解得到如下：

• 假设矩阵$n\times n$ 矩阵的秩为k
  X = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T + ⋯ + σ k u k v k T + σ k + 1 u k + 1 v k + 1 T + ⋯ + σ n u n v n T

  $$\begin{equation} X=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T+\cdots+\sigma_ku_kv_k^T+\sigma_{k+1}u_{k+1}v_{k+1}^T+\cdots+\sigma_nu_nv_n^T\end{equation}$$ X=σ1​u1​v1T​+σ2​u2​v2T​+⋯+σk​uk​vkT​+σk+1​uk+1​vk+1T​+⋯+σn​un​vnT​​​

• 我们知道矩阵X的奇异值关系如下：
  σ 1 ≥ σ 2 ≥ ⋯ ≥ σ k ≥ σ k + 1 ≥ ⋯ ≥ σ n

  $$\begin{equation} \sigma_1\ge\sigma_2\ge\cdots\ge\sigma_k\ge\sigma_{k+1}\ge\cdots\ge\sigma_{n} \end{equation}$$ σ1​≥σ2​≥⋯≥σk​≥σk+1​≥⋯≥σn​​​

• 如果矩阵X的秩为k，那么可得：
  σ k + 1 = ⋯ = σ n = 0

  $$\begin{equation} \sigma_{k+1}=\cdots=\sigma_{n}=0 \end{equation}$$ σk+1​=⋯=σn​=0​​

• 在没有低秩压缩的情况下，我们发送数据大小$S_1$为,直接长=n宽=n相乘
  S 1 = n ∗ n = n 2

  $$\begin{equation} S_1=n*n=n^2 \end{equation}$$ S1​=n∗n=n2​​

• SVD奇异值分解后可得：
  X = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T + ⋯ + σ k u k v k T

  $$\begin{equation} X=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T+\cdots+\sigma_ku_kv_k^T \end{equation}$$ X=σ1​u1​v1T​+σ2​u2​v2T​+⋯+σk​uk​vkT​​​

• 在低秩压缩的后下，我们发送数据大小$S_2$为，其中每个
  S 2 = ( n + n ) ∗ k = 2 n k

  $$\begin{equation} S_2=(n+n)*k=2nk \end{equation}$$ S2​=(n+n)∗k=2nk​​
  

• 那么我们可以得到如下：
  2 n k ≤ n 2 → k ≤ n 2

  $$\begin{equation} 2nk\leq n^2\rightarrow k\leq\frac{n}{2} \end{equation}$$ 2nk≤n2→k≤2n​​​

• 那问题来了，我们能够做得更好吗？我们能够用更小的数据来压缩吗？

2. 低秩矩阵图像处理

假设我们有一张日本国旗的图像表示如下，我们

• 如图所示，我们可以依据对称性，将一个日本国旗拆解为如下三个部分，每个部分的秩表示如下,注意要取整：
  $$\begin{array}{c}{r}_1=(1-\frac{\sqrt{2}}{2})r;r_2=(1-\frac{\sqrt{2}}{2})r;r_3=1\end{array}$$
• 那么拆解后，数据的秩表示如下：
  $$\begin{array}{c}{r}_k=(2-\sqrt{2})r+1\end{array}$$
• 小结：对于一个原始的日本国旗图像来说，我们通过对称的原理，不断的对称分解得到三个最小的无法对称的三个小图像，这样我们可以将原来的日本国旗图像最后分解为三个小图像发给对方，当对方收到三个小图像后，可以通过对称原理进行还原，这样数据就压缩了，我们可以进行数据低秩压缩处理。
• 整体思路如下:
  

3. 秩的相关性质

3.1 秩的公差轴表示

假设我们有一个公差 $0<ϵ<1$, 如果满足 ${\sigma }_{k+1}\le ϵ{\sigma }_1(x),{\sigma }_k\ge ϵ{\sigma }_1(x)$,则 $ran{k}_{ϵ}=k$

• 我们知道$0<ϵ<1$，两百年乘以 ${\sigma }_1(x)$ 可得：
  $$\begin{array}{c}0<ϵ{\sigma }_1(x)<{\sigma }_1(x)\end{array}$$
• 也就是说 $ϵ{\sigma }_1(x)$ 可以取到所有大于零的奇异值
  
• 也就是说我们能够在${\sigma }_k(x)$这个点上面找到奇异值的正负边界，那么我们就能够知道秩为k。

3.2 Eckart-Young 定理

假设矩阵B有和矩阵$A_k$一样的值为k，那么可得如下结论：

∣ ∣ A − B ∣ ∣ ≥ ∣ ∣ A − A k ∣ ∣

$$\begin{equation} ||A-B|| \geq ||A-A_k|| \end{equation}$$ ∣∣A−B∣∣≥∣∣A−Ak​∣∣​​

• 画图证明：
  假设我们定义矩阵A为一个向量，$A_k$为矩阵A向量的子向量,定义矩阵B的秩为k，那么矩阵B向量的长度和向量$A_k$长度一样，方向不同，具体如下图所述：
  
  -由于$0°<\theta <90°$，所以可得$90°<\beta <180°$，也就是说在新的三角形中，$\beta$是钝角，那么钝角对应的边最大，所以可得$||C||\ge ||D||$,可以得到结论如下：
  $$\begin{array}{c}||A-B||\ge ||A-A_k||\end{array}$$
• 那么${\sigma }_{k+1}=||A-A_k||$暂时不会，后面补充吧！！

4. 低秩矩阵

4.1 低秩矩阵描述

• 4.1 hilbert 希尔伯特矩阵
  我们定义希尔伯特矩阵如下：
  H j k = 1 j + k − 1

  $$\begin{equation} H_{jk}=\frac{1}{j+k-1} \end{equation}$$ Hjk​=j+k−11​​​

• 4.2 Vandermonde 范德蒙矩阵
  我们定义范德蒙矩阵如下：
  V n = [ 1 x 1 x 1 2 ⋯ x 1 n − 1 1 x 2 x 2 2 ⋯ x 2 n − 1 ⋮ ⋮ ⋮ ⋯ ⋮ 1 x n x n 2 ⋯ x n n − 1 ]

  $$\begin{equation} V_{n}=\begin{bmatrix} 1&x_1&x_1^2&\cdots&x_1^{n-1}\\\\ 1&x_2&x_2^2&\cdots&x_2^{n-1}\\\\ \vdots&\vdots&\vdots&\cdots&\vdots\\\\ 1&x_n&x_n^2&\cdots&x_n^{n-1} \end{bmatrix} \end{equation}$$ Vn​= ​11⋮1​x1​x2​⋮xn​​x12​x22​⋮xn2​​⋯⋯⋯⋯​x1n−1​x2n−1​⋮xnn−1​​ ​​​

• 其中 $A_n=[a_{ij}]$时一个$n\times n$阶矩阵，每个元素为$a_{ij}=x_i^{j-1}$
  经常我们需要求解 $V_n^{-1}$,但是因为$V_n$是低秩矩阵，所以很难求解其逆矩阵，那为什么这么难求这些低秩矩阵的逆呢？原因居然是世界是平滑的，所以存在很多低秩的矩阵。

4.2 函数低秩矩阵形式

假设我们有一个函数表示如下：
P ( x , y ) = 1 + x + x y → X j k = P ( j , k )

$$\begin{equation} P(x,y)=1+x+xy\rightarrow X_{jk}=P(j,k) \end{equation}$$ P(x,y)=1+x+xy→Xjk​=P(j,k)​​

• 那么矩阵X可以表示如下：
  $$\begin{array}{c}X=\left[\begin{array}{c}1\\ \\ 1\\ \\ ⋮\\ \\ 1\end{array}\right]\left[\begin{array}{cccc}1& 1& \cdots & 1\end{array}\right]+\left[\begin{array}{c}1\\ \\ 2\\ \\ ⋮\\ \\ n\end{array}\right]\left[\begin{array}{cccc}1& 1& \cdots & 1\end{array}\right]+\left[\begin{array}{c}1\\ \\ 2\\ \\ ⋮\\ \\ n\end{array}\right]\left[\begin{array}{cccc}1& 2& \cdots & n\end{array}\right]\end{array}$$
• 那么可以得到矩阵X的秩小于3，即$Rank(X)\le 3$

4.3通项小结

假设我们有如下函数
p ( x , y ) = ∑ s = 0 m − 1 ∑ t = 0 m − 1 a s t x s y t , X j k = p ( j , k )

$$\begin{equation} p(x,y)=\sum_{s=0}^{m-1}\sum_{t=0}^{m-1}a_{st}x^sy^t,X_{jk}=p(j,k) \end{equation}$$ p(x,y)=s=0∑m−1​t=0∑m−1​ast​xsyt,Xjk​=p(j,k)​​

• 那么我们可以得到矩阵X的秩有如下关系：
  $$\begin{array}{c}rank(X)\le m^2\end{array}$$

4.4 函数采样拟合

假设我们有一个矩阵X且$X_{jk}=\frac{1}{j+k-1},f(x,y)=\frac{1}{x+y-1}$,我们希望通过在$f(x,y)$函数中采样的方法得到一个近似的函数$p(x,y)$，使得我们能够在进行了有限的采样后，我们只需要用$p(x,y)$近似于原函数$f(x,y)$
∣ f ( x , y ) − p ( x , y ) ∣ ≤ ϵ n ∣ ∣ x ∣ ∣ 2

$$\begin{equation} |f(x,y)-p(x,y)|\leq \frac{\epsilon}{n}||x||_2 \end{equation}$$ ∣f(x,y)−p(x,y)∣≤nϵ​∣∣x∣∣2​​​

• 是不是很神奇，用有限的采样可以拟合出来原来的函数。
  假设我们有一个希尔伯特矩阵，其秩为1000，假设我们有一个公差$ϵ=10^{-15}$,Reade's 大神得到秩为
  $$\begin{array}{c}ran{k}_{ϵ}(H_{1000})\le 719\end{array}$$

5. 西尔维斯特方程

Sylvester 方程：
A X + X B = C

$$\begin{equation} AX+XB=C \end{equation}$$ AX+XB=C​​

其中A、B及C是已知的矩阵，问题是要找出符合条件的X。其中所有矩阵的系数都是复数。为了要使方程成立，矩阵的行和列需要满足一定条件，A和B都要是方阵，大小分别是n和m，而X和C要是n行m列的矩阵，n和m也可以相等，四个矩阵都是大小相同的方阵。
西尔维斯特方程有唯一解X的充分必要条件是A和-B没有共同的特征值。
AX+XB=C也可以视为是（可能无穷维中）巴拿赫空间中有界算子的方程。此情形下，唯一解X的充份必要条件几乎相同：唯一解X的充份必要条件是A和-B的谱互为不交集

5.1 希尔伯特矩阵举例

[ 1 2 3 2 ⋱ n − 1 2 ] H − H [ − 1 2 − 3 2 ⋱ − n + 1 2 ] = [ 1 1 ⋯ 1 1 1 ⋯ 1 ⋮ ⋮ ⋯ ⋮ 1 1 ⋯ 1 ]

$$\begin{equation} \begin{bmatrix} \frac{1}{2}\\\\ &\frac{3}{2}\\\\ &&\ddots\\\\ &&&n-\frac{1}{2} \end{bmatrix}H-H\begin{bmatrix} -\frac{1}{2}\\\\ &-\frac{3}{2}\\\\ &&\ddots\\\\ &&&-n+\frac{1}{2} \end{bmatrix}=\begin{bmatrix} 1&1&\cdots&1\\\\ 1&1&\cdots&1\\\\ \vdots&\vdots&\cdots&\vdots\\\\ 1&1&\cdots&1 \end{bmatrix} \end{equation}$$ ​21​​23​​⋱​n−21​​ ​H−H ​−21​​−23​​⋱​−n+21​​ ​= ​11⋮1​11⋮1​⋯⋯⋯⋯​11⋮1​ ​​​

• 我们那H中的第i,j项目来说；
  $$\begin{array}{c}{H}_{ij}=\frac{1}{i+j-1}\end{array}$$
  $$\begin{array}{c}(i-\frac{1}{2})\cdot \frac{1}{i+j-1}-(-j+\frac{1}{2})\frac{1}{i+j-1}=\frac{i+j-1}{i+j-1}=1\end{array}$$
• 既然每个元素结果为1，所以最后结果为全1矩阵。

5.2 范德蒙矩阵举例

A = [ x 1 x 2 ⋱ x n ] ; B = [ 0 0 ⋯ − 1 1 0 0 ⋯ ⋅ 0 1 0 ⋱ 0 0 0 1 0 ] ; C = [ 0 0 0 x 1 n + 1 0 0 0 x 2 n + 1 0 0 0 ⋮ 0 0 0 x n n + 1 ] ;

$$\begin{equation} A=\begin{bmatrix}x_1\\\\ &x_2\\\\ &&\ddots\\\\ &&&x_n\end{bmatrix}; B=\begin{bmatrix} 0&0&&\cdots&-1\\\\ 1&0&0&\cdots&\cdot\\\\ 0&1&0&\ddots&0\\\\ 0&0&1&&0\end{bmatrix}; C=\begin{bmatrix} 0&0&0&x_1^n+1\\\\ 0&0&0&x_2^n+1\\\\ 0&0&0&\vdots\\\\ 0&0&0&x_n^n+1 \end{bmatrix}; \end{equation}$$ A= ​x1​​x2​​⋱​xn​​ ​;B= ​0100​0010​001​⋯⋯⋱​−1⋅00​ ​;C= ​0000​0000​0000​x1n​+1x2n​+1⋮xnn​+1​ ​;​​

5.3 西尔维斯特方程

如果 X满足如下方程：
A X − X B = C

$$\begin{equation} AX-XB=C \end{equation}$$ AX−XB=C​​

• A,B是正规矩阵，E为A的特征值集合，F为B的的特征值集合，那么可以得到如下：
  $$\begin{array}{c}{\sigma }_{rk+1}(X)\le Z_k[\sigma (A),\sigma (B)]{\sigma }_1(X)\to rank(C)=r;\end{array}$$