之前在各类应用中接触到了 Schur补， 即舒尔补这个概念。 而下定决心写一篇博客来记录， 是由于在 压缩感知的尽头: 原子范数最小化 又一次充分应用到了 Schur 补。 似乎， 这和 矩阵的 半正定性， 和 SDP 的充分使用，密不可分。 因此， 有足够的理由深入了解。
参考的书籍为： Convex Optimization for Signal Processing and Communications: From Fundamentals to Applications.
无疑是凸优化的一本好书， 和Boyd的著作相比， 完全称得上是各有千秋。 后续的许多博客， 可能也会介绍其中的精华内容。
Schur 补假设 C ∈ S + + m , A ∈ S n \mathbf{C} \in \mathbb{S}_{++}^{m}, \mathbf{A} \in \mathbb{S}^{n} C∈S++m,A∈Sn， 即前者为正定矩阵， 后者为对称矩阵。那么： S ≜ [ A B B T C ] ⪰ 0 , 当且仅当 S C ≜ A − B C − 1 B T ⪰ 0 \mathrm{S} \triangleq\left[\begin{array}{cc} \mathrm{A} & \mathrm{B} \\ \mathrm{B}^{\mathrm{T}} & \mathrm{C} \end{array}\right] \succeq 0, \text { 当且仅当 } \mathrm{S}_{\mathrm{C}} \triangleq \mathrm{A}-\mathrm{BC}^{-1} \mathrm{~B}^{\mathrm{T}} \succeq 0 S≜[ABTBC]⪰0, 当且仅当 SC≜A−BC−1 BT⪰0 其中， S C \mathrm{S}_{\mathrm{C}} SC 被称为 Schur 补。 可以看到， 此处要求 C \mathbf{C} C 矩阵必须可逆， 这也是一开始要求其为正定矩阵的原因。
证明：必要性由于 S ⪰ 0 \mathbf{S}\succeq 0 S⪰0， 根据半正定矩阵的定义， 有： f ( x , y ) = [ x T y T ] S [ x y ] = [ x T y T ] [ A B B T C ] [ x y ] ⩾ 0 , ∀ ( x , y ) ∈ R n + m \begin{aligned} f(\mathbf{x}, \mathbf{y}) &=\left[\mathbf{x}^{\mathrm{T}} \;\mathbf{y}^{\mathrm{T}}\right] \mathbf{S}\left[\begin{array}{l} \mathbf{x} \\ \mathbf{y} \end{array}\right] \\ &=\left[\mathbf{x}^{\mathrm{T}}\; \mathbf{y}^{\mathrm{T}}\right]\left[\begin{array}{cc} \mathbf{A} & \mathbf{B} \\ \mathbf{B}^{\mathrm{T}} & \mathbf{C} \end{array}\right]\left[\begin{array}{l} \mathbf{x} \\ \mathbf{y} \end{array}\right] \geqslant 0, \forall(\mathbf{x}, \mathbf{y}) \in \mathbb{R}^{n+m} \end{aligned} f(x,y)=[xTyT]S[xy]=[xTyT][ABTBC][xy]⩾0,∀(x,y)∈Rn+m 这是 关于 f ( x , y ) f(\mathbf{x}, \mathbf{y}) f(x,y) 的凸函数， 因为这是个二次型函数，而矩阵 S \mathbf{S} S 半正定， 因此可由二阶条件直接得到。 再考虑函数： g ( x ) = inf y ∈ R m f ( x , y ) ⩾ 0 (1) g(\mathbf{x})=\inf _{\mathbf{y} \in \mathbb{R}^{m}} f(\mathbf{x}, \mathbf{y}) \geqslant 0 \tag{1} g(x)=y∈Rminff(x,y)⩾0(1) 注意到 g ( x ) g(x) g(x)可以视为 f ( x , y ) f(x,y) f(x,y)在非空凸集中的逐点下确界。因此， g ( x ) g(x) g(x) 也是凸函数 （逐点下确界法则）。 同时注意到， f ( x , y ) = x T A x + 2 x T B y + y T C y f(\mathbf{x}, \mathbf{y})=\mathbf{x}^{\mathrm{T}} \mathbf{A} \mathbf{x}+2 \mathbf{x}^{\mathrm{T}} \mathbf{B} \mathbf{y}+\mathbf{y}^{\mathrm{T}} \mathbf{C y} f(x,y)=xTAx+2xTBy+yTCy 因此当固定 x x x 时， f f f 对于 y y y 是个凸函数 （因为二次型函数， C \mathbf{C} C 为正定）。因此，要找出 (1) 中的下界， 先对 y y y 求梯度： ∇ y f ( x , y ) = 2 B T x + 2 C y = 0 ⇒ y ⋆ = − C − 1 B T x \nabla_{\mathbf{y}} f(\mathbf{x}, \mathbf{y})=2 \mathbf{B}^{\mathrm{T}} \mathbf{x}+2 \mathbf{C y}=\mathbf{0} \Rightarrow \mathbf{y}^{\star}=-\mathbf{C}^{-1} \mathbf{B}^{\mathrm{T}} \mathbf{x} ∇yf(x,y)=2BTx+2Cy=0⇒y⋆=−C−1BTx 将其代入 (1)， 有： g ( x ) = f ( x , y ∗ ) = x T A x − 2 x T B C − 1 B T x + x T B C − 1 B T x = x T ( A − B C − 1 B T ) x = x T S C x ≥ 0 , ∀ x ∈ R n \begin{aligned} g(\mathbf{x}) &=f\left(\mathbf{x}, \mathbf{y}^{*}\right) \\ &=\mathbf{x}^{\mathrm{T}} \mathbf{A} \mathbf{x}-2 \mathbf{x}^{\mathrm{T}} \mathbf{B} \mathbf{C}^{-1} \mathbf{B}^{\mathrm{T}} \mathbf{x}+\mathbf{x}^{\mathrm{T}} \mathbf{B} \mathbf{C}^{-1} \mathbf{B}^{\mathrm{T}} \mathbf{x} \\ &=\mathbf{x}^{\mathrm{T}}\left(\mathbf{A}-\mathbf{B} \mathbf{C}^{-1} \mathbf{B}^{\mathrm{T}}\right) \mathbf{x}=\mathbf{x}^{\mathrm{T}} \mathbf{S}_{\mathbf{C}} \mathbf{x} \ge 0, \quad \forall \mathbf{x} \in \mathbb{R}^{n} \end{aligned} g(x)=f(x,y∗)=xTAx−2xTBC−1BTx+xTBC−1BTx=xT(A−BC−1BT)x=xTSCx≥0,∀x∈Rn 因此， S C \mathbf{S}_\mathbf{C} SC 为半正定矩阵。 至此， 必要性得证。
证明：充分性S C ⪰ 0 \mathbf{S}_\mathbf{C}\succeq0 SC⪰0 时， 直接有 g ( x ) ≥ 0 , ∀ x ∈ R n g(x)\ge 0, \forall \mathbf{x}\in\mathbb{R}^n g(x)≥0,∀x∈Rn 而 f ( x , y ) ≥ g ( x ) f(x,y)\ge g(x) f(x,y)≥g(x)， 因为 g ( x ) g(x) g(x) 的定义就是 f ( x , y ) f(x,y) f(x,y) 的下确界。 因此， S ⪰ 0 \mathbf{S}\succeq 0 S⪰0 显然成立。 充分性得证。
拓展当 C \mathbf{C} C 为半正定时， Schur补变为： S C = A − B C † B T \mathrm{S}_{\mathbf{C}}=\mathbf{A}-\mathbf{B C}^{\dagger} \mathbf{B}^{\mathrm{T}} SC=A−BC†BT 结论仍成立。
类似的推导下， 也可以有： S ≜ [ A B B T C ] ⪰ 0 , 当且仅当 S A ≜ C − B T A − 1 B ⪰ 0 \mathrm{S} \triangleq\left[\begin{array}{cc} \mathrm{A} & \mathrm{B} \\ \mathrm{B}^{\mathrm{T}} & \mathrm{C} \end{array}\right] \succeq 0, \quad \text { 当且仅当 } \mathrm{S}_{\mathrm{A}} \triangleq \mathrm{C}-\mathrm{B}^{\mathrm{T}} \mathrm{A}^{-1} \mathrm{~B} \succeq 0 S≜[ABTBC]⪰0, 当且仅当 SA≜C−BTA−1 B⪰0
