Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Woodbury matrix identity
Résumé
In mathematics (specifically linear algebra), the Woodbury matrix identity, named after Max A. Woodbury, says that the inverse of a rank-k correction of some matrix can be computed by doing a rank-k correction to the inverse of the original matrix. Alternative names for this formula are the matrix inversion lemma, Sherman–Morrison–Woodbury formula or just Woodbury formula. However, the identity appeared in several papers before the Woodbury report.
The Woodbury matrix identity is
where A, U, C and V are conformable matrices: A is n×n, C is k×k, U is n×k, and V is k×n. This can be derived using blockwise matrix inversion.
While the identity is primarily used on matrices, it holds in a general ring or in an .
The Woodbury matrix identity allows cheap computation of inverses and solutions to linear equations. However, little is known about the numerical stability of the formula. There are no published results concerning its error bounds. Anecdotal evidence suggests that it may diverge even for seemingly benign examples (when both the original and modified matrices are well-conditioned).
To prove this result, we will start by proving a simpler one. Replacing A and C with the identity matrix I, we obtain another identity which is a bit simpler:
To recover the original equation from this reduced identity, set and .
This identity itself can be viewed as the combination of two simpler identities. We obtain the first identity from
thus,
and similarly
The second identity is the so-called push-through identity
that we obtain from
after multiplying by on the right and by on the left.
Putting all together,
where the first and second equality come from the first and second identity, respectively.
When are vectors, the identity reduces to the Sherman–Morrison formula.
In the scalar case, the reduced version is simply
If n = k and U = V = In is the identity matrix, then
Continuing with the merging of the terms of the far right-hand side of the above equation results in Hua's identity
Another useful form of the same identity is
which, unlike those above, is valid even if is singular, and has a recursive structure that yields
if the spectral radius of is less than one.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.