分块矩阵的Sherman-Morrison-Woodbury公式在低秩更新求逆中的应用

字数 2092 2025-11-04 20:47:27

分块矩阵的Sherman-Morrison-Woodbury公式在低秩更新求逆中的应用

题目描述
假设我们有一个n×n的可逆矩阵A，其逆矩阵A⁻¹已知。现在对A进行低秩修正，得到新矩阵B = A + UVᵀ，其中U和V是n×k矩阵（k << n），即修正的秩k远小于矩阵维度n。Sherman-Morrison-Woodbury公式（简称SMW公式）提供了一种高效计算B⁻¹的方法，避免直接对B求逆（时间复杂度O(n³)），而是利用已知的A⁻¹，通过处理较小的k×k矩阵来高效求解。

解题过程

1. 公式推导思路
我们从简单的秩1修正开始理解核心思想，再推广到秩k情况。

步骤1.1：秩1修正情况（Sherman-Morrison公式）
当k=1时，U和V退化为列向量u和v，B = A + uvᵀ。
我们假设B⁻¹可以表示为A⁻¹加上一个修正项：B⁻¹ = A⁻¹ + C。
在等式两边同时乘以B = A + uvᵀ：
B⁻¹B = (A⁻¹ + C)(A + uvᵀ) = I（单位矩阵）
展开得：A⁻¹A + A⁻¹(uvᵀ) + CA + C(uvᵀ) = I
即：I + A⁻¹uvᵀ + CA + Cuvᵀ = I
化简：A⁻¹uvᵀ + CA + Cuvᵀ = 0
为了求解C，我们假设C具有形式C = A⁻¹u * β * vᵀA⁻¹，其中β是一个待定标量。
代入上式：
A⁻¹uvᵀ + (A⁻¹uβvᵀA⁻¹)A + (A⁻¹uβvᵀA⁻¹)uvᵀ = 0
化简：A⁻¹uvᵀ + A⁻¹uβvᵀ + A⁻¹uβvᵀA⁻¹uvᵀ = 0
提取公因式A⁻¹u：A⁻¹u [vᵀ + βvᵀ + βvᵀA⁻¹uvᵀ] = 0
由于A⁻¹u一般非零，所以括号内必须为零：vᵀ + βvᵀ + β(vᵀA⁻¹u)vᵀ = 0
即：vᵀ [1 + β + β(vᵀA⁻¹u)] = 0
由于vᵀ一般非零，所以：1 + β + β(vᵀA⁻¹u) = 0
解得：β = -1 / (1 + vᵀA⁻¹u)
因此，秩1修正的逆矩阵公式为：
B⁻¹ = (A + uvᵀ)⁻¹ = A⁻¹ - (A⁻¹uvᵀA⁻¹) / (1 + vᵀA⁻¹u)
验证：将B⁻¹与B相乘，确实可以得到单位矩阵I。

步骤1.2：推广到秩k修正（Woodbury公式）
现在考虑一般情况B = A + UVᵀ，其中U, V是n×k矩阵。
推导思路类似，但需要使用块矩阵运算。我们假设B⁻¹ = A⁻¹ + A⁻¹U * M * VᵀA⁻¹，其中M是一个k×k的待定矩阵。
在等式两边乘以B：
B⁻¹B = (A⁻¹ + A⁻¹UMVᵀA⁻¹)(A + UVᵀ) = I
展开：
A⁻¹A + A⁻¹UVᵀ + A⁻¹UMVᵀA⁻¹A + A⁻¹UMVᵀA⁻¹UVᵀ = I
即：I + A⁻¹UVᵀ + A⁻¹UMVᵀ + A⁻¹UM(VᵀA⁻¹U)Vᵀ = I
化简：A⁻¹U[Vᵀ + MVᵀ + M(VᵀA⁻¹U)Vᵀ] = 0
由于A⁻¹U一般列满秩，所以括号内必须为零：
Vᵀ + MVᵀ + M(VᵀA⁻¹U)Vᵀ = 0
即：Vᵀ + M[I + (VᵀA⁻¹U)]Vᵀ = 0
提取Vᵀ：{I + M[I + VᵀA⁻¹U]}Vᵀ = 0
由于Vᵀ一般行满秩，所以：I + M(I + VᵀA⁻¹U) = 0
解得：M = -(I + VᵀA⁻¹U)⁻¹
因此，完整的SMW公式为：
B⁻¹ = (A + UVᵀ)⁻¹ = A⁻¹ - A⁻¹U(I + VᵀA⁻¹U)⁻¹VᵀA⁻¹

