线性代数|机器学习-P8矩阵低秩近似eckart-young

1. SVD奇异值分解

我们知道，对于任意矩阵A来说，我们可以将其通过SVD奇异值分解得到$A=U\Sigma V^T$，通过$\Sigma$中可以看到只有r个非零的特征值，所以通过矩阵A奇异值分解可得如下表达式：
$$\begin{array}{c}A={\sigma }_1{u}_1{v}_1^T+{\sigma }_2{u}_2{v}_2^T+\cdots +{\sigma }_n{u}_n{v}_n^T，{\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_r\end{array}$$
$$\begin{array}{c}{A}_k={\sigma }_1{u}_1{v}_1^T+{\sigma }_2{u}_2{v}_2^T+\cdots +{\sigma }_k{u}_k{v}_k^T，{\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_k\end{array}$$
$$\begin{array}{c}A\sim A_k\end{array}$$

• 上面的等式里面，我们希望通过前面k项的和来近似矩阵A，这就是主成分分析PCA

2. Eckart-Young

如果矩阵B的秩为 k ，对于矩阵A和B的距离来说，矩阵A与子矩阵$A_k$(秩为k)的距离小于等于矩阵A与矩阵B之间的距离

• 假设我们有如下矩阵
  $$\begin{array}{c}A=\left[\begin{array}{cccc}4& 0& 0& 0\\ & & & \\ 0& 3& 0& 0\\ & & & \\ 0& 0& 2& 0\\ & & & \\ 0& 0& 0& 1\end{array}\right];A_2=\left[\begin{array}{cccc}4& 0& 0& 0\\ & & & \\ 0& 3& 0& 0\\ & & & \\ 0& 0& 0& 0\\ & & & \\ 0& 0& 0& 0\end{array}\right];B=\left[\begin{array}{cccc}3.5& 3.5& 0& 0\\ & & & \\ 3.5& 3.5& 0& 0\\ & & & \\ 0& 0& 1.5& 1.5\\ & & & \\ 0& 0& 1.5& 1.5\end{array}\right]\end{array}$$
• 用python计算 $||A-B||\ge ||A-A_k||$

import numpy as npif __name__=="__main__":A=np.array([  [4,0,0,0],[0,3,0,0],[0,0,2,0],[0,0,0,1]],dtype='int16')A2=np.array([  [4,0,0,0],[0,3,0,0],[0,0,0,0],[0,0,0,0]],dtype='int16')B=np.array([  [3.5,3.5,0,0],[3.5,3.5,0,0],[0,0,1.5,1.5],[0,0,1.5,1.5]],dtype='int16')Aa2norm =A-A2AB2norm =A-Bprint(f"A={A}")print(f"A2={A2}")print(f"B={B}")print(f"Aa2norm={np.linalg.norm(Aa2norm,ord=2)}")print(f"AB2norm={np.linalg.norm(AB2norm,ord=2)}")
#A=[[4 0 0 0]
# [0 3 0 0]
# [0 0 2 0]
# [0 0 0 1]]
#A2=[[4 0 0 0]
# [0 3 0 0]
# [0 0 0 0]
# [0 0 0 0]]
#B=[[3 3 0 0]
# [3 3 0 0]
# [0 0 1 1]
# [0 0 1 1]]
#Aa2norm=2.0
#AB2norm=3.54138126514911

• 结果： $||A-B|{|}_2=3.54,||A-A_2||=2.0\to ||A-B||\ge ||A-A_2||$
• 向量x乘以正交单位矩阵Q后长度不变,正交矩阵相当于将向量旋转，所以长度不变。
  $$\begin{array}{c}||x|{|}_2=x^{T}x=x^T{Q}^{T}Qx=(Qx{)}^{T}Qx=||Qx|{|}_2\end{array}$$
  这就是主成分分析的原理，因为矩阵A里面有很多无用信息，用 $A_k$ 来代替 A

2.1 范数

• 向量$L_1$范数
  $$\begin{array}{c}||V|{|}_1=|v_1|+|v_2|+\cdots +|v_n|\end{array}$$

• 向量$L_2$范数
  $$\begin{array}{c}||V|{|}_2=\sqrt{v_1^2+v_2^2+\cdots +v_n^2}\end{array}$$

• 向量$L_{\infty }$范数
  $$\begin{array}{c}||V|{|}_{\infty }=\max |v_i|\end{array}$$

• 我们假设在二维平面上，我们就三个范数进行图形形象表达：
  
  

• 小结，随着范数越大，图形由原来的菱形膨胀到了正方形，这个正方形就是极限了。这个思路真神奇！！！

• $L_1$函数范数跟向量$L_1$范数一样，通过$L_1$函数可以知道一个函数在指定区间内的体量$L_1$函数范数
  $$\begin{array}{c}L=\sum _{i=1}^n|y_i-f(x_i)|\end{array}$$

• $L_2$函数范数
  $L_2$损失函数表示测量和真实值之差的平方，就是我们之前一直用的最小二乘法。真神奇，居然都对上了，同一个问题，不同的角度。
  $$\begin{array}{c}L=\sum _{i=1}^n(y_i-f(x_i){)}^2\end{array}$$
  矩阵$L_1$范数定义为每一列元素绝对值之和的最大值。具体步骤是：
  1. 对矩阵A的每一列，求每个元素的绝对值之和
  2. 找出所有列和中最大值

• $L_2$矩阵范数定义为矩阵A的最大奇异值，计算步骤：
  1. 计算矩阵A的共轭转置，记为$A^H$,得到$A^{H}A，A{A}^H$
  2. 计算矩阵$A{A}^H,A^{H}A$的特征值，求出平方根后求得最大特征值为$L_2$范数

• Frobenius-norm
  $$\begin{array}{c}||A|{|}_F=\sqrt{{\sigma }_1^2+{\sigma }_2^2+\cdots +{\sigma }_r^2}\end{array}$$

• Nuclear-norm
  $$\begin{array}{c}||A|{|}_N={\sigma }_1+{\sigma }_2+\cdots +{\sigma }_r\end{array}$$

3. $QA=QU\Sigma V^T$

对于矩阵A来说，我们可以左乘以一个正交单位矩阵A，其特征值不变
$$\begin{array}{c}QA=(QU)\Sigma V^T\end{array}$$

4. 主成分分析图像表示

我们来看看最小二乘法的图像，通过求y方向的最小值和来拟合曲线
$$\begin{array}{c}L=\sum _{i=1}^n|y_i-f(x_i)|\to A^{T}A\hat{x}=A^{T}b\to \hat{x}=(A^{T}A{)}^{-1}{A}^{T}b\end{array}$$

• 主成分分析PCA 是通过先减去样本的均值后，根据点到直线的垂直距离来拟合直线。