线性代数|机器学习-P15矩阵A的低秩变换下的逆矩阵

1. 单位矩阵的秩1变换

1.1 功能说明

假设我们有一个单位矩阵I，列向量u,v那么当我们对单位向量I减去秩为1的矩阵后，其逆等于多少？
$$\begin{array}{c}M=I-u{v}^T,M^{-1}=I+\frac{u{v}^T}{1-v^{T}u}\end{array}$$

• 我们发现，对于单位矩阵进行秩为1的扰动 $u{v}^T$,其逆也是进行秩为1的扰动 $\frac{u{v}^T}{1-v^{T}u}$,这个公式的好处在于，当我们知道对I的秩为1的扰动，就能通过公式直接知道其逆的扰动，真神奇！

1.2 证明

$$\begin{array}{c}M=I-u{v}^T\Rightarrow M^{-1}=I+\frac{u{v}^T}{1-v^{T}u}\end{array}$$

• 定义矩阵E表示如下：
  $$E=\left[\begin{array}{ccc}I& & u\\ & & \\ v^T& & 1\end{array}\right],Det[E]=1-v^{T}u\text{\hspace{1em}(3)}$$
  我们想求$E^{-1}$，可以通过增广矩阵，进行行变换得到，
• 第一种方法是：将第一行乘以$v^T$后加到第二行中.
  $$\left[\begin{array}{ccc}I& & 0\\ & & \\ -v^T& & 1\end{array}\right]E=\left[\begin{array}{ccc}I& & u\\ & & \\ 0& & D\end{array}\right]\text{\hspace{1em}(4)}$$
  $$E^{-1}={\left[\begin{array}{ccc}I& & u\\ & & \\ 0& & D\end{array}\right]}^{-1}\left[\begin{array}{ccc}I& & 0\\ & & \\ -v^T& & 1\end{array}\right]=\left[\begin{array}{ccc}I+u{D}^{-1}{v}^T& & -u{D}^{-1}\\ & & \\ -D^{-1}{v}^T& & D^{-1}\end{array}\right]\text{\hspace{1em}(5)}$$
• 第二种方法是：将第二行乘以$u$后加到第一行中.
  $$\left[\begin{array}{ccc}I& & -u\\ & & \\ 0& & 1\end{array}\right]E=\left[\begin{array}{ccc}I-u{v}^T& & 0\\ & & \\ v^T& & 1\end{array}\right]\text{\hspace{1em}(6)}$$
  $$E^{-1}={\left[\begin{array}{ccc}I-u{v}^T& & 0\\ & & \\ v^T& & 1\end{array}\right]}^{-1}\left[\begin{array}{ccc}I& & -u\\ & & \\ 0& & 1\end{array}\right]=\left[\begin{array}{ccc}{M}^{-1}& & -M^{-1}u\\ & & \\ -v^T{M}^{-1}& & 1+v^T{M}^{-1}u\end{array}\right]\text{\hspace{1em}(7)}$$
• 由公式4,6 可得，两个$E^{-1}$相等,$M=I-u{v}^T$
  $$\left[\begin{array}{ccc}I+u{D}^{-1}{v}^T& & -u{D}^{-1}\\ & & \\ -D^{-1}{v}^T& & D^{-1}\end{array}\right]=\left[\begin{array}{ccc}{M}^{-1}& & -M^{-1}u\\ & & \\ -v^T{M}^{-1}& & 1+v^T{M}^{-1}u\end{array}\right]\text{\hspace{1em}(8)}$$
• 由第一个行，第一列可得如下
  $$M^{-1}=I+u{D}^{-1}{v}^T=I+\frac{u{v}^T}{1-v^{T}u}\text{\hspace{1em}(9)}$$
• 结论：
  $$M=I-u{v}^T\Rightarrow M^{-1}=I+\frac{u{v}^T}{1-v^{T}u}\text{\hspace{1em}(10)}$$

2. 单位矩阵$I_n$的秩k变换

• 定义 M 表示如下：
  $$\begin{array}{c}M=I-U{V}^T\to M^{-1}=I_n+U(I_k-V^{T}U{)}^{-1}{V}^T\end{array}$$
• 同理构造矩阵E
  $$\begin{array}{c}E=\left[\begin{array}{cc}{I}_n& U\\ & \\ V^T& I_k\end{array}\right],det(E)=det(I_n-U{V}^T)\end{array}$$

3. 一般矩阵A的秩k变换

• Sherman-Morrison-Woodbury formula
• 定义 M 表示如下：
  $$\begin{array}{c}M=A-U{V}^T\end{array}$$
  -$$\begin{array}{c}{M}^{-1}=A^{-1}+A^{-1}U(I-V^T{A}^{-1}U{)}^{-1}{V}^T{A}^{-1}\end{array}$$
• 同理构造矩阵E
  $$\begin{array}{c}E=\left[\begin{array}{cc}A& U\\ & \\ V^T& I\end{array}\right],det(E)=det(A-U{V}^T)\end{array}$$

4. 公式用途

4.1 求解方程

$$\begin{array}{c}(I_k-U{V}^T)x=b\to x=[I_n+U(I_k-V^{T}U{)}^{-1}{V}^T]b\end{array}$$

4.2 卡曼滤波

当我们有一个已知的方程解$Ax=b$，最小二乘的结果如下：
$$\begin{array}{c}{A}^{T}A\hat{x}=A^{T}b\end{array}$$

• 突然我们需要新增一行数据 $v^T$,那么矩阵变成如下：
  $$\begin{array}{c}\left[\begin{array}{cc}{A}^T& v\end{array}\right]\left[\begin{array}{c}A\\ \\ v^T\end{array}\right]\hat{x}=\left[\begin{array}{cc}{A}^T& v\end{array}\right]\left[\begin{array}{c}b\\ \\ b_{m+1}\end{array}\right]\end{array}$$
• 整理可得如下：
  $$\begin{array}{c}[A^{T}A+v{v}^T]\hat{x}=A^{T}b+v{b}_{m+1}\end{array}$$
• 我们发现原来的矩阵为$A^{T}A$，后来加了一个秩1的矩阵 $v{v}^T$,那么在假设原来$A^{T}A$可逆的情况下，可以直接通过公式求得：
  $$\begin{array}{c}M=A^{T}A-v{v}^T\end{array}$$
  $$\begin{array}{c}{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}\end{array}$$
  这样就可以在原来的结果基础上直接得到新解。