The Woodbury Matrix Identity
Updating an inverse cheaply — the trick behind Kalman filters and online regression.
On this page
The one-sentence idea: if you already know the answer to a hard problem, and the problem only changes a little, there's often a shortcut to the new answer that's much cheaper than solving the whole thing again from scratch — Woodbury is exactly that shortcut, specifically for matrix inverses.
Beginner: inverting a matrix (section 1.6) is expensive — roughly O(n³). But what if you already have the inverse of a matrix, and you only need to update it slightly (say, adding one new data point to a dataset)? Recomputing the whole inverse from scratch every time would be wasteful.
Intermediate: the Woodbury matrix identity (also called the matrix inversion lemma) gives a formula for the inverse of a matrix after a low-rank update, expressed entirely in terms of the original inverse — turning an expensive full O(n³) re-inversion into a much cheaper update.
Advanced: this is exactly the trick that makes online/streaming algorithms practical: a Kalman filter updates its covariance estimate every time a new measurement arrives, and a Gaussian process can incorporate one new observation, both without ever recomputing a full matrix inverse from scratch at every single step.
Dense as this looks, the key point is simple: if A is n×n but U, C, V represent only a small (rank-k) update, the right-hand side only ever needs to invert a small k×k matrix instead of a full n×n one.
The cleanest proof of a claimed inverse formula is to just multiply it by the original matrix and check the result is the identity. Let B = A⁻¹ − A⁻¹U(C⁻¹ + VA⁻¹U)⁻¹VA⁻¹ be the claimed inverse of (A + UCV). Multiply them together and distribute:
Group the last three terms, all of which share a common right-hand factor of (C⁻¹ + VA⁻¹U)⁻¹VA⁻¹ once UCVA⁻¹ is rewritten as UC(C⁻¹ + VA⁻¹U)(C⁻¹ + VA⁻¹U)⁻¹VA⁻¹:
The bracket is exactly CC⁻¹ − I = 0, so everything past the leading I vanishes and (A + UCV)B = I — confirming B really is the inverse, purely by algebra, with no assumption needed beyond the relevant inverses existing.
Where this is used: recursive least squares and Kalman filters (an O(n³) covariance re-inversion at every timestep would make real-time filtering infeasible), Gaussian process regression when adding one new observation, and low-rank adaptation (LoRA) style updates to large weight matrices in deep learning.
Let A = [[2, 0], [0, 2]] (so A⁻¹ = [[0.5, 0], [0, 0.5]]), and update it with u = [1, 1] so A_new = A + uuᵀ = [[3, 1], [1, 3]]. Direct inversion gives A_new⁻¹ = [[0.375, −0.125], [−0.125, 0.375]]. Sherman-Morrison instead computes A⁻¹u = [0.5, 0.5], then 1 + uᵀA⁻¹u = 1 + 0.5 + 0.5 = 2, giving A_new⁻¹ = A⁻¹ − (A⁻¹u)(A⁻¹u)ᵀ / 2 = [[0.5,0],[0,0.5]] − [[0.125,0.125],[0.125,0.125]] = [[0.375, −0.125], [−0.125, 0.375]] — the exact same answer, using only vector operations on the already-known A⁻¹, never re-inverting the full 2×2 matrix.
This special rank-1 case is called the Sherman-Morrison formula — the same idea as Woodbury, just for the simplest possible update.
import numpy as np
n = 200
A = np.eye(n) * 2 + np.random.rand(n, n) * 0.01
A_inv = np.linalg.inv(A) # expensive, done once
# A rank-1 update: A_new = A + u @ u.T
u = np.random.rand(n, 1)
A_new = A + u @ u.T
# Full recomputation (the slow way):
A_new_inv_direct = np.linalg.inv(A_new)
# Sherman-Morrison (Woodbury's rank-1 special case):
Ainv_u = A_inv @ u
A_new_inv_fast = A_inv - (Ainv_u @ Ainv_u.T) / (1 + (u.T @ Ainv_u)[0, 0])
print(np.allclose(A_new_inv_direct, A_new_inv_fast)) # True, much cheaper to compute- Kalman filters (robotics, GPS, finance) use exactly this identity to update state covariance estimates efficiently every time a new sensor reading arrives.
- Online/recursive least squares updates a regression model's solution as new data streams in, without recomputing the full normal-equation inverse from section 1.6 each time.
- Gaussian process libraries use Woodbury-style updates to add new training points incrementally, avoiding a full
O(n³)Cholesky refactorization (section 1.15) every time.
- Applying Woodbury when the "update" isn't actually low-rank — the whole benefit disappears if k is comparable to n; it's specifically a low-rank-update trick.
- Forgetting numerical stability still matters — repeated incremental updates can accumulate floating-point drift, and long-running online systems often periodically recompute a fresh, exact inverse to correct for it.
Going deeper
The Woodbury identity is, algebraically, a generalization of the simple scalar fact that 1/(a+bc) can be rewritten in terms of 1/a when bc is "small" relative to a — matrix inversion has a genuine analogue of this same idea, just dressed up in more notation.
At the master level: the Woodbury identity is one of the standard tools that makes Bayesian linear regression and Gaussian process regression tractable at scale — both rely on repeatedly manipulating covariance matrices under low-rank updates, and naive full re-inversion at every step would make either approach computationally infeasible for any real dataset size.