PaperlayerView exact revision on arXiv

Source-linked AI summary

Low-Complexity Polynomial Channel Estimation in Large-Scale MIMO with Arbitrary Statistics

Nafiseh Shariati, Emil Björnson, Mats Bengtsson, Mérouane Debbah

arXiv:1401.5703v2cs.IT

TL;DR

The paper addresses the high computational cost of pilot-based MMSE channel estimation in large-scale MIMO. It introduces PEACH estimators that replace covariance-matrix inversion with optimized finite-degree polynomials, achieving near-optimal MSE with lower complexity. The paper also identifies diagonalized estimation as a useful alternative in high-power noise-limited scenarios.

  • Problem

    Pilot-based MMSE estimation is computationally expensive in large-scale MIMO because covariance-matrix inversion has cubic complexity in the matrix dimension.

  • Method

    PEACH estimators approximate the MMSE covariance-matrix inverse with an L-degree polynomial whose coefficients are optimized for low MSE.

  • Results

    Near-optimal MSE is achieved at small L, while exact complexity analysis shows PEACH estimators are beneficial for practically large systems.

  • Takeaways & Limitations

    L need not scale with system dimensions, and pilot contamination can allow good PEACH performance at smaller L than noise-limited operation.

Abstract

from arXiv · show

This paper considers pilot-based channel estimation in large-scale multiple-input multiple-output (MIMO) communication systems, also known as massive MIMO, where there are hundreds of antennas at one side of the link. Motivated by the fact that computational complexity is one of the main challenges in such systems, a set of low-complexity Bayesian channel estimators, coined Polynomial ExpAnsion CHannel (PEACH) estimators, are introduced for arbitrary channel and interference statistics. While the conventional minimum mean square error (MMSE) estimator has cubic complexity in the dimension of the covariance matrices, due to an inversion operation, our proposed estimators significantly reduce this to square complexity by approximating the inverse by a L-degree matrix polynomial. The coefficients of the polynomial are optimized to minimize the mean square error (MSE) of the estimate. We show numerically that near-optimal MSEs are achieved with low polynomial degrees. We also derive the exact computational complexity of the proposed estimators, in terms of the floating-point operations (FLOPs), by which we prove that the proposed estimators outperform the conventional estimators in large-scale MIMO systems of practical dimensions while providing a reasonable MSEs. Moreover, we show that L needs not scale with the system dimensions to maintain a certain normalized MSE. By analyzing different interference scenarios, we observe that the relative MSE loss of using the low-complexity PEACH estimators is smaller in realistic scenarios with pilot contamination. On the other hand, PEACH estimators are not well suited for noise-limited scenarios with high pilot power; therefore, we also introduce the low-complexity diagonalized estimator that performs well in this regime. Finally, we ...

I. INTRODUCTION

Large-scale MIMO can improve spectral and energy efficiency, but practical gains depend on accurate CSI and computationally feasible pilot-based estimation. The paper motivates polynomial-expansion estimators for arbitrary channel and interference statistics.

  • Large-scale MIMO uses hundreds of antennas to increase spatial resolution, array gain, and spatial reuse.
  • Accurate instantaneous CSI is required to exploit large-scale MIMO's spatial resolution, and pilots are used to estimate channel coefficients.
  • MMSE and MVU estimators require covariance-matrix inversions with cubic computational complexity, which is prohibitive for large-scale systems with spatial correlation.
  • Polynomial expansion approximates matrix functions with an L-degree polynomial, enabling low-complexity alternatives to matrix inversion.
  • PEACH estimators optimize polynomial coefficients for low MSE, achieve good performance at low degrees, and need not increase L with antenna count.
  • The paper evaluates low-complexity Bayesian estimators under arbitrary channel and disturbance statistics, including pilot contamination.

A. Complexity Issues in Large-Scale MIMO Systems

