Rank-1 Cholesky update: given L where LLᵀ = A, compute L' where L'L'ᵀ = A + vvᵀ. More...
#include "config.h"#include "fused/fused_matrix.h"#include "fused/fused_vector.h"#include "math/math_utils.h"
Include dependency graph for cholesky_update.h:
Go to the source code of this file.
Namespaces | |
| namespace | matrix_algorithms |
Functions | |
| template<typename T , my_size_t N> | |
| FusedMatrix< T, N, N > | matrix_algorithms::cholesky_rank1_update (const FusedMatrix< T, N, N > &L, const FusedVector< T, N > &v) |
| Rank-1 Cholesky update: compute L' where L'L'ᵀ = LLᵀ + vvᵀ. | |
Detailed Description
Rank-1 Cholesky update: given L where LLᵀ = A, compute L' where L'L'ᵀ = A + vvᵀ.
Updates an existing Cholesky factor in O(N²) without recomputing the full O(N³) decomposition. Essential for streaming/online covariance updates, recursive least squares, and square-root Kalman filters.
ALGORITHM
Uses Givens rotations to incorporate the rank-1 perturbation:
p = v (work vector, modified in place) For k = 0 … N−1: r = sqrt(L(k,k)² + p(k)²) c = L(k,k) / r s = p(k) / r L'(k,k) = r For i = k+1 … N−1: tmp = L(i,k) L'(i,k) = c · tmp + s · p(i) p(i) = c · p(i) - s · tmp
Complexity: O(N²) multiply-adds, O(N) square roots.
- Note
- Only the update (A + vvᵀ) is provided. The downdate (A - vvᵀ) requires hyperbolic rotations and can fail if the result is not positive definite. Downdate may be added in a future revision.
