schur complement

Schur Complement

定义

舒尔补被定义为：

假设 A, B, C, D 是 4 个复矩阵，设：

$$M=\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]$$

那么如果 D 是可逆的，记 M 对 D 的 schur complement(舒尔补) 为：

$$M/D\equiv A-B{D}^{-1}C$$

对应的，如果 A 是可逆的，记其对 A 的舒尔补为：

$$M/A\equiv D-C{A}^{-1}B$$

如果 A 或者 D 是奇异的，那么将其替换为广义逆 即可

背景

舒尔补出现在对矩阵 M 进行块矩阵的高斯分解的过程中，如下所示：

$$M=\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]\to \left[\begin{array}{cc}A& B\\ C& D\end{array}\right]\left[\begin{array}{cc}I& 0\\ -D^{-1}C& I\end{array}\right]=\left[\begin{array}{cc}A-B{D}^{-1}C& B\\ 0& D\end{array}\right]$$

进一步进行消元：

$$\left[\begin{array}{cc}A-B{D}^{-1}C& B\\ 0& D\end{array}\right]\to \left[\begin{array}{cc}I& -B{D}^{-1}\\ 0& I\end{array}\right]\left[\begin{array}{cc}A-B{D}^{-1}C& B\\ 0& D\end{array}\right]=\left[\begin{array}{cc}A-B{D}^{-1}C& 0\\ 0& D\end{array}\right]$$

这引入了矩阵 M 的 LU decomposition - Wikipedia，有：

$$M=\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]=\left[\begin{array}{cc}I& -B{D}^{-1}\\ 0& I\end{array}\right]\left[\begin{array}{cc}A-B{D}^{-1}C& 0\\ 0& D\end{array}\right]\left[\begin{array}{cc}I& 0\\ -D^{-1}C& I\end{array}\right]$$

从而可以将 $M^{-1}$ 表示为舒尔补的逆和 $D^{-1}$ 的组合，假定其存在，则：

$$\begin{array}{rl}{M}^{-1}={\left[\begin{array}{ll}A& B\\ C& D\end{array}\right]}^{-1}& ={\left(\left[\begin{array}{cc}{I}_p& B{D}^{-1}\\ 0& I_q\end{array}\right]\left[\begin{array}{cc}A-B{D}^{-1}C& 0\\ 0& D\end{array}\right]\left[\begin{array}{cc}{I}_p& 0\\ D^{-1}C& I_q\end{array}\right]\right)}^{-1}\\ & =\left[\begin{array}{cc}{I}_p& 0\\ -D^{-1}C& I_q\end{array}\right]\left[\begin{array}{rr}{\left(A-B{D}^{-1}C\right)}^{-1}& 0\\ 0& D^{-1}\end{array}\right]\left[\begin{array}{cc}{I}_p& -B{D}^{-1}\\ 0& I_q\end{array}\right]\\ & =\left[\begin{array}{cc}{\left(A-B{D}^{-1}C\right)}^{-1}& -{\left(A-B{D}^{-1}C\right)}^{-1}B{D}^{-1}\\ -D^{-1}C{\left(A-B{D}^{-1}C\right)}^{-1}& D^{-1}+D^{-1}C{\left(A-B{D}^{-1}C\right)}^{-1}B{D}^{-1}\end{array}\right]\\ & =\left[\begin{array}{cc}(M/D{)}^{-1}& -(M/D{)}^{-1}B{D}^{-1}\\ -D^{-1}C(M/D{)}^{-1}& D^{-1}+D^{-1}C(M/D{)}^{-1}B{D}^{-1}\end{array}\right]\end{array}$$

性质

块矩阵逆

$$M^{-1}=\frac{1}{AD-BC}\left[\begin{array}{cc}D& -B\\ -C& A\end{array}\right]$$

如果 $AD-BC$ 不是零

note

这里不是0怎么理解？

块矩阵行列式

$$\begin{gathered} \det \left(M\right)=\det \left(A\right)\det \left(D-C{A}^{-1}B\right) \\ \det \left(M\right)=\det \left(D\right)\det \left(A-B{D}^{-1}C\right) \end{gathered}$$

正定性质

note

应用在优化理论！

如果 X 具有这样的形式：

$$X=\left[\begin{array}{cc}A& B\\ B^T& C\end{array}\right]$$

那么有：

• 如果 A 可逆，则 X 正定<=>A 和 X/A 正定
  • $X\succ 0\iff A\succ 0,X/A=C-B^T{A}^{-1}B\succ 0$
• 如果 C 可逆，则 X 正定<=>C 和 X/C 正定
  • $X\succ 0\iff C\succ 0,X/C=A-B{C}^{-1}{B}^T\succ 0$

半正定同理

上面的结论可以通过考虑这样一个优化问题来证明：

假设 quadratic function

$$f\left(x,y\right)=x^{T}Ax+2x^{T}By+y^{T}Cy$$

（其中 A, C 是对称的）是对 (x,y) 凸的，这意味着：

$$\left[\begin{array}{cc}A& B\\ B^T& C\end{array}\right]⪰0$$

我们考虑函数

$$g\left(x\right)={\inf }_{y}f\left(x,y\right)=x^T\left(A-B{C}^g{B}^T\right)x$$

其中 $C^g$ 是 C 的广义逆，那么根据 minimization rule，g 是凸的，则意味着：

$$A-B{C}^g{B}^T⪰0$$

对奇异的情形：

仅对半正定有：

• $X⪰0\iff A⪰0,C-B^T{A}^{g}B⪰0,\left(I-A{A}^g\right)B=0$
• $X⪰0\iff C⪰0,A-B{C}^g{B}^T⪰0,\left(I-C{C}^g\right)B^T=0$

其中 $A^g$ 代表 A 的 广义逆

参考

引文

• Schur complement - Wikipedia

脚注