Large-scale MIMO makes conventional covariance inversion computationally expensive because pilot length and receiver dimensions produce large matrices. Diagonalization reduces complexity substantially, but discards statistical dependence and is mainly effective in high-SNR noise-limited conditions.

  • MMSE and MVU estimation scale as O(M^3), where M = BNr, while large-scale systems require B of the same order as Nt.
  • For Nr = 200 and Nt = B = 20, conventional estimation requires inverting 4000×4000 matrices at approximately 3.4 · 10^11 FLOPs.
  • Classical inversion has cubic scaling, whereas the proposed estimators target O(M^2) complexity and can be beneficial at practical matrix dimensions.
  • The diagonalized estimator reduces computation by zeroing covariance off-diagonal elements and can precompute its matrix factor with complexity proportional to M.
  • In noise-limited settings with S = σ^2I, the diagonalized estimator's MSE approaches zero as pilot power Pt increases.
  • Diagonalization performs well mainly at high SNR because it ignores dependence among received pilots and channel coefficients, limiting MSE improvements elsewhere.

III. LOW-COMPLEXITY BAYESIAN PEACH ESTIMATORS

The PEACH approach approximates covariance-matrix inverses with finite-degree polynomial expansions. Truncation provides a tunable trade-off between approximation error and computational complexity.

  • Polynomial-expansion Bayesian estimators are proposed to reduce the complexity of MMSE channel estimation.
  • An L-degree polynomial retains terms l = 0, ..., L to approximate the matrix inverse.
  • Because eigenvalue contributions decrease with polynomial order, L need not scale with matrix dimension for a target per-element accuracy.
  • The polynomial degree L is selected to balance approximation error against computational complexity.

A. Unweighted PEACH Estimator

The PEACH estimator approximates the Bayesian MMSE estimator with an L-degree polynomial, replacing matrix inversion with matrix-vector multiplications. Its complexity is O(LM^2), and it converges to MMSE as L increases.

  • A. Unweighted PEACH Estimator: PEACH applies an L-degree polynomial approximation to the Bayesian MMSE channel estimator.The approximation is formed by applying the polynomial expansion to the MMSE expression.
  • A. Unweighted PEACH Estimator: The estimator requires no matrix inversions and uses only matrix-vector multiplications.This structure enables recursive computation and avoids the cubic-cost inversion in the original estimator.
  • A. Unweighted PEACH Estimator: O(LM^2) is the computational complexity of PEACH, compared with O(M^3) for the conventional MMSE estimator.The reduction is substantial when L is much smaller than M.
  • A. Unweighted PEACH Estimator: PEACH achieves an analytically characterized mean-square error determined by the polynomial approximation.The MSE follows from direct computation using the estimation-error definition.
  • A. Unweighted PEACH Estimator: The scaling parameter α is selected to satisfy convergence conditions and influences the polynomial's convergence speed.A trace-based choice can reduce complexity, while eigenvalue-based choices target faster asymptotic convergence.

B. Weighted PEACH Estimator

Weighted PEACH generalizes the polynomial estimator by optimizing one coefficient per polynomial term for each fixed degree. This can improve finite-degree MSE, but exact weight optimization has cubic complexity and therefore requires approximation for low-complexity use.

  • B. Weighted PEACH Estimator: Weighted PEACH assigns independently optimized coefficients to polynomial terms instead of using the unweighted expansion's common scaling.The coefficients are selected for a specific polynomial degree and pilot matrix.
  • B. Weighted PEACH Estimator: The MSE-minimizing weights solve an (L+1)-equation linear system.Stationarity with respect to the L+1 coefficients yields the system Aw = b.
  • B. Weighted PEACH Estimator: The optimal weighted estimator has a closed-form MSE obtained by substituting wopt = A^-1b into the MSE expression.The resulting minimum MSE is expressed using the channel covariance trace and the quadratic weight terms.
  • B. Weighted PEACH Estimator: The PEACH and W-PEACH MSE expressions are independent of the channel and disturbance mean matrices.Thus, their performance is the same under the corresponding nonzero-mean and zero-mean formulations.
  • B. Weighted PEACH Estimator: Exact optimal-weight computation has O(M^3) complexity, so it does not preserve the asymptotic advantage without a low-complexity approximation.The cubic cost comes from pure matrix multiplications involving powers of Z.
  • B. Weighted PEACH Estimator: The PE technique also applies to MVU and other channel estimators involving matrix inversions, subject to their respective assumptions.For MVU, a regularization factor is introduced before applying the polynomial approximation.