2. 计算步骤
已知A⁻¹，求B⁻¹的具体计算流程：

步骤2.1：计算中间矩阵
首先计算k×k矩阵：C = VᵀA⁻¹U
计算复杂度：Vᵀ是k×n，A⁻¹是n×n，U是n×k，所以总共需要O(kn²)运算。

步骤2.2：求小矩阵的逆
计算k×k矩阵：D = (I + C)⁻¹
由于k很小，这个求逆只需要O(k³)运算，相对于O(n³)可以忽略。

步骤2.3：组合最终结果
计算B⁻¹ = A⁻¹ - (A⁻¹U)D(VᵀA⁻¹)
这里A⁻¹U是n×k矩阵，D是k×k，VᵀA⁻¹是k×n，整个计算需要O(kn²)运算。

3. 复杂度分析

直接求B⁻¹：O(n³)
使用SMW公式：O(kn² + k³) ≈ O(kn²)（因为k << n）
当k远小于n时，SMW公式将计算复杂度从O(n³)降低到O(kn²)，实现了显著加速。

4. 应用场景

动态系统：当系统矩阵A发生低秩变化时，快速更新逆矩阵
机器学习：在线学习、增量学习中参数矩阵的低秩更新
数值优化：拟牛顿法中的Hessian矩阵低秩修正
统计计算：协方差矩阵的秩1更新

5. 数值稳定性考虑
当A病态或修正项较大时，SMW公式可能数值不稳定。实践中常采用：

对I + VᵀA⁻¹U进行Cholesky分解（当矩阵对称正定时）
使用QR分解等数值稳定方法
添加正则化项改善条件数

