线性代数|机器学习-P15矩阵A的低秩变换下的逆矩阵
文章目录
- 1. 单位矩阵的秩1变换
- 1.1 功能说明
- 1.2 证明
- 2. 单位矩阵 I n I_n In的秩k变换
- 3. 一般矩阵A的秩k变换
- 4. 公式用途
- 4.1 求解方程
- 4.2 卡曼滤波
1. 单位矩阵的秩1变换
1.1 功能说明
假设我们有一个单位矩阵I，列向量u,v那么当我们对单位向量I减去秩为1的矩阵后，其逆等于多少？
M = I − u v T , M − 1 = I + u v T 1 − v T u \begin{equation} M=I-uv^T,M^{-1}=I+\frac{uv^T}{1-v^Tu} \end{equation} M=I−uvT,M−1=I+1−vTuuvT
- 我们发现，对于单位矩阵进行秩为1的扰动 u v T uv^T uvT,其逆也是进行秩为1的扰动 u v T 1 − v T u \frac{uv^T}{1-v^Tu} 1−vTuuvT,这个公式的好处在于，当我们知道对I的秩为1的扰动，就能通过公式直接知道其逆的扰动，真神奇！
1.2 证明
M = I − u v T ⇒ M − 1 = I + u v T 1 − v T u \begin{equation} M=I-uv^T\Rightarrow M^{-1}=I+\frac{uv^T}{1-v^Tu}\end{equation} M=I−uvT⇒M−1=I+1−vTuuvT
- 定义矩阵E表示如下：
E = [ I u v T 1 ] , D e t [ E ] = 1 − v T u (3) E=\begin{bmatrix}I&&u\\\\v^T&&1\end{bmatrix},Det[E]=1-v^Tu\tag{3} E= IvTu1 ,Det[E]=1−vTu(3)
我们想求 E − 1 E^{-1} E−1，可以通过增广矩阵，进行行变换得到， - 第一种方法是：将第一行乘以 v T v^T vT后加到第二行中.
[ I 0 − v T 1 ] E = [ I u 0 D ] (4) \begin{bmatrix}I&&0\\\\-v^T&&1\end{bmatrix}E=\begin{bmatrix}I&&u\\\\0&&D\end{bmatrix}\tag{4} I−vT01 E= I0uD (4)
E − 1 = [ I u 0 D ] − 1 [ I 0 − v T 1 ] = [ I + u D − 1 v T − u D − 1 − D − 1 v T D − 1 ] (5) E^{-1}=\begin{bmatrix}I&&u\\\\0&&D\end{bmatrix}^{-1}\begin{bmatrix}I&&0\\\\-v^T&&1\end{bmatrix}=\begin{bmatrix}I+uD^{-1}v^T&&-uD^{-1}\\\\-D^{-1}v^T&&D^{-1}\end{bmatrix}\tag{5} E−1= I0uD −1 I−vT01 = I+uD−1vT−D−1vT−uD−1D−1 (5) - 第二种方法是：将第二行乘以 u u u后加到第一行中.
[ I − u 0 1 ] E = [ I − u v T 0 v T 1 ] (6) \begin{bmatrix}I&&-u\\\\0&&1\end{bmatrix}E=\begin{bmatrix}I-uv^T&&0\\\\v^T&&1\end{bmatrix}\tag{6} I0−u1 E= I−uvTvT01 (6)
E − 1 = [ I − u v T 0 v T 1 ] − 1 [ I − u 0 1 ] = [ M − 1 − M − 1 u − v T M − 1 1 + v T M − 1 u ] (7) E^{-1}=\begin{bmatrix}I-uv^T&&0\\\\v^T&&1\end{bmatrix}^{-1}\begin{bmatrix}I&&-u\\\\0&&1\end{bmatrix}=\begin{bmatrix}M^{-1}&&-M^{-1}u\\\\-v^TM^{-1}&&1+v^TM^{-1}u\end{bmatrix}\tag{7} E−1= I−uvTvT01 −1 I0−u1 = M−1−vTM−1−M−1u1+vTM−1u (7) - 由公式4,6 可得，两个 E − 1 E^{-1} E−1相等, M = I − u v T M=I-uv^T M=I−uvT
[ I + u D − 1 v T − u D − 1 − D − 1 v T D − 1 ] = [ M − 1 − M − 1 u − v T M − 1 1 + v T M − 1 u ] (8) \begin{bmatrix}I+uD^{-1}v^T&&-uD^{-1}\\\\-D^{-1}v^T&&D^{-1}\end{bmatrix}=\begin{bmatrix}M^{-1}&&-M^{-1}u\\\\-v^TM^{-1}&&1+v^TM^{-1}u\end{bmatrix}\tag{8} I+uD−1vT−D−1vT−uD−1D−1 = M−1−vTM−1−M−1u1+vTM−1u (8) - 由第一个行，第一列可得如下
M − 1 = I + u D − 1 v T = I + u v T 1 − v T u (9) M^{-1}=I+uD^{-1}v^T=I+\frac{uv^T}{1-v^Tu}\tag{9} M−1=I+uD−1vT=I+1−vTuuvT(9) - 结论：
M = I − u v T ⇒ M − 1 = I + u v T 1 − v T u (10) M=I-uv^T\Rightarrow M^{-1}=I+\frac{uv^T}{1-v^Tu}\tag{10} M=I−uvT⇒M−1=I+1−vTuuvT(10)
2. 单位矩阵 I n I_n In的秩k变换
- 定义 M 表示如下：
M = I − U V T → M − 1 = I n + U ( I k − V T U ) − 1 V T \begin{equation} M=I-UV^T\rightarrow M^{-1}=I_n+U(I_k-V^TU)^{-1}V^T \end{equation} M=I−UVT→M−1=In+U(Ik−VTU)−1VT - 同理构造矩阵E
E = [ I n U V T I k ] , d e t ( E ) = d e t ( I n − U V T ) \begin{equation} E=\begin{bmatrix}I_n&U\\\\V^T&I_k\end{bmatrix},det(E)=det(I_n-UV^T) \end{equation} E= InVTUIk ,det(E)=det(In−UVT)
3. 一般矩阵A的秩k变换
Sherman-Morrison-Woodbury formula- 定义 M 表示如下：
M = A − U V T \begin{equation} M=A-UV^T \end{equation} M=A−UVT
- M − 1 = A − 1 + A − 1 U ( I − V T A − 1 U ) − 1 V T A − 1 \begin{equation} M^{-1}=A^{-1}+A^{-1}U(I-V^TA^{-1}U)^{-1}V^TA^{-1} \end{equation} M−1=A−1+A−1U(I−VTA−1U)−1VTA−1 - 同理构造矩阵E
E = [ A U V T I ] , d e t ( E ) = d e t ( A − U V T ) \begin{equation} E=\begin{bmatrix}A&U\\\\V^T&I\end{bmatrix},det(E)=det(A-UV^T) \end{equation} E= AVTUI ,det(E)=det(A−UVT)
4. 公式用途
4.1 求解方程
( I k − U V T ) x = b → x = [ I n + U ( I k − V T U ) − 1 V T ] b \begin{equation} (I_k-UV^T)x=b\rightarrow x=[I_n+U(I_k-V^TU)^{-1}V^T] b \end{equation} (Ik−UVT)x=b→x=[In+U(Ik−VTU)−1VT]b
4.2 卡曼滤波
当我们有一个已知的方程解 A x = b Ax=b Ax=b，最小二乘的结果如下：
A T A x ^ = A T b \begin{equation} A^TA\hat{x}=A^Tb \end{equation} ATAx^=ATb
- 突然我们需要新增一行数据 v T v^T vT,那么矩阵变成如下：
[ A T v ] [ A v T ] x ^ = [ A T v ] [ b b m + 1 ] \begin{equation} \begin{bmatrix}A^T&v\end{bmatrix} \begin{bmatrix}A\\\\v^T\end{bmatrix}\hat{x}=\begin{bmatrix}A^T&v\end{bmatrix} \begin{bmatrix}b\\\\b_{m+1}\end{bmatrix} \end{equation} [ATv] AvT x^=[ATv] bbm+1 - 整理可得如下：
[ A T A + v v T ] x ^ = A T b + v b m + 1 \begin{equation} [A^TA+vv^T]\hat{x}=A^Tb+vb_{m+1} \end{equation} [ATA+vvT]x^=ATb+vbm+1 - 我们发现原来的矩阵为 A T A A^TA ATA，后来加了一个秩1的矩阵 v v T vv^T vvT,那么在假设原来 A T A A^TA ATA可逆的情况下，可以直接通过公式求得：
M = A T A − v v T \begin{equation} M=A^TA-vv^T \end{equation} M=ATA−vvT
M − 1 = ( A T A ) − 1 + ( A T A ) − 1 v ( I + v T ( A T A ) − 1 v ) − 1 v T ( A T A ) − 1 \begin{equation} M^{-1}=(A^TA)^{-1}+(A^TA)^{-1}v(I+v^T(A^TA)^{-1}v)^{-1}v^T(A^TA)^{-1} \end{equation} M−1=(ATA)−1+(ATA)−1v(I+vT(ATA)−1v)−1vT(ATA)−1
这样就可以在原来的结果基础上直接得到新解。