C. Low-Complexity Weights

The low-complexity W-PEACH procedure estimates polynomial weights from a sliding window of received signals and updates them recursively. Its per-time-step cost scales as O(LM^2), with additional O(L^3) weight solving.

  • C. Low-Complexity Weights: The sample covariance approximation is consistent for sufficiently large windows, although trace estimation can work with smaller T.The text notes that T much larger than BN_r is generally needed for consistency, while smaller windows may suffice for traces.
  • C. Low-Complexity Weights: Algorithm 1 updates covariance-related quantities and approximate weights using a sliding window of received signals.At time t, it uses signals from yt through yt-T+1 and previous approximations.
  • C. Low-Complexity Weights: Solving for the approximate weights adds O(L^3) complexity, after which the W-PEACH estimate is computed recursively.The algorithm outputs approximate weights at each time instant.
  • C. Low-Complexity Weights: O(LM^2) FLOPs per time instant are required to compute the approximations of A and b.The cost arises from vector-matrix and matrix-vector products for each polynomial-related element.
  • C. Low-Complexity Weights: The procedure can use imperfect covariance estimates and thereby support adaptive tracking of slowly varying channel and disturbance statistics.The practical relevance is assessed through numerical estimation with statistical mismatch.
  • C. Low-Complexity Weights: Trace terms can be approximated with random vectors when direct computation is inconvenient.This approach is used for terms such as tr(eP R^2 eP^H).

D. Imperfect Covariance Matrix Estimation

The proposed covariance estimator shrinks the sample covariance toward its diagonal to improve estimation in large dimensions. Its shrinkage parameter balances rapidly converging diagonal information against unreliable off-diagonal estimates.

  • D. Imperfect Covariance Matrix Estimation: Pure sample covariance estimation is unsuitable when the number of observations is smaller than the covariance dimension, because the estimate is then non-invertible.This issue is especially relevant for channel covariance matrices with dimension N_tN_r.
  • D. Imperfect Covariance Matrix Estimation: The estimator uses Ĉ = κC_d + (1 − κ)C_sample, where C_d contains the sample covariance's diagonal.κ is chosen to minimize the expected squared Frobenius-norm difference from the true covariance.
  • D. Imperfect Covariance Matrix Estimation: The diagonal elements converge quickly with N, while κ controls reliance on the off-diagonal sample estimates.This balances stable diagonal information against potentially noisy off-diagonal information.
  • D. Imperfect Covariance Matrix Estimation: As N grows, the optimal κ decreases, indicating greater trust in the sample covariance.The resulting W-PEACH estimator adapts well to imperfect statistical knowledge in the reported numerical study.

E. Asymptotic and Exact Computational Complexity

