线性代数一直迷的不行……so
这个博客主要参考MIT18.06和18.065两门课进行记录梳理，构建各个知识点的联系。一定要学过一遍线性代数再看 ，这里着重记录“感觉”，信息密度大，多停多想，不要贪快。没有证明（或许提供了思路）的定理可以当作练习
MIT18.06讲了线性代数，18.065讲了线性代数在数据科学中的诸多用法。本文计算机视觉和机器学习有关的内容还参考了很多Prince的Computer vision: models, learning, and inference的附录C，鼓励大家看原书 ，这是我读过的最清楚的。同时穿插了一些信号、图像方面的知识点
（实际上应该先讲线性空间，但是会不明意义，所以先从几何角度建立线性变换的感觉，强烈建议去看3B1B 线性代数的本质 理解线性变换，无前置基础）T T T T ( v + w ) = T ( v ) + T ( w ) T ( c v ) = c T ( v )
\begin{aligned}
T(v+w)&=T(v)+T(w) \\
T(cv)&=cT(v)
\end{aligned}
T ( v + w ) T ( c v ) = T ( v ) + T ( w ) = c T ( v )
只需要确定T T T
基变换和坐标变换是一种看法，线性变换是另一种看法
两个定理（对几何直觉构建帮助不大，可以先略去）
对于同一个元素，在基α \alpha α x x x β \beta β x ′ x' x ′ β = α P \beta = \alpha P β = α P x = P x ′ x=Px' x = P x ′ α x = β x ′ \alpha x = \beta x' α x = β x ′ P P P
如果β = α P \beta = \alpha P β = α P T T T A , B A,B A , B T ( α ) = α A , T ( β ) = β B T(\alpha)=\alpha A, T(\beta)=\beta B T ( α ) = α A , T ( β ) = β B B = P − 1 A P B=P^{-1}AP B = P − 1 A P β B = T ( β ) = T ( α P ) = T ( α ) P = α A P = β P − 1 α P \beta B = T(\beta)=T(\alpha P) = T(\alpha)P=\alpha AP=\beta P^{-1}\alpha P β B = T ( β ) = T ( α P ) = T ( α ) P = α A P = β P − 1 α P β \beta β B = P − 1 A P B=P^{-1}AP B = P − 1 A P A A A B B B P P P
n n n R n \mathbb R^n R n
对向量加法和数乘封闭的非空集合
注意b b b
以矩阵为元素的线性空间
对于两个子空间S S S U U U d i m ( S ) + d i m ( U ) = d i m ( S + U ) + d i m ( S ∩ U )
dim(S) + dim(U) = dim(S+U) + dim(S\cap U)
d i m ( S ) + d i m ( U ) = d i m ( S + U ) + d i m ( S ∩ U )
列空间Column Space C ( A ) C(A) C ( A ) A x Ax A x
行空间Raw Space C ( A T ) C(A^T) C ( A T )
零空间Null space of a matrix N ( A ) N(A) N ( A ) A x = 0 Ax=0 A x = 0 x x x
左 零空间Left Null space N ( A T ) N(A^T) N ( A T ) x T A = 0 x^TA=0 x T A = 0 x x x A x = 0 Ax=0 A x = 0 C ( A T ) C(A^T) C ( A T ) N ( A ) N(A) N ( A )
对于A ∈ R m × n A\in \mathbb R^{m\times n} A ∈ R m × n r r r r r r C = [ c v 1 , ⋯ , c v r ] C=[c_{v_1}, \cdots, c_{v_r}] C = [ c v 1 , ⋯ , c v r ] A A A C C C A = C R A=CR A = C R C ∈ R m × r , R ∈ R r × n C\in \mathbb R^{m\times r},\ R \in \mathbb R^{r\times n} C ∈ R m × r , R ∈ R r × n A A A R R R r r r r r r 行 秩 = 列 秩 = r 行秩=列秩=r 行 秩 = 列 秩 = r A = C R A=CR A = C R C C C R R R
从C C C R R R A A A r a n k [ A B ] ⩽ min { r a n k [ A ] , r a n k [ B ] } rank[AB]\leqslant \min\{rank[A], rank[B] \} r a n k [ A B ] ⩽ min { r a n k [ A ] , r a n k [ B ] }
A x = b Ax=b A x = b b b b A A A
N ( B A ) = N ( A ) N(BA)=N(A) N ( B A ) = N ( A ) B B B
行空间和列空间维度都为r r r
行空间与零空间正交，所以零空间N ( A ) N(A) N ( A ) n − r n-r n − r A x = 0 Ax=0 A x = 0 N ( A T ) N(A^T) N ( A T ) m − r m-r m − r
对于向量a a a b b b b b b a a a a a T b a T a = a a T a T a b = P b (1) a\frac{a^Tb}{a^T a}=\frac{aa^T}{a^Ta}b=Pb \tag{1} a a T a a T b = a T a a a T b = P b ( 1 ) P P P
求解A x = b Ax=b A x = b b b b C ( A ) C(A) C ( A ) A x ^ = p A \hat x=p A x ^ = p p p p b b b C ( A ) C(A) C ( A ) b − A x ^ b - A \hat x b − A x ^ C ( A ) C(A) C ( A ) A T ( b − A x ^ ) = 0 A^T(b-A\hat x)=0 A T ( b − A x ^ ) = 0 A T A x ^ = A T b A^TA\hat x=A^T b A T A x ^ = A T b
所以x ^ = ( A T A ) − 1 A T b \hat x = (A^TA)^{-1}A^T b x ^ = ( A T A ) − 1 A T b p = A x ^ = A ( A T A ) − 1 A T b = P b p=A\hat x=A (A^TA)^{-1}A^T b=Pb p = A x ^ = A ( A T A ) − 1 A T b = P b P = A ( A T A ) − 1 A T P=A(A^TA)^{-1}A^T P = A ( A T A ) − 1 A T x ^ \hat x x ^ A A A
注意P P P P T = P , P 2 = P P^T=P, P^2=P P T = P , P 2 = P P 2 = P P^2=P P 2 = P
因为b = p + e b=p+e b = p + e e e e p = P b p=Pb p = P b e = ( I − P ) b e=(I-P)b e = ( I − P ) b ( I − P ) 2 = I − P , ( I − P ) T = I − P (I-P)^2=I-P, (I-P)^T=I-P ( I − P ) 2 = I − P , ( I − P ) T = I − P P P P
A T A A^TA A T A A A A r ( A T A ) = r ( A ) r(A^TA)=r(A) r ( A T A ) = r ( A )
A x = b Ax=b A x = b x ^ = arg min x [ ( A x − b ) T ( A x − b ) ] = arg min x [ x T A T A x − 2 x T A T b ]
\begin{aligned}
\hat x &= \argmin_x [(Ax-b)^T(Ax-b)] \\
&= \argmin_x [x^TA^TAx - 2x^TA^Tb]
\end{aligned}
x ^ = x a r g m i n [ ( A x − b ) T ( A x − b ) ] = x a r g m i n [ x T A T A x − 2 x T A T b ] x x x x = ( A T A ) − 1 A T b
x=(A^TA)^{-1}A^Tb
x = ( A T A ) − 1 A T b A A A x x x
记训练集标注为t = ( t 1 , . . . , t N ) T \bf t = (t_1, ..., t_N)^T t = ( t 1 , . . . , t N ) T R N \mathbb R^N R N S \mathcal{S} S
这里线性回归的基可以是带核φ ( X ) \varphi (X) φ ( X ) i i i φ i ( X ) \varphi_i(X) φ i ( X ) φ i \varphi_i φ i i i i X X X
注意误差向量垂直于S \mathcal{S} S S S S
之前只知道多重共线性不好，到底哪里不好一直说不清楚。这里把它讲清楚。参数值爆炸 。Φ ∈ R N × M \Phi \in \mathbb{R}^{N \times M} Φ ∈ R N × M M M M r ( ⋅ ) r(\cdot) r ( ⋅ ) r ( Φ ) < M r(\Phi)<M r ( Φ ) < M r ( Φ ) = r ( Φ T Φ ) = r ( Φ Φ T ) r(\Phi) = r(\Phi^T \Phi) = r(\Phi \Phi^T) r ( Φ ) = r ( Φ T Φ ) = r ( Φ Φ T ) Φ x = 0 \Phi x =0 Φ x = 0 Φ T Φ x = 0 \Phi^T \Phi x= 0 Φ T Φ x = 0 r ( Φ ) r(\Phi) r ( Φ ) M M M Φ T Φ \Phi^T \Phi Φ T Φ Φ T Φ \Phi^T \Phi Φ T Φ 参数闭式解( Φ T Φ ) − 1 Φ T t (\Phi^T \Phi)^{-1} \Phi^T \bf t ( Φ T Φ ) − 1 Φ T t 。从几何角度解释，即两个基向量方向非常近，那么为了表达出与这两个基向量几乎垂直的方向上的位置，这两个向量需要不断抵消，系数会增长非常快！
这里如果无法求逆，则可以求伪逆，参考后文
d e t [ I ] = 1 det[I]=1 d e t [ I ] = 1 交换两行，行列式取反
a) 某一行乘k k k k k k d e t [ ⋮ a i 1 + a i 2 ⋮ ] = d e t [ ⋮ a i 1 ⋮ ] d e t [ ⋮ a i 2 ⋮ ] det \begin{bmatrix}\vdots \\ a_{i_1}+a_{i_2} \\ \vdots\end{bmatrix}=det \begin{bmatrix}\vdots \\ a_{i_1} \\ \vdots\end{bmatrix}det \begin{bmatrix}\vdots \\ a_{i_2} \\ \vdots\end{bmatrix} d e t ⎣ ⎢ ⎢ ⎡ ⋮ a i 1 + a i 2 ⋮ ⎦ ⎥ ⎥ ⎤ = d e t ⎣ ⎢ ⎢ ⎡ ⋮ a i 1 ⋮ ⎦ ⎥ ⎥ ⎤ d e t ⎣ ⎢ ⎢ ⎡ ⋮ a i 2 ⋮ ⎦ ⎥ ⎥ ⎤
用这三条性质能推出剩下一大堆东西，包括基本算法和其他性质，都能推出来，列几个常用的性质
d e t [ A T ] = d e t [ A ] det[A^T]=det[A] d e t [ A T ] = d e t [ A ]
d e t [ A B ] = d e t [ A ] d e t [ B ] det[AB]=det[A]det[B] d e t [ A B ] = d e t [ A ] d e t [ B ] d e t [ A − 1 ] = 1 / d e t [ A ] det[A^{-1}]=1/det[A] d e t [ A − 1 ] = 1 / d e t [ A ]
不满秩矩阵的行列式为0。由此可证d e t [ ⋮ a i 1 ⋮ a i 2 ⋮ ] = d e t [ ⋮ a i 1 ⋮ a i 1 + a i 2 ⋮ ] det \begin{bmatrix}\vdots \\ a_{i_1} \\ \vdots \\ a_{i_2} \\\vdots\end{bmatrix}=det \begin{bmatrix}\vdots \\ a_{i_1} \\ \vdots \\ a_{i_1}+a_{i_2} \\\vdots\end{bmatrix} d e t ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ⋮ a i 1 ⋮ a i 2 ⋮ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ = d e t ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ ⋮ a i 1 ⋮ a i 1 + a i 2 ⋮ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤
可以证明体积也满足上述三个重要性质。于是得证。（3b不是很好证）3B1B——线性代数的本质
三阶行列式即混合积：a × ( b ⋅ c ) = d e t [ [ a , b , c ] ] a\times (b\cdot c)=det[[a,b,c]] a × ( b ⋅ c ) = d e t [ [ a , b , c ] ]
对于方阵A ∈ R n × n A \in \mathbb{R}^{n\times n} A ∈ R n × n d e t [ A ] = ∑ n ! terms ± a 1 α a 2 β ⋯ a n ω
det[A]=\sum_{n! \text{ terms}} \pm a_{1\alpha}a_{2\beta}\cdots a_{n\omega}
d e t [ A ] = n ! terms ∑ ± a 1 α a 2 β ⋯ a n ω ( α , β , γ , ⋯ , ω ) = perm of ( 1 , 2 , ⋯ , n )
(\alpha, \beta,\gamma, \cdots,\omega) = \text{perm of } (1,2,\cdots,n)
( α , β , γ , ⋯ , ω ) = perm of ( 1 , 2 , ⋯ , n ) d e t [ A ] = a 11 C 11 + a 12 C 12 + ⋯ + a 1 n C 1 n
det[A]=a_{11}C_{11} + a_{12} C_{12} + \cdots + a_{1n} C_{1n}
d e t [ A ] = a 1 1 C 1 1 + a 1 2 C 1 2 + ⋯ + a 1 n C 1 n C i j C_{ij} C i j i i i j j j
A C T = d e t [ A ] I AC^T=det[A]I A C T = d e t [ A ] I C C C C T C^T C T
伴随矩阵和逆矩阵只差一个系数。然而，伴随矩阵对不可逆的矩阵也有定义，并且不需要用到除法（摘自百度百科）
A x = b
Ax=b
A x = b x = A − 1 b = 1 d e t [ A ] C T b
x=A^{-1}b=\frac{1}{det[A]}C^Tb
x = A − 1 b = d e t [ A ] 1 C T b C T b C^Tb C T b x i = d e t [ B i ] d e t [ A ] B i = [ A ⋅ 1 , ⋯ , A ⋅ ( i − 1 ) , b , A ⋅ ( i + 1 ) , ⋯ , A ⋅ n ]
x_i=\frac{det[B_i]}{det[A]} \\
B_i = \begin{bmatrix} A_{\cdot 1}, \cdots, A_{\cdot (i-1)}, b, A_{\cdot (i+1)}, \cdots, A_{\cdot n} \end{bmatrix}
x i = d e t [ A ] d e t [ B i ] B i = [ A ⋅ 1 , ⋯ , A ⋅ ( i − 1 ) , b , A ⋅ ( i + 1 ) , ⋯ , A ⋅ n ] 3B1B——线性代数的本质
Q Q Q Q T Q = I , Q − 1 = Q T Q^TQ=I,Q^{-1}=Q^T Q T Q = I , Q − 1 = Q T 博客
复空间的正交矩阵叫做酉矩阵unitary，即满足A ˉ T A = I \bar A^TA=I A ˉ T A = I
正交矩阵特征值绝对值都为1，因为( Q x ) ‾ T Q x = λ ˉ λ x ˉ T x \overline {(Qx)}^TQx=\bar \lambda\lambda \bar x^Tx ( Q x ) T Q x = λ ˉ λ x ˉ T x x ˉ T x > 0 \bar x^T x>0 x ˉ T x > 0 ∥ λ ∥ = 1 \|\lambda\|=1 ∥ λ ∥ = 1 I I I
注意：如果Q T Q = I Q^TQ=I Q T Q = I Q Q Q Q Q T = I QQ^T=I Q Q T = I
正交矩阵行列式绝对值为1，所以线性变换体积不变。左乘的线性变换效果是可看作是一种反演（改变手性）+旋转 ，这个在SVD中会有感受。行列式为1时，为旋转矩阵 ，为-1则包含了反演
距离不变
夹角不变
上述两条也能推出内积不变 ，即x 1 T x 2 = ( A x 1 ) T ( A x 2 ) x_1^Tx_2=(Ax_1)^T(Ax_2) x 1 T x 2 = ( A x 1 ) T ( A x 2 )
即正交对称阵r T = r r^T=r r T = r
注意这意味着特征值都为实数±1，且特征向量都存在。这是一个不带旋转的变换，如果带旋转的话不可能特征值都为±1
Q Q Q R R R Q Q Q q 1 , q 2 , ⋯ , q n q_1,q_2,\cdots, q_n q 1 , q 2 , ⋯ , q n
信号处理中有一大类变换是线性变换，其中的部分变换是正交变换，可以看作是对原始信号x x x y = A T x y=A^Tx y = A T x A A A A A A A T A^T A T
傅里叶变换，A A A a p q = e 2 π i p q / N a_{pq}=e^{2\pi i pq / N} a p q = e 2 π i p q / N p , q p,q p , q A A A A ˉ T \bar A^T A ˉ T
小波变换。参考我的另一篇博客：小波变换——公式整理和简单介绍
对于方阵A ∈ R n × n A \in \mathbb{R}^{n\times n} A ∈ R n × n A v = λ v
Av=\lambda v
A v = λ v v v v λ \lambda λ
∑ λ = t r [ A ] \sum \lambda=tr[A] ∑ λ = t r [ A ] ∏ λ = d e t [ A ] \prod \lambda = det[A] ∏ λ = d e t [ A ] 对称矩阵特征值一定为实数，反对称矩阵则为零或纯虚数 ；其他矩阵介于对称与反对称之间
A A A A T A^T A T
A = V Λ V − 1
A=V\Lambda V^{-1}
A = V Λ V − 1 V V V Λ \Lambda Λ 假设n n n ，即S S S
A k = V Λ k V − 1 A^k=V \Lambda ^k V^{-1} A k = V Λ k V − 1 A k A^k A k k k k
A k u = ( V Λ k ) ( V − 1 u ) = ( λ 1 v 1 , ⋯ , λ n v n ) ( c 1 , ⋯ , c n ) T = ∑ i = 1 n c i λ i k v i A^k u=(V\Lambda^k)( V^{-1}u)=(\lambda_1 v_1,\cdots,\lambda_n v_n)(c_1,\cdots,c_n)^T=\sum_{i=1}^{n}c_i \lambda_i^k v^i A k u = ( V Λ k ) ( V − 1 u ) = ( λ 1 v 1 , ⋯ , λ n v n ) ( c 1 , ⋯ , c n ) T = ∑ i = 1 n c i λ i k v i 若A A A n n n
特征向量组唯一当且仅当所有的特征值都是唯一的
给定特征值和特征向量唯一确定一个矩阵，可以从几何角度感知，参考3B1B线性代数本质
如果A A A A A A n n n A = Q Λ Q T
A = Q\Lambda Q^T
A = Q Λ Q T
上述实对称矩阵可以放松为A = A ˉ T A=\bar A^T A = A ˉ T A ˉ \bar A A ˉ A A A
如果A A A
实际上当A A A A A ˉ T = A ˉ T A A\bar A^T=\bar A^TA A A ˉ T = A ˉ T A
Q Q Q A A A A A A v i v_i v i λ i \lambda_i λ i A u = Q Λ Q T u Au=Q\Lambda Q^T u A u = Q Λ Q T u Q T Q^T Q T u u u Λ \Lambda Λ Q Q Q
Λ \Lambda Λ
矩阵奇异当且仅当有0特征值
所有特征值为正，则正定；不为负，则半正定；不为正，则半负定；为负，则负定。感受一下正负定对线性变换的影响
实对称矩阵的特征分解：S = ( Q Λ ) Q T = ∑ i λ i q i q i T
S=(Q\Lambda) Q^T = \sum_i \lambda_i q_i q_i^T
S = ( Q Λ ) Q T = i ∑ λ i q i q i T
且有S q i = ( ∑ i λ i q i q i T ) q i = λ q i
Sq_i =( \sum_i \lambda_i q_i q_i^T) q_i= \lambda q_i
S q i = ( i ∑ λ i q i q i T ) q i = λ q i
马尔科夫矩阵A A A
每列的和为1
所有元素大于0
物理意义是列到行概率转移。
上述定义1保证了1是特征值，原因在于A − I A-I A − I A ∞ u 0 A^{\infty}u_0 A ∞ u 0
两条定义共同保证了特征值不大于1. 注意马尔科夫矩阵在无限次放后的稳态性，A n = V Λ k V − 1 A^n=V \Lambda ^k V^{-1} A n = V Λ k V − 1
A ∼ B ⇔ A = M B M − 1 A \sim B \Leftrightarrow A=MBM^{-1} A ∼ B ⇔ A = M B M − 1
相似矩阵特征值相同。对于A x = λ x Ax=\lambda x A x = λ x M − 1 A M M − 1 x = λ M − 1 x M^{-1}AMM^{-1}x=\lambda M^{-1}x M − 1 A M M − 1 x = λ M − 1 x B ( M − 1 x ) = λ M − 1 x B(M^{-1}x)=\lambda M^{-1}x B ( M − 1 x ) = λ M − 1 x A A A λ \lambda λ B B B
上述命题反过来不成立，如果特征值有重根，特征向量个数有可能不同。当特征向量不够的时候，甚至无法对角化。例如[ 4 1 0 4 ]
\begin{bmatrix}
4 & 1\\ 0 & 4
\end{bmatrix}
[ 4 0 1 4 ]
每个矩阵都像相似于一个Jordan矩阵，Jordan矩阵由Jordan块组成。而Jordan块数则等于不同的特征向量数。这里仅mark一下，不再展开（等用到时再详细了解吧）
A B AB A B B A BA B A B ( A B ) B − 1 = B A B(AB)B^{-1}=BA B ( A B ) B − 1 = B A B B B A T A , A A T A^TA, AA^T A T A , A A T
一种特殊的实对称矩阵。几个等价定义：
∀ x ≠ 0 , x T S x > 0 \forall x\neq 0, x^TSx>0 ∀ x = 0 , x T S x > 0
特征值全为正 ，即S = Q Λ Q T S=Q\Lambda Q^T S = Q Λ Q T Λ \Lambda Λ
主元pivots全为正 。主元实际上和LU分解，和二次型配方都是一一对应的
顺序主子式leading determinants全为正 。注意主元和顺序主子式的关系，前k k k k k k
S = A T A S=A^TA S = A T A A A A A A A N ( A ) N(A) N ( A ) 所以协方差总是半正定 ，就像是方差总是正数
性质：
如果A , B A,B A , B A + B A+B A + B
正定矩阵可逆，且逆矩阵正定
说明：
二次型x T S x x^TSx x T S x x x x
正定时二次型是凸函数convex function
对任意m × n m\times n m × n A A A A = U Σ V T
A=U\Sigma V^T
A = U Σ V T U U U m m m Σ \Sigma Σ m × n m\times n m × n V V V n n n Σ \Sigma Σ 对角元素沿着从大到小的顺序排 ，在某些情况下唯一。参考：可逆矩阵的奇异值分解唯一吗？存在奇异值分解唯一的矩阵吗？
性质：A T A = V ( Σ T Σ ) V T A^TA=V(\Sigma^T\Sigma)V^T A T A = V ( Σ T Σ ) V T A A T = U ( Σ Σ T ) U T AA^T=U(\Sigma\Sigma^T)U^T A A T = U ( Σ Σ T ) U T
如果A A A
如果r a n k [ A ] = r rank[A]=r r a n k [ A ] = r A A A C ( A T ) C(A^T) C ( A T ) r r r 同构映射 到列空间C ( A ) C(A) C ( A ) r r r C ( A ) C(A) C ( A ) C ( A T ) C(A^T) C ( A T ) A [ v 1 , v 2 , ⋯ , v r ] = [ u 1 , u 2 , ⋯ , u r ] d i a g [ σ 1 , σ 2 , ⋯ , σ r ] (2)
A[ v_1, v_2, \cdots , v_r] =[u_1,u_2,\cdots,u_r]diag[\sigma_1, \sigma_2, \cdots, \sigma_r] \tag{2}
A [ v 1 , v 2 , ⋯ , v r ] = [ u 1 , u 2 , ⋯ , u r ] d i a g [ σ 1 , σ 2 , ⋯ , σ r ] ( 2 ) A V = U Σ
AV=U\Sigma
A V = U Σ V V V v r + 1 , ⋯ , v n v_{r+1}, \cdots, v_n v r + 1 , ⋯ , v n A A A N ( A ) N(A) N ( A ) n − r n-r n − r U U U N ( A T ) N(A^T) N ( A T ) i > r i>r i > r Σ i i = 0 \Sigma_{ii} = 0 Σ i i = 0 r r r
如何找出V V V r r r A T A A^TA A T A A T A = V ( Σ T Σ ) V T A^TA=V(\Sigma^T \Sigma)V^T A T A = V ( Σ T Σ ) V T V V V A T A A^TA A T A Σ \Sigma Σ
σ i 2 v i = A T ( A v i ) \sigma_i^2 v_i=A^T(Av_i) σ i 2 v i = A T ( A v i ) v i v_i v i C ( A T ) C(A^T) C ( A T )
如何找出U U U r r r u i = A v i σ i u_i=\frac{Av_i}{\sigma_i} u i = σ i A v i
可以看出u i u_i u i A A A
可以证明这r r r r r r V r ∈ R n × r , U r ∈ R m × r , Σ r ∈ R r × r V_r \in \mathbb R^{n\times r}, \ U_r \in \mathbb R^{m\times r},\ \Sigma_r \in \mathbb R^{r\times r} V r ∈ R n × r , U r ∈ R m × r , Σ r ∈ R r × r U r = A V r Σ r − 1 U r T U r = ( A V r Σ r − 1 ) T A V r Σ r − 1 = Σ r − 1 V r T ( V Σ T Σ V T ) V r Σ r − 1 = ( Σ r − 1 V r T V Σ T ) ( Σ r − 1 V r T V Σ T ) T U_r=AV_r \Sigma_r^{-1} \\ U_r^T U_r = (AV_r \Sigma_r^{-1})^TAV_r \Sigma_r^{-1}=\Sigma_r^{-1} V_r^T(V\Sigma^T \Sigma V^T) V_r \Sigma_r^{-1}=(\Sigma_r^{-1}V_r^TV\Sigma^T)( \Sigma_r^{-1} V_r^TV\Sigma^T)^T U r = A V r Σ r − 1 U r T U r = ( A V r Σ r − 1 ) T A V r Σ r − 1 = Σ r − 1 V r T ( V Σ T Σ V T ) V r Σ r − 1 = ( Σ r − 1 V r T V Σ T ) ( Σ r − 1 V r T V Σ T ) T V r T V = I r × n V_r^TV=I_{r\times n} V r T V = I r × n Σ r − 1 I r × n = Σ r − 1 \Sigma_r^{-1}I_{r\times n} = \Sigma_r^{-1} Σ r − 1 I r × n = Σ r − 1 Σ r − 1 Σ T = I r × r \Sigma_r^{-1}\Sigma^T=I_{r\times r} Σ r − 1 Σ T = I r × r U r T U r = I r × r U_r^TU_r=I_{r\times r} U r T U r = I r × r r r r 一定可以构造出来的
注意V V V U U U ，
U : [ C ( A ) , N ( A T ) ] U: [C(A), N(A^T)] U : [ C ( A ) , N ( A T ) ] V ： [ C ( A T ) , N ( A ) ] V： [C(A^T), N(A)] V ： [ C ( A T ) , N ( A ) ]
从矩阵分解的角度揭示了矩阵从四个记本子空间中如何生成的，这也是SVD各种秒用的原理之一
从线性变换的角度看奇异值分解揭示了矩阵的组成方法， 如下图所示：
V T V^T V T
L L L L L L
U U U
只改变某部分，对最终矩阵A 3 A_3 A 3
σ \sigma σ
个数：m i n ( m , n ) min(m, n) m i n ( m , n )
非0奇异值的数量是矩阵的秩
最小奇异值与最大奇异值之比反映了可逆性的度量，称为条件数
根据行列式的定义，知，奇异值的乘积为行列式（因为只有L L L U U U V V V
A − 1 = V L − 1 U T
A^{-1}=VL^{-1} U^T
A − 1 = V L − 1 U T
A = Q S
A=QS
A = Q S Q Q Q S S S A = Q V Λ V ˉ T
A=QV\Lambda \bar V^T
A = Q V Λ V ˉ T Q V = U QV=U Q V = U V V V
关于求S S S A ˉ T A = S ˉ T Q ˉ T Q S = S 2 \bar A^TA=\bar S^T \bar Q^T QS=S^2 A ˉ T A = S ˉ T Q ˉ T Q S = S 2 矩阵开方 的知识，正规矩阵都可以开方，S = A ˉ T A = V Λ 2 V ˉ T = V Λ V ˉ T S=\sqrt {\bar A^TA} = \sqrt {V\Lambda ^2 \bar V^T}=V\Lambda \bar V^T S = A ˉ T A = V Λ 2 V ˉ T = V Λ V ˉ T
这里插入矩阵范数，以便应用部分使用
满足这三条的叫做范数
∥ A ∥ ⩾ 0 \|A\| \geqslant 0 ∥ A ∥ ⩾ 0 ∥ c A ∥ = ∣ c ∣ ∥ A ∥ \|cA\|=|c| \|A\| ∥ c A ∥ = ∣ c ∣ ∥ A ∥ ∥ A + B ∥ ⩽ ∥ A ∥ + ∥ B ∥ \|A+B\| \leqslant \|A\|+\|B\| ∥ A + B ∥ ⩽ ∥ A ∥ + ∥ B ∥
如果定义∥ A ∥ = ( ∑ i , j a i , j p ) 1 / p \|A\|=(\sum_{i,j} a_{i,j}^p)^{1/p} ∥ A ∥ = ( ∑ i , j a i , j p ) 1 / p p < 1 p<1 p < 1 p ⩾ 1 p\geqslant 1 p ⩾ 1
∥ A ∥ 2 = max x ∥ A x ∥ 2 ∥ x ∥ 2 = σ 1
\|A\|_2=\max_x\frac{\|Ax\|_2}{\|x\|_2}=\sigma_1
∥ A ∥ 2 = x max ∥ x ∥ 2 ∥ A x ∥ 2 = σ 1 ∥ x ∥ 2 = 1 \|x\|_2=1 ∥ x ∥ 2 = 1 x = ∑ i λ i v i x=\sum_i {\lambda_i}v_i x = ∑ i λ i v i ∑ i λ i 2 = 1 \sum_i \lambda_i^2=1 ∑ i λ i 2 = 1 A x = ∑ i λ i σ i u i Ax=\sum_i \lambda_i\sigma_i u_i A x = ∑ i λ i σ i u i ∥ A x ∥ 2 = ∑ i λ i 2 σ i 2 ⩽ σ 1 \|Ax\|_2=\sqrt{\sum_{i} \lambda_i^2\sigma_i^2}\leqslant \sigma_1 ∥ A x ∥ 2 = ∑ i λ i 2 σ i 2 ⩽ σ 1
∥ A ∥ F \|A\|_F ∥ A ∥ F ∥ A ∥ F = t r [ A T A ] ∣ = t r [ V Σ T Σ V T ] \|A\|_F=\sqrt {tr[A^TA]|}=\sqrt {tr[V\Sigma^T \Sigma V^T]} ∥ A ∥ F = t r [ A T A ] ∣ = t r [ V Σ T Σ V T ] 迹的轮换对称性 t r [ A B ] = t r [ B A ] tr[AB]=tr[BA] t r [ A B ] = t r [ B A ] ∥ A ∥ F = t r [ V T V Σ T Σ ] = ∑ i = 1 r σ 2 \|A\|_F=\sqrt {tr[V^TV\Sigma^T \Sigma ]}=\sqrt {\sum_{i=1}^r \sigma^2} ∥ A ∥ F = t r [ V T V Σ T Σ ] = i = 1 ∑ r σ 2
∥ A ∥ N = ∑ i = 1 r σ i
\|A\|_{N}=\sum_{i=1}^r \sigma_i
∥ A ∥ N = i = 1 ∑ r σ i
Q A = ( Q U ) Σ V T QA=(QU)\Sigma V^T Q A = ( Q U ) Σ V T Q A QA Q A Σ \Sigma Σ Q Q Q
这三个范数相等
基追踪问题Basis persuitm i n ∥ x ∥ p s . t . A x = b p = 1 o r 2
min\|x\|_p\qquad s.t. \quad Ax=b \\
p=1\ or\ 2
m i n ∥ x ∥ p s . t . A x = b p = 1 o r 2
这里矩阵可以是一幅图像或DataFrame型数据。如果r a n k [ A ] = r rank[A]=r r a n k [ A ] = r A = U Σ V T = ∑ i = 1 r σ i u i v i T A=U\Sigma V^T = \sum_{i=1}^r \sigma_i u_i v_i^T A = U Σ V T = i = 1 ∑ r σ i u i v i T σ \sigma σ σ \sigma σ ∥ u i v i T ∥ F = t r [ v i u i T u i v i T ] = t r [ v i v i T ] = t r [ v i T v i ] = 1 \left\|u_i v_i ^T \right\|_F=tr[v_i u_i^T u_i v_i^T]=tr[v_i v_i^T]=tr[v_i^T v_i]=1 ∥ ∥ u i v i T ∥ ∥ F = t r [ v i u i T u i v i T ] = t r [ v i v i T ] = t r [ v i T v i ] = 1 σ \sigma σ k k k σ \sigma σ A A A A k = U k Σ k V k T A_k=U_k \Sigma_k V_k^T A k = U k Σ k V k T
Eckart-Young定理A k = U k Σ k V k T A_k=U_k \Sigma_k V_k^T A k = U k Σ k V k T k k k ∥ A − B ∥ ⩾ ∥ A − A k ∥
\|A-B \| \geqslant\|A-A_k\|
∥ A − B ∥ ⩾ ∥ A − A k ∥ A k A_k A k k k k A A A
主成分分析：X = [ x 1 , ⋯ , x n ] ∈ R m × n X=[x_1,\cdots,x_n] \in \mathbb R^{m\times n} X = [ x 1 , ⋯ , x n ] ∈ R m × n m m m n n n 线性变换 W ∈ R k × m W \in \mathbb R^{k\times m} W ∈ R k × m k k k W X WX W X k k k k k k X k X_k X k X X X X k = U k Σ k V k T X_k=U_k \Sigma_k V_k^T X k = U k Σ k V k T X k X_k X k
降维：实际上可以取U k T U_k^T U k T U k T X U_k^T X U k T X R k × n \mathbb R^{k\times n} R k × n u i T x u_i^Tx u i T x i i i
升维：取矩阵U k U_k U k U k ( U k T X ) = U k ( U k T U ) Σ V T = U k I k × m Σ V T = U k [ Σ k , 0 k × ( n − k ) ] V T = U k Σ k V k T = X k U_k(U_k^TX)=U_k(U_k^TU)\Sigma V^T=U_kI_{k\times m}\Sigma V^T=U_k [\Sigma_{k}, \textbf{0}_{k\times (n-k)}]V^T=U_k\Sigma_kV_k^T=X_k U k ( U k T X ) = U k ( U k T U ) Σ V T = U k I k × m Σ V T = U k [ Σ k , 0 k × ( n − k ) ] V T = U k Σ k V k T = X k
所以这样的变换是成立的，即对X X T XX^T X X T k k k u 1 , ⋯ , u r u_1, \cdots, u_r u 1 , ⋯ , u r X X X X ^ = X − μ m 1 1 × n \hat X=X-\mu_{m} \textbf 1_{1\times n} X ^ = X − μ m 1 1 × n X ^ 1 n = 0 \hat X \textbf 1_{n}=0 X ^ 1 n = 0 PCA ，注意X ^ X ^ T / ( m − 1 ) \hat X \hat X^T/(m-1) X ^ X ^ T / ( m − 1 )
主方向问题：arg max b ∥ A b ∥ s . t . ∥ b ∥ = 1
\argmax_b \|Ab\| \qquad s.t. \quad \|b\|=1
b a r g m a x ∥ A b ∥ s . t . ∥ b ∥ = 1
根据限制，b b b V T V^T V T X = ( 1 , 0 , . . . , 0 ) X=(1, 0, ..., 0) X = ( 1 , 0 , . . . , 0 ) ( V T ) − 1 X = V X (V^T)^{-1}X=VX ( V T ) − 1 X = V X V V V
同理，最小值方向为V V V
寻找正交矩阵Ω \Omega Ω Ω ^ = arg min Ω ∥ Ω A − B ∥ F
\hat \Omega =\argmin_\Omega \left\|\Omega A-B \right\|_F
Ω ^ = Ω a r g m i n ∥ Ω A − B ∥ F Ω ^ = arg min Ω t r [ ( Ω A − B ) T ( Ω A − B ) ] = arg max Ω t r [ Ω T B A T ]
\begin{aligned}
\hat \Omega &=\argmin_\Omega tr\left[(\Omega A-B)^T(\Omega A-B)\right] \\
&=\argmax_\Omega tr \left[\Omega^TBA^T\right]
\end{aligned}
Ω ^ = Ω a r g m i n t r [ ( Ω A − B ) T ( Ω A − B ) ] = Ω a r g m a x t r [ Ω T B A T ] B A T = U L V T BA^T=ULV^T B A T = U L V T Ω ^ = arg max Ω t r [ Ω T U L V T ] = arg max Ω t r [ V T Ω T U L ]
\begin{aligned}
\hat \Omega &=\argmax_\Omega tr\left[\Omega^T ULV^T\right]\\
&= \argmax_\Omega tr\left[V^T\Omega^T UL\right]
\end{aligned}
Ω ^ = Ω a r g m a x t r [ Ω T U L V T ] = Ω a r g m a x t r [ V T Ω T U L ] t r [ V T Ω T U L ] = t r [ Z L ] = ∑ i = 1 I z i i l i i
tr \left[V^T\Omega^T UL \right] = tr \left[ZL \right] = \sum_{i=1}^I z_{ii}l_{ii}
t r [ V T Ω T U L ] = t r [ Z L ] = i = 1 ∑ I z i i l i i Z = V T Ω T U Z=V^T\Omega^TU Z = V T Ω T U Z Z Z Z = I Z=I Z = I Ω ^ = U V T
\hat \Omega = UV^T
Ω ^ = U V T
本问题的一个特殊形式是给定方阵B B B Ω \Omega Ω Ω ^ = arg min Ω ∥ Ω − B ∥ F
\hat \Omega=\argmin_\Omega \|\Omega - B\|_F
Ω ^ = Ω a r g m i n ∥ Ω − B ∥ F Ω ^ = U V T \hat\Omega=UV^T Ω ^ = U V T B = U L V T B=ULV^T B = U L V T
对于A ∈ R m × n A \in \mathbb R ^{m\times n} A ∈ R m × n
左逆: ( A T A ) − 1 A T ∈ R n × m (A^TA)^{-1}A^T \in \mathbb R^{n\times m} ( A T A ) − 1 A T ∈ R n × m A T A A^TA A T A r a n k [ A ] = n rank[A]=n r a n k [ A ] = n
右逆: A T ( A A T ) − 1 ∈ R n × m A^T(AA^T)^{-1} \in \mathbb R^{n\times m} A T ( A A T ) − 1 ∈ R n × m r a n k [ A T ] = r a n k [ A ] = m rank[A^T]=rank[A]=m r a n k [ A T ] = r a n k [ A ] = m
考虑行空间和列空间，从行空间中拿元素x x x A x Ax A x x x x A x Ax A x 能构成一一对应 ，两个空间维度相同。证明：
对于x 1 , x 2 ∈ C ( A T ) x_1,x_2 \in C(A^T) x 1 , x 2 ∈ C ( A T ) A x 1 ≠ A x 2 Ax_1\neq Ax_2 A x 1 = A x 2 A ( x 1 − x 2 ) = 0 A(x_1-x_2)=0 A ( x 1 − x 2 ) = 0 x 1 − x 2 x_1-x_2 x 1 − x 2 N ( A ) N(A) N ( A )
另外只取x ∈ C ( A T ) , A x x\in C(A^T), Ax x ∈ C ( A T ) , A x x ′ ∈ R n x'\in \mathbb R^{n} x ′ ∈ R n A x ′ Ax' A x ′ x ′ = x + x N x'=x+x_N x ′ = x + x N x ∈ C ( A T ) , x N ∈ N ( A ) x\in C(A^T),x_N \in N(A) x ∈ C ( A T ) , x N ∈ N ( A ) A x ′ = A x + A x N = A x Ax'=Ax+Ax_N=Ax A x ′ = A x + A x N = A x A x Ax A x
所以双射，即一一对应成立。
此时限制在这两空间上的逆就是伪逆，即对于A x = y Ax=y A x = y A + A^+ A + x = A + y = ( A + A ) x x=A^{+}y=(A^+A)x x = A + y = ( A + A ) x A = U Σ V T A=U\Sigma V^T A = U Σ V T U , V U,V U , V Σ + \Sigma^+ Σ + 1 / σ 1 , 1 / σ 2 , ⋯ , 1 / σ r , 0 , ⋯ , 0 1/\sigma_1, 1/\sigma_2, \cdots, 1/\sigma_r, 0, \cdots,0 1 / σ 1 , 1 / σ 2 , ⋯ , 1 / σ r , 0 , ⋯ , 0 Σ ∈ R m × n , Σ + ∈ R n × m \Sigma \in \mathbb R^{m\times n},\Sigma^+ \in \mathbb R^{n\times m} Σ ∈ R m × n , Σ + ∈ R n × m A + = V Σ + U T A^+=V\Sigma^+ U^T A + = V Σ + U T
A V = U Σ = [ u 1 σ 1 , ⋯ , u r σ r , 0 , ⋯ , 0 ] AV=U\Sigma=[u_1\sigma_1, \cdots, u_r\sigma_r, 0,\cdots,0] A V = U Σ = [ u 1 σ 1 , ⋯ , u r σ r , 0 , ⋯ , 0 ] A A A v r + 1 , ⋯ , v n v_{r+1}, \cdots, v_n v r + 1 , ⋯ , v n v r + 1 , ⋯ , v n v_{r+1},\cdots,v_n v r + 1 , ⋯ , v n N ( A ) N(A) N ( A ) A + U = V Σ + = [ v 1 / σ 1 , ⋯ , u r / σ r , 0 , ⋯ , 0 ] A^+U=V\Sigma^+=[v_1/\sigma_1, \cdots, u_r/\sigma_r, 0, \cdots, 0] A + U = V Σ + = [ v 1 / σ 1 , ⋯ , u r / σ r , 0 , ⋯ , 0 ] A + A^+ A + u r + 1 , ⋯ , u m u_{r+1},\cdots,u_m u r + 1 , ⋯ , u m
性质1： A + A^+ A + N ( A T ) N(A^T) N ( A T ) 变换成0
A T A A^TA A T A
对于A x = b Ax=b A x = b x ^ = ( A T A ) − 1 A T b \hat x = (A^TA)^{-1}A^Tb x ^ = ( A T A ) − 1 A T b A T A A^TA A T A 伪逆可以消除该限制 ，而且思考过程非常漂亮！b = b C + b N b=b_C+b_N b = b C + b N b C ∈ C ( A ) , b N ∈ N ( A T ) b_C \in C(A), b_N \in N(A^T) b C ∈ C ( A ) , b N ∈ N ( A T ) A x = b Ax=b A x = b A x = b C Ax=b_C A x = b C x = A + b C x=A^+b_C x = A + b C A x = A A + b C Ax=AA^+b_C A x = A A + b C b C ∈ C ( A ) b_C \in C(A) b C ∈ C ( A ) A A + b C = b C AA^+b_C=b_C A A + b C = b C x = A + b C x=A^+b_C x = A + b C A x = b C Ax=b_C A x = b C A x = b Ax=b A x = b A + b C = A + b A^+b_C=A^+b A + b C = A + b x = A + b = V Σ + U b x=A^+b=V\Sigma^+Ub x = A + b = V Σ + U b A x = b Ax=b A x = b
讨论：
如果A T A A^TA A T A r a n k [ A ] = n rank[A]=n r a n k [ A ] = n m ⩾ n m\geqslant n m ⩾ n x = A + b = ( A T A ) − 1 A T b x=A^+b=(A^TA)^{-1}A^Tb x = A + b = ( A T A ) − 1 A T b A + = ( A T A ) − 1 A T A^+=(A^TA)^{-1}A^T A + = ( A T A ) − 1 A T A A A A + = A − 1 A^+=A^{-1} A + = A − 1
如果A T A A^TA A T A x = A + b x=A^+b x = A + b C ( A T ) C(A^T) C ( A T )
A = C R 列/行向量无关 A = L U elimination，下上三角分解 A = Q R Gram-Schmitt, Q 正交 A = V Λ V − 1 一 般 特 征 分 解 S = Q Λ Q T S 对称, 特征分解， Q 正交 A = U Σ V T SVD A = Q S Polar Decomposition
\begin{aligned}
A=&CR &\qquad \text{ 列/行向量无关}\\
A=& LU&\qquad \text{ elimination，下上三角分解}\\
A=&QR &\qquad \text{Gram-Schmitt, $Q$正交} \\
A=&V\Lambda V^{-1} & 一般特征分解\\
S=&Q\Lambda Q^T & \qquad \text{$S$对称, 特征分解，$Q$正交} \\
A= &U\Sigma V^T &\qquad \text{SVD} \\
A = &QS &\qquad \text{Polar Decomposition}
\end{aligned}
A = A = A = A = S = A = A = C R L U Q R V Λ V − 1 Q Λ Q T U Σ V T Q S 列 / 行向量无关 elimination ，下上三角分解 Gram-Schmitt, Q 正交 一 般 特 征 分 解 S 对称 , 特征分解， Q 正交 SVD Polar Decomposition
L U = [ l 1 , l 2 , ⋯ ] [ u 1 u 2 ⋮ ] = l 1 u 1 + l 2 u 2 + ⋯
LU=[l_1, l_2, \cdots]\begin{bmatrix} u_1\\ u_2 \\ \vdots \end{bmatrix} \\
=l_1u_1+l_2u_2+\cdots
L U = [ l 1 , l 2 , ⋯ ] ⎣ ⎢ ⎡ u 1 u 2 ⋮ ⎦ ⎥ ⎤ = l 1 u 1 + l 2 u 2 + ⋯ L L L 单位 下三角矩阵（对角线为1）。l i u i l_iu_i l i u i A A A l 1 u 1 l_1u_1 l 1 u 1 A A A l i u i l_i u_i l i u i i − 1 i-1 i − 1 i − 1 i-1 i − 1 l i l_i l i i − 1 i-1 i − 1 u i u_i u i L U LU L U
当A的所有顺序主子式都不为0时，主元不为0，矩阵A A A 百度百科 ）U U U L L L
参考文献：MIT18.06 Linear Algebra MIT 18.065 Matrix Methods in Data Analysis, Signal Processing, and Machine Learning 3Blue1Brown 线性代数的本质