分块矩阵的Sherman-Morrison-Woodbury公式在低秩更新求逆中的应用题目描述假设我们有一个n×n的可逆矩阵A，其逆矩阵A⁻¹已知。现在对A进行低秩修正，得到新矩阵B = A + UVᵀ，其中U和V是n×k矩阵（k < < n），即修正的秩k远小于矩阵维度n。Sherman-Morrison-Woodbury公式（简称SMW公式）提供了一种高效计算B⁻¹的方法，避免直接对B求逆（时间复杂度O(n³)），而是利用已知的A⁻¹，通过处理较小的k×k矩阵来高效求解。解题过程 1. 公式推导思路我们从简单的秩1修正开始理解核心思想，再推广到秩k情况。步骤1.1：秩1修正情况（Sherman-Morrison公式）当k=1时，U和V退化为列向量u和v，B = A + uvᵀ。我们假设B⁻¹可以表示为A⁻¹加上一个修正项：B⁻¹ = A⁻¹ + C。在等式两边同时乘以B = A + uvᵀ： B⁻¹B = (A⁻¹ + C)(A + uvᵀ) = I（单位矩阵）展开得：A⁻¹A + A⁻¹(uvᵀ) + CA + C(uvᵀ) = I 即：I + A⁻¹uvᵀ + CA + Cuvᵀ = I 化简：A⁻¹uvᵀ + CA + Cuvᵀ = 0 为了求解C，我们假设C具有形式C = A⁻¹u * β * vᵀA⁻¹，其中β是一个待定标量。代入上式： A⁻¹uvᵀ + (A⁻¹uβvᵀA⁻¹)A + (A⁻¹uβvᵀA⁻¹)uvᵀ = 0 化简：A⁻¹uvᵀ + A⁻¹uβvᵀ + A⁻¹uβvᵀA⁻¹uvᵀ = 0 提取公因式A⁻¹u：A⁻¹u [ vᵀ + βvᵀ + βvᵀA⁻¹uvᵀ ] = 0 由于A⁻¹u一般非零，所以括号内必须为零：vᵀ + βvᵀ + β(vᵀA⁻¹u)vᵀ = 0 即：vᵀ [ 1 + β + β(vᵀA⁻¹u) ] = 0 由于vᵀ一般非零，所以：1 + β + β(vᵀA⁻¹u) = 0 解得：β = -1 / (1 + vᵀA⁻¹u) 因此，秩1修正的逆矩阵公式为： B⁻¹ = (A + uvᵀ)⁻¹ = A⁻¹ - (A⁻¹uvᵀA⁻¹) / (1 + vᵀA⁻¹u) 验证：将B⁻¹与B相乘，确实可以得到单位矩阵I。步骤1.2：推广到秩k修正（Woodbury公式）现在考虑一般情况B = A + UVᵀ，其中U, V是n×k矩阵。推导思路类似，但需要使用块矩阵运算。我们假设B⁻¹ = A⁻¹ + A⁻¹U * M * VᵀA⁻¹，其中M是一个k×k的待定矩阵。在等式两边乘以B： B⁻¹B = (A⁻¹ + A⁻¹UMVᵀA⁻¹)(A + UVᵀ) = I 展开： A⁻¹A + A⁻¹UVᵀ + A⁻¹UMVᵀA⁻¹A + A⁻¹UMVᵀA⁻¹UVᵀ = I 即：I + A⁻¹UVᵀ + A⁻¹UMVᵀ + A⁻¹UM(VᵀA⁻¹U)Vᵀ = I 化简：A⁻¹U[ Vᵀ + MVᵀ + M(VᵀA⁻¹U)Vᵀ ] = 0 由于A⁻¹U一般列满秩，所以括号内必须为零： Vᵀ + MVᵀ + M(VᵀA⁻¹U)Vᵀ = 0 即：Vᵀ + M[ I + (VᵀA⁻¹U) ]Vᵀ = 0 提取Vᵀ：{I + M[ I + VᵀA⁻¹U ]}Vᵀ = 0 由于Vᵀ一般行满秩，所以：I + M(I + VᵀA⁻¹U) = 0 解得：M = -(I + VᵀA⁻¹U)⁻¹ 因此，完整的SMW公式为： B⁻¹ = (A + UVᵀ)⁻¹ = A⁻¹ - A⁻¹U(I + VᵀA⁻¹U)⁻¹VᵀA⁻¹ 2. 计算步骤已知A⁻¹，求B⁻¹的具体计算流程：步骤2.1：计算中间矩阵首先计算k×k矩阵：C = VᵀA⁻¹U 计算复杂度：Vᵀ是k×n，A⁻¹是n×n，U是n×k，所以总共需要O(kn²)运算。步骤2.2：求小矩阵的逆计算k×k矩阵：D = (I + C)⁻¹ 由于k很小，这个求逆只需要O(k³)运算，相对于O(n³)可以忽略。步骤2.3：组合最终结果计算B⁻¹ = A⁻¹ - (A⁻¹U)D(VᵀA⁻¹) 这里A⁻¹U是n×k矩阵，D是k×k，VᵀA⁻¹是k×n，整个计算需要O(kn²)运算。 3. 复杂度分析直接求B⁻¹：O(n³) 使用SMW公式：O(kn² + k³) ≈ O(kn²)（因为k < < n）当k远小于n时，SMW公式将计算复杂度从O(n³)降低到O(kn²)，实现了显著加速。 4. 应用场景动态系统：当系统矩阵A发生低秩变化时，快速更新逆矩阵机器学习：在线学习、增量学习中参数矩阵的低秩更新数值优化：拟牛顿法中的Hessian矩阵低秩修正统计计算：协方差矩阵的秩1更新 5. 数值稳定性考虑当A病态或修正项较大时，SMW公式可能数值不稳定。实践中常采用：对I + VᵀA⁻¹U进行Cholesky分解（当矩阵对称正定时）使用QR分解等数值稳定方法添加正则化项改善条件数