The conventional MMSE and MVU estimators have cubic complexity, whereas PEACH reduces the dominant scaling to quadratic complexity when the polynomial degree remains fixed. Exact FLOP analysis identifies practical antenna regimes where PEACH and W-PEACH outperform MMSE, while matrix-vector operations also support parallel implementation.

  • Asymptotic complexity: O(BN_r)^3 complexity of conventional MMSE and MVU estimators is reduced to O((BN_r)^2) for PEACH and W-PEACH when L is fixed.The polynomial degree affects complexity but need not scale with the number of antennas.
  • Practical motivation: Because statistics change continuously in practice, conventional inversion may need to be recomputed every few seconds rather than reused indefinitely.Recursive MMSE implementations still have cubic complexity because stable covariance estimation requires more than M recursions.
  • Exact FLOP analysis: PEACH requires 2LM^2 + ((4L + 2)N − 2L)M + 2(L + 1)N^2 − 2(L + 1)N FLOPs.This is the exact total complexity expression given for PEACH.
  • Exact FLOP analysis: W-PEACH requires 4LM^2 + (8L + 4)MN + (4L + 4)N^2 + M − (4L + 3)N + 1 FLOPs.Its polynomial structure has the same estimator computation cost as PEACH, with additional work for the weight vector and Algorithm 1.
  • Practical complexity conditions: For Q = 50 and L = 2, PEACH is less complex than MMSE for M ≥ 167, while W-PEACH is less complex for M ≥ 357.Examples include PEACH with N_t = 2, N_r = 100 and W-PEACH with N_t = 4, N_r = 100.
  • Implementation implications: PEACH uses matrix-vector multiplications that are easier to parallelize and implement in hardware than MMSE/MVU matrix inversions.This can reduce computational delay and energy when FLOP counts are similar.

IV. PERFORMANCE EVALUATION

The evaluation studies the proposed diagonalized, PEACH, and W-PEACH estimators under noise-limited and cellular pilot-contamination scenarios. It combines asymptotic analysis with numerical results for both interference settings.

  • Evaluation scope: The evaluation compares diagonalized, PEACH, and W-PEACH estimators across noise-limited and pilot-contaminated cellular scenarios.Pilot contamination is treated in more detail because it is a major challenge in large-scale MIMO.
  • Evaluation scope: Both asymptotic analysis and numerical results are used to assess estimator performance in the two scenarios.

A. Noise-Limited Scenario

In the noise-limited setting, the diagonalized estimator retains asymptotically optimal behavior at high pilot power, whereas PEACH and W-PEACH converge to non-zero MSE floors. Thus, approximating the full inverse is less suitable than diagonalization in this regime.

  • Asymptotic behavior: The diagonalized estimator has the same asymptotically optimal high-power behavior as MMSE in the noise-limited scenario.For uncorrelated receiver noise, MMSE MSE is known to approach zero as pilot power increases.
  • Asymptotic behavior: As pilot power P_t → ∞, PEACH and W-PEACH MSEs converge to non-zero error floors independent of P_t.The same non-zero-floor behavior holds for any α selection satisfying the stated condition for PEACH.
  • Estimator choice: In high-power noise-limited operation, ignoring spatial correlation with diagonalization is preferable to approximating the full matrix inversion with PEACH.This conclusion follows from the non-zero PEACH and W-PEACH MSE floors.

B. Pilot Contamination Scenario

Under pilot contamination, all estimators exhibit non-zero high-power MSE floors determined by desired and interfering channel covariances. Only overlapping pilot subspaces cause interference, and PEACH requires the sum covariance of the interfering channels.

  • Covariance requirements: PEACH needs the sum covariance matrix of interfering channels, whereas the diagonalized estimator uses only its diagonal elements.
  • Interference model: Only interfering pilots with overlapping span, P_iP^H ≠ 0, contaminate the desired pilot signaling.The synchronized common-pilot case is identified as a canonical, worst-case assumption.
  • MMSE and diagonalized estimators: As P_t → ∞, MMSE and diagonalized estimators converge to non-zero MSE floors caused by pilot contamination.The floors are characterized by the covariance matrices of the desired and interfering channels.
  • PEACH estimators: As P_t → ∞, PEACH and W-PEACH also converge to non-zero MSE floors that depend on desired and interfering channel covariance matrices.These floors do not depend on pilot power or noise power.
  • Overall comparison: All four estimators saturate as pilot power grows under pilot contamination, unlike the noise-limited MMSE and diagonalized cases.PEACH estimators also saturate in the noise-limited case, while MMSE and diagonalized saturation there is specifically due to contamination.

