Cholesky Decomposition

The Cholesky decomposition exists uniquely if and only if the input matrix A is symmetric and positive-definite.

• Symmetry: A = Aᵀ, meaning the autocorrelation matrix in RLS must be Hermitian.
• Positive-definiteness: All eigenvalues are strictly greater than zero, ensuring the decomposition yields a real, non-singular lower triangular factor.
• Practical implication: In DPD coefficient estimation, the input correlation matrix naturally satisfies this property as long as the input signal is persistently exciting and the regularization parameter is appropriately chosen.

Cholesky decomposition requires approximately n³/3 floating-point operations, making it roughly twice as fast as LU decomposition and significantly cheaper than QR decomposition for solving linear systems.

• Storage advantage: Only the lower triangular factor L needs to be stored, halving memory requirements compared to storing the full matrix.
• RLS context: The inverse correlation matrix update in conventional RLS has O(n²) complexity. Cholesky-based formulations maintain this complexity but with improved numerical stability.
• Comparison: While QR-RLS offers superior numerical stability, Cholesky-based RLS provides a favorable speed-stability tradeoff for many embedded DPD applications.

Two primary Cholesky formulations exist for adaptive filtering:

• Square-root Cholesky: Factorizes A = LLᵀ, where L has the square root of the matrix on its diagonal. This is the standard form.
• LDLᵀ decomposition: Factorizes A = LDLᵀ, where L is unit lower triangular (ones on diagonal) and D is a diagonal matrix. This variant avoids square-root operations, which is advantageous for fixed-point hardware implementations.
• Numerical benefit: Both variants have condition numbers that are the square root of the original matrix, halving the sensitivity to roundoff errors compared to direct matrix inversion.

A critical property for adaptive algorithms is the ability to efficiently update the Cholesky factor when the input correlation matrix changes.

• Rank-one update: When new data arrives, the correlation matrix is updated as R(k) = λR(k-1) + x(k)x(k)ᵀ. The Cholesky factor can be updated in O(n²) operations without full recomputation.
• Forgetting factor integration: The exponential weighting factor λ is seamlessly incorporated into the update recursion.
• Downdating: Removing stale data contributions (sliding window RLS) requires numerically stable downdate operations, which hyperbolic rotations can perform on the Cholesky factor.

Cholesky decomposition offers guaranteed numerical stability without pivoting, unlike LU decomposition.

• No pivot growth: The elements of L are bounded by the square root of the diagonal elements of A, preventing the catastrophic magnification of roundoff errors.
• Backward stability: The computed solution is the exact solution to a slightly perturbed problem, with error bounds proportional to the condition number of A.
• Fixed-point considerations: In FPGA-based DPD implementations, the LDLᵀ variant is preferred because it avoids square-root operations that are expensive in fixed-point arithmetic and can introduce quantization errors.

Cholesky decomposition directly solves the normal equation at the core of least squares estimation.

• The Wiener-Hopf equation Rw = p (where R is the autocorrelation matrix and p is the cross-correlation vector) is solved in two steps:
  1. Forward substitution: Solve Ly = p for y.
  2. Back substitution: Solve Lᵀw = y for the coefficient vector w.
• RLS connection: The recursive update of the Cholesky factor of R⁻¹ enables direct coefficient updates without explicitly solving the linear system at each iteration, maintaining O(n²) complexity.

The primary algorithm that leverages Cholesky decomposition for coefficient updates. RLS recursively computes the inverse of the input correlation matrix to achieve an order of magnitude faster convergence rate than LMS-based algorithms.

• Directly solves the Wiener-Hopf equation iteratively
• Requires O(N²) complexity per iteration, where N is the number of coefficients
• Cholesky factorization maintains the positive-definiteness of the correlation matrix during updates

A numerically robust variant of RLS that uses Givens rotations to directly update the Cholesky factor (square-root) of the inverse correlation matrix. This avoids explicit matrix inversion and squares the condition number, doubling the numerical precision.

• Immune to loss of positive-definiteness from finite-precision arithmetic
• Ideal for fixed-point FPGA implementations
• Forms the basis for systolic array DPD processors

A symmetric matrix A is positive-definite if xᵀAx > 0 for all non-zero vectors x. The input autocorrelation matrix in DPD coefficient estimation naturally possesses this property.

• Guarantees the existence and uniqueness of the Cholesky factor
• Ensures the normal equation solution is a global minimum
• Regularization adds a diagonal loading term to enforce this property for ill-conditioned data

A scalar parameter (0 ≪ λ ≤ 1) that exponentially weights recent data more heavily in recursive estimation. In RLS with Cholesky updates, λ directly scales the downdating of the triangular factor.

• Typical values: 0.95 to 0.999 for tracking time-varying PA characteristics
• Lower λ provides faster tracking but higher misadjustment
• The effective memory of the algorithm is approximately 1/(1-λ) samples

The closed-form solution w = R⁻¹p where R is the autocorrelation matrix and p is the cross-correlation vector. Cholesky decomposition solves this system efficiently by forward and backward substitution without explicitly inverting R.

• Solving LLᵀw = p requires O(N³/6) operations for the factorization
• Numerically more stable than Gaussian elimination for symmetric systems
• Forms the batch solution for offline training of predistorter coefficients

The ratio of the largest to smallest singular value of the correlation matrix, quantifying solution sensitivity to input perturbations. Cholesky-based solvers are vulnerable to squared condition number effects.

• Ill-conditioned matrices (high condition number) amplify estimation noise
• Regularization (adding δI to R) artificially improves the condition number
• QR-RLS avoids squaring the condition number by operating on the square-root factor