QR Decomposition (QRD)

Unlike solving the Normal Equation directly, QRD avoids squaring the condition number of the data matrix. By operating on the original matrix A using orthogonal transformations, it prevents the amplification of rounding errors. This is critical for ill-conditioned correlation matrices common in wideband DPD where signal bandwidths are large and memory depth is high.

• Condition Number Preservation: The condition number of R equals that of A.
• No Explicit Matrix Inversion: The upper triangular structure of R allows solution via simple back-substitution.

QR decomposition transforms the overdetermined system Ax ≈ b into an equivalent, easily solvable form. By applying the transpose of Q to both sides, the problem reduces to solving Rx = Qᵀb. Since R is upper triangular, the optimal coefficient vector x is found through efficient back-substitution.

• Minimizes ||Ax - b||²: Directly solves the minimization problem without forming the normal equations.
• Residual Analysis: The bottom rows of Qᵀb directly provide the least squares residual norm.

The most common method for computing QRD in practice uses Householder reflections. These are elementary orthogonal transformations that zero out all elements below the diagonal of a column vector in a single step. This method is preferred over Gram-Schmidt for its superior numerical stability on finite-precision hardware.

• Block Operations: Householder vectors can be aggregated to apply transformations in matrix-matrix operations, maximizing cache efficiency on DSPs.
• Compact Storage: The reflection vectors can be stored in the lower triangular part of the original matrix, saving memory.

Givens rotations provide an alternative method for computing QRD by zeroing out matrix elements one at a time. While less efficient for batch computation, they are the fundamental building block for the QR-RLS adaptive algorithm. Givens rotations allow the triangular factor R to be updated directly when new data rows arrive, without recomputing the entire decomposition.

• Selective Zeroing: Targets specific matrix elements for elimination.
• Pipelined Hardware: The regular, rotation-based structure is highly amenable to systolic array implementation on FPGAs.

The upper triangular matrix R in QRD is mathematically equivalent to the Cholesky factor of the Gram matrix AᵀA. This connection reveals why QRD is superior: it computes the Cholesky factor directly from A without explicitly forming the product AᵀA, an operation that squares the condition number and introduces numerical instability.

• AᵀA = RᵀR: The Gram matrix is the product of the transpose of R and R.
• Square-Root Algorithm: QRD is often called a "square-root" method because it works on the data matrix directly, analogous to taking the square root of the correlation matrix.

Column pivoting can be integrated into the QRD process to handle rank-deficient or near-rank-deficient matrices. By reordering columns based on their norm, the algorithm produces a factorization where the diagonal elements of R are non-increasing. This reveals the numerical rank and allows for effective regularization by truncating small diagonal elements, preventing overfitting in coefficient extraction.

• Diagonal Inspection: The magnitude of diagonal entries of R indicates linear independence of basis functions.
• Truncated SVD Alternative: Provides a computationally cheaper alternative to full SVD for regularization.

The ratio of the largest to smallest singular value of a matrix, denoted κ(A) = σₘₐₓ / σₘᵢₙ. It quantifies how sensitive the solution of a linear system is to perturbations in the input data. In DPD coefficient estimation:

• κ ≈ 1: Well-conditioned, stable solution
• κ > 10⁴: Ill-conditioned, small measurement noise causes large coefficient errors QR decomposition with column pivoting helps mitigate ill-conditioning by reordering columns to keep R well-conditioned.

The closed-form solution w = (XᵀX)⁻¹Xᵀy to the linear least squares problem. While conceptually simple, solving via the normal equation squares the condition number: κ(XᵀX) = κ(X)². This makes it dangerously unstable for DPD applications where data matrices are often ill-conditioned. QR decomposition avoids this squaring effect by operating directly on X, making it the standard approach for production DPD coefficient extraction.