In massive MIMO systems, base stations are equipped with tens or hundreds of antennas to serve multiple users simultaneously. To eliminate multi-user interference, the base station must perform linear precoding (on the downlink) and channel estimation or detection (on the uplink). The gold standard for these operations—such as Regularized Zero-Forcing (RZF) precoding or Minimum Mean Square Error (MMSE) estimation—requires inverting a large matrix.
For a system with $M$ antennas or $K$ users, direct matrix inversion demands an execution time that scales cubically ($O(M^3)$ or $O(K^3)$). As wireless networks scale to support massive antenna arrays, this cubic complexity becomes a critical hardware bottleneck, breaking the real-time computational budget of practical baseband processors.
Truncated Polynomial Expansion (TPE) bypasses this bottleneck entirely. It replaces the monolithic, computationally expensive matrix inverse with a short, weighted sum of matrix powers, transforming a cubic-complexity bottleneck into a series of highly parallelizable, low-complexity matrix-vector multiplications.
The Core Intuition: Matrix Inversion as a Polynomial
To understand why TPE works, consider the scalar geometric series. If you want to compute the inverse of a scalar $1 - x$ where $|x| < 1$, you can expand it into an infinite polynomial series:
$$\frac{1}{1-x} = 1 + x + x^2 + x^3 + \dots$$
If $x$ is small, you can truncate this series after just a few terms and still get a highly accurate approximation.
TPE applies this exact mathematical intuition to matrices. Let $\mathbf{A}$ be the matrix we need to invert (for example, the channel Gram matrix $\mathbf{H}\mathbf{H}^H + \sigma^2\mathbf{I}$ in RZF precoding). By shifting and scaling the matrix so that its eigenvalues fall within a bounded radius, we can express its inverse using a truncated Neumann series or an optimized matrix polynomial:
$$\mathbf{A}^{-1} \approx \sum_{k=0}^{L} c_k \mathbf{A}^k$$
where $c_k$ are scalar coefficients and $L$ is a small, fixed polynomial degree.
This algebraic shift fundamentally changes the nature of the computation. Instead of performing a direct matrix inversion, computing the precoded signal or estimated channel now requires calculating terms like $\mathbf{A}^k \mathbf{x}$. This can be computed iteratively as:
$$\mathbf{A}(\mathbf{A}(\dots \mathbf{A}(\mathbf{A}\mathbf{x})\dots))$$
By structuring the calculation this way, the baseband processor never multiplies a matrix by another matrix. It only performs sequential matrix-vector multiplications. As a result, the computational complexity drops from a cubic scaling law down to a quadratic or linear scaling law, which is perfectly suited for pipelined hardware architectures.
Why It Works: Asymptotic Magic in High Dimensions
A natural objection to this approximation is accuracy: do we not need an impractically large number of terms ($L \to \infty$) to get a faithful approximation of the inverse?
The breakthrough insight, rooted in Random Matrix Theory, is that in high-dimensional spaces, the eigenvalue spectrum of channel matrices stabilizes. As the number of antennas grows large, the empirical distribution of the matrix eigenvalues concentrates within a predictable, compact interval.
Because the eigenvalues are tightly bounded, a remarkably low-order polynomial is sufficient to approximate the inverse across the entire spectrum. Hoydis et al. demonstrated in Asymptotic Moments for Interference Mitigation in Correlated Fading Channels that a polynomial of degree six is sufficient to achieve near-optimal signal-to-interference-plus-noise ratios (SINR) compared to an exact, full matrix inversion.
Crucially, this means the required polynomial degree $L$ does not need to grow as you add more antennas to the system. Work by Mueller et al. in Linear precoding based on polynomial expansion: reducing complexity in massive MIMO and Shariati et al. in Low-Complexity Channel Estimation in Large-Scale MIMO using Polynomial Expansion proved that a low, fixed polynomial order maintains a consistent, negligible performance gap relative to exact inversion, regardless of the overall system dimensions. The approximation error remains bounded, making the approach infinitely scalable.
Achieving Linear Complexity Per User
While standard TPE reduces the global matrix operation complexity, researchers have found ways to optimize the framework further by tailoring the polynomials to individual users or cells.
In multi-cell environments, Kammoun et al. showed in Linear Precoding Based on Polynomial Expansion: Large-Scale Multi-Cell MIMO Systems that optimizing the polynomial coefficients using random matrix theory allows TPE to handle inter-cell interference efficiently, sometimes even outperforming standard RZF when channel state information is imperfect.
To drive complexity down even further, Sifaou et al. introduced a per-user polynomial expansion framework in Polynomial expansion of the precoder for power minimization in large-scale MIMO systems. Instead of computing a single massive matrix polynomial for the entire system, the authors apply a truncated expansion on a per-user basis. This slashes the computational complexity to $O(KM)$, a massive reduction from traditional methods requiring $O(K^2M)$ operations.
The authors extended this philosophy to fairness optimization in Max–Min SINR in Large-Scale Single-Cell MU-MIMO: Asymptotic Analysis and Low-Complexity Transceivers, utilizing User-Specific Truncated Polynomial Expansions (US-TPE). By replacing full matrix inversions with second- or third-order user-specific expansions, they reduced the computational complexity from quadratic to linear scaling relative to the number of users, all while maintaining near-optimal user fairness.
Application to Channel Estimation
The utility of polynomial expansion is not restricted to downlink precoding; it is equally powerful for uplink channel estimation. Minimum Mean Square Error (MMSE) channel estimation requires inverting large covariance matrices to suppress noise and pilot contamination.
To solve this, Shariati et al. proposed the PEACH (Polynomial ExpAnsion CHannel) estimator in Low-Complexity Polynomial Channel Estimation in Large-Scale MIMO With Arbitrary Statistics. By substituting the exact covariance inversion with an optimized finite-degree matrix polynomial, PEACH transforms a cubic $O(M^3)$ estimation problem into a quadratic $O(M^2)$ operation. This enables real-time, highly accurate channel estimation that remains robust even in the presence of severe pilot contamination.
The Broader Paradigm: Matrix-Free Iterative Methods
Truncated Polynomial Expansion belongs to a broader philosophy in signal processing: avoiding explicit matrix inversions and complex optimization solvers by using iterative, matrix-vector scaling operations. Several parallel lines of research exploit this same core intuition:
- Approximate Message Passing (AMP): For systems dealing with hardware non-linearities or peak-to-average power ratio (PAPR) constraints, Bereyhi et al. in RLS Precoding for Massive MIMO Systems with Nonlinear Front-End and Jamali et al. in PAPR-Limited Precoding in Massive MIMO Systems with Reflect- and Transmit-Array Antennas utilize the AMP framework. AMP solves complex non-linear optimization problems iteratively, ensuring that the computational complexity scales strictly linearly with the number of antennas.
- Power Iteration and Closed-Form Scaling: In systems assisted by Intelligent Reflecting Surfaces (IRS), traditional optimization relies on heavy semi-definite programming. Esmaeilbeig et al. demonstrated in Quantized Phase-Shift Design of Active IRS for Integrated Sensing and Communications that replacing these solvers with power-iteration methods reduces the mathematical overhead to simple matrix-vector multiplications. Similarly, Chen et al. in Active RIS-Assisted Multi-User Multi-Stream Transmit Precoding Relying on Scalable-Complexity Iterations leverage closed-form expressions and bisection methods to bypass cubic matrix operations entirely.
Ultimately, whether through TPE, AMP, or power iterations, the underlying breakthrough is the same: by leveraging the statistical properties of large matrices, we can trade exact, monolithic matrix algebra for simple, iterative polynomial expansions. This trade-off yields massive computational savings with virtually no loss in wireless performance.
Key Foundational Work
Asymptotic moments for interference mitigation in correlated fading channels (2011) — contributed 2 concept elements to this direction.
Polynomial expansion detector for uniform linear arrays (2011) — contributed 2 concept elements to this direction.
Efficient Compression of QRS Complexes Using Hermite Expansion (2012) — contributed 1 concept elements to this direction.