Givens Rotation

A Givens rotation is defined by a rotation matrix that is orthogonal by construction. This means its transpose equals its inverse, ensuring that the Euclidean norm of the transformed vector is exactly preserved. In QR decomposition, this property prevents the amplification of rounding errors that plague direct matrix inversion methods. The rotation is parameterized by cosine and sine values derived from the two elements being operated on.

The primary purpose of a Givens rotation is to introduce a zero at a specific position in a matrix. When applied to a pair of elements in a column vector, the rotation angle is chosen such that one of the two resulting elements becomes exactly zero. This is achieved by setting:

• c = a / sqrt(a² + b²)
• s = -b / sqrt(a² + b²) This selective annihilation is what enables the systematic triangularization of a matrix in QR decomposition.

Unlike Householder reflections, Givens rotations operate on only two rows at a time, making them ideal for updating an existing triangular factor when new data arrives. In QR-RLS algorithms, this avoids the catastrophic cancellation and square-root breakdown that can occur in the conventional RLS update. The rotation is applied directly to the square-root of the inverse correlation matrix, maintaining positive definiteness by construction.

A single Givens rotation applied to a matrix row pair requires:

• Square-root operation to compute the normalization factor
• 6 multiplications and 2 additions per column element
• No pivoting required for the zeroing operation For an m × n matrix, approximately 3n² rotations are needed for full triangularization. In systolic array implementations, these rotations can be pipelined across processing elements for high-throughput real-time DPD coefficient updates.

In digital predistortion, the QR-RLS algorithm uses Givens rotations to maintain the Cholesky factor of the input correlation matrix. When a new sample arrives:

1. The new data row is appended to the existing triangular factor
2. A sequence of Givens rotations annihilates the appended row
3. The updated triangular factor is used to solve for new DPD coefficients This approach avoids explicit matrix inversion and provides superior numerical conditioning for ill-conditioned input signals common in wideband predistortion applications.

Givens rotations are one of three classical methods for QR decomposition, alongside:

• Householder reflections: More efficient for batch processing of dense matrices
• Gram-Schmidt orthogonalization: Simpler but less numerically stable Givens rotations are preferred in adaptive filtering because they can update an existing decomposition incrementally without recomputing from scratch. This makes them the method of choice for real-time DPD systems where coefficient updates must track time-varying power amplifier characteristics.

The matrix factorization that Givens rotations are designed to compute. QRD factors a matrix A into an orthogonal matrix Q and an upper triangular matrix R (A = QR). This is the foundational step for solving linear least squares problems without forming the normal equations, which squares the condition number. Givens rotations perform QRD by selectively zeroing elements below the diagonal, one at a time.

A numerically robust implementation of Recursive Least Squares that uses Givens rotations as its core update mechanism. Instead of updating the inverse correlation matrix directly, QR-RLS maintains and updates the Cholesky factor (square root) of the data matrix. This square-root approach doubles the precision of conventional RLS, making it the preferred choice for fixed-point DSP implementations where dynamic range is limited.

An alternative orthogonal transformation that zeros out all subdiagonal elements of a column vector in a single step, unlike Givens rotations which zero one element at a time. A Householder reflector is defined as H = I - 2vvᵀ, where v is a unit vector. While more efficient for batch QRD of dense matrices, Householder is less suited for adaptive filtering because it cannot selectively update a single row without recomputing the entire decomposition.

Factors a symmetric positive-definite matrix A into LLᵀ, where L is lower triangular. In the context of RLS, the inverse correlation matrix is symmetric positive-definite, and QR-RLS effectively updates its Cholesky factor directly using Givens rotations. This avoids the numerical instability of explicitly forming and inverting the correlation matrix, which is the primary failure mode of conventional RLS in finite-precision arithmetic.

A scalar κ(A) = σₘₐₓ / σₘᵢₙ that quantifies how sensitive the solution of a linear system is to perturbations in the input data. A high condition number indicates an ill-conditioned problem where small rounding errors are amplified catastrophically. Givens rotations are backward stable, meaning they introduce errors no larger than those caused by perturbing the original data by machine epsilon, regardless of the condition number.

A hardware design pattern where a grid of identical processing elements rhythmically compute and pass data, ideal for implementing Givens rotations in FPGA or ASIC for real-time DPD. Each cell in the array performs a boundary rotation (generating sine/cosine parameters) or an internal rotation (applying them). This pipelined approach achieves high throughput with minimal memory access, critical for wideband 5G linearization where sample rates exceed 1 GS/s.