C. Numerical Examples

The numerical examples compare PEACH-family and conventional estimators across interference, SNR, antenna dimension, covariance knowledge, and computational-complexity settings. W-PEACH is near-optimal at low degree, PEACH complexity is lowest, and estimator advantages depend on interference and SNR.

  • Interference and polynomial degree: At γ = 5 dB, W-PEACH approaches MMSE quickly as L increases and outperforms MVU, diagonalized, and PEACH estimators across interference scenarios.PEACH also outperforms conventional alternatives under pilot contamination and at sufficiently large L in the noise-limited case.
  • SNR dependence: With L = 10, PEACH and W-PEACH converge to non-zero MSE floors as γ increases, while pilot contamination drives all estimators toward non-zero floors.Under contamination, the SINR approaches a constant as pilot power increases, making the MSE independent of pilot power in the high-SNR limit.
  • SNR dependence: Pilot contamination reduces the performance gap between W-PEACH and MMSE; for β = 1, W-PEACH matches MMSE, making PEACH estimators near-optimal in realistic scenarios.In the noise-limited case, PEACH estimators saturate because of approximation bias, whereas contamination limits the attainable SINR for all estimators.
  • Estimator regimes: The diagonalized estimator’s MSE tends to zero in the noise-limited high-SNR regime, while PEACH estimators retain an advantage across the SNR range under pilot contamination.Thus, PEACH estimators are most useful at low and medium SNRs in noise-limited settings.
  • Antenna scaling: For fixed L, normalized performance shows no clear dependence on the channel dimensions, indicating that polynomial degree need not scale with the number of antennas.The MSE is determined by the approximation accuracy achieved for the matrix inversion at that degree.
  • Statistical uncertainty: The approximate W-PEACH weights achieve almost identical performance to optimal weights, while W-PEACH remains robust with estimated covariance matrices and close to MMSE.The covariance-uncertainty experiment uses fewer samples than the matrix dimension and still reports reasonably good performance.
  • Computational complexity: PEACH has the lowest computational complexity; with L = 4, W-PEACH is less complex than MMSE for Nr ≥65 when Q = 50 and Nr ≥135 when Q = 100.At L = 2, the corresponding thresholds are Nr ≥35 for Q = 50 and Nr ≥73 for Q = 100.

V. CONCLUSIONS

The paper proposes PEACH estimators that replace covariance-matrix inversion with low-degree matrix polynomials to reduce channel-estimation complexity in large-scale MIMO. Exact analyses and numerical evaluations show favorable complexity–MSE trade-offs, with performance depending on polynomial degree and interference conditions.

  • Estimator design: PEACH estimators approximate the MMSE covariance-matrix inversion with an L-degree matrix polynomial to address the complexity of pilot-based channel estimation.The conventional estimators are described as unsuitable for real-time large-scale MIMO systems because of their computational complexity.
  • Estimator design: The polynomial coefficients are optimized for each degree L, yielding near-optimal MSE at small degrees while L need not scale with system dimensions.The degree can be selected to balance complexity and MSE performance.
  • Complexity analysis: Exact FLOP analyses show that PEACH estimators are beneficial for practically large systems under different channel-stationarity assumptions and polynomial degrees.Figures 7 and 8 evaluate computational complexity versus the number of received antennas for L = 2 and L = 4, respectively.
  • Interference conditions: Pilot contamination enables good PEACH performance at smaller L than noise-limited conditions, although it generally creates an MSE floor.The relative complexity–accuracy behavior differs across interference regimes.
  • Interference conditions: The diagonalized estimator is a lower-complexity alternative in noise-limited, high-SNR scenarios, while PEACH estimators outperform it across the SNR range under pilot contamination.The proposed estimators are also reported to be robust to imperfect channel covariance matrices.
Loading 1401.5703v2…