Rank-1 updates in Linear Algebra in simple terms.
Let’s say that we have a missile travelling. The missile is using sensors to determine its position. The sensor data are stored in matrices. Every new, for example, nanosecond a new reading from the sensor arrives. It is really expensive to recompute the whole matrix of the readings for calibrations and other operations.
When the right-hand side of linear system changes but the matrix stays the same, then an LU factorization is needed to avoid computing the whole system again.
But what if the matrix changes?
It is possible to avoid refactoring even with a change in the matrix. For example, making a “Rank-one update”. That means adding to our matrix another matrix of rank one.
How we will avoid computing the inverse of the whole matrix?
The trick is using the Sherman-Morisson-Woodbury formula. The formula will give us the inverse of the matrix that results from a rank-one update but without computing the inverse multiple times.
It is clear that the inverse of A can be calculated only once. This allows us to work with matrix products that need O(n²) rather than computing the inverse in O(n³).
Solving the Linear System
Suppose we have a change in our matrix. We can obtain the following system:
And by using the Sherman-Morisson-Woodbury formula we obtain:
We can then follow the steps bellow:
Let’s look at an example
And now a small change occurs in position (3,2). From -3 we have -1.
We now need two update vectors so that the following stands.
These two work for our example.
Now lets compute step 1 and 2.
And finally, solve the linear system without the need to recompute the new matrix every time.
