Source-linked AI summary
Low-Complexity Soft-Output Signal Detection Based on Gauss-Seidel Method for Uplink Multi-User Large-Scale MIMO Systems
Linglong Dai, Xinyu Gao, Xin Su, Shuangfeng Han, Chih-Lin I, Zhaocheng Wang
TL;DR
Uplink large-scale MIMO needs practical near-optimal detection because MMSE requires high-complexity matrix inversion. The paper uses GS iteration with diagonal initialization and approximate LLR computation, reducing complexity while retaining near-optimal performance with few iterations.
Problem
MMSE detection is near-optimal for uplink large-scale MIMO, but its matrix inversion has O(K^3) complexity and is costly for large K.
Method
The paper uses GS iteration to realize MMSE detection without inversion, adds a diagonal-approximate initial solution, and approximates LLR computation.
Results
The proposed algorithm reduces complexity from O(K^3) to O(K^2), outperforms the conventional Neumann-based method, and approaches MMSE and ML performance with few iterations.
Takeaways & Limitations
At i = 3, the approximated LLR method differs from exact LLR computation by within 0.1 dB, while preserving satisfying performance.
Abstract
from arXiv · showhide
For uplink large-scale MIMO systems, minimum mean square error (MMSE) algorithm is near-optimal but involves matrix inversion with high complexity. In this paper, we propose to exploit the Gauss-Seidel (GS) method to iteratively realize the MMSE algorithm without the complicated matrix inversion. To further accelerate the convergence rate and reduce the complexity, we propose a diagonal-approximate initial solution to the GS method, which is much closer to the final solution than the traditional zero-vector initial solution. We also propose a approximated method to compute log-likelihood ratios (LLRs) for soft channel decoding with a negligible performance loss. The analysis shows that the proposed GS-based algorithm can reduce the computational complexity from O(K^3) to O(K^2), where K is the number of users. Simulation results verify that the proposed algorithm outperforms the recently proposed Neumann series approximation algorithm, and achieves the near-optimal performance of the classical MMSE algorithm with a small number of iterations.
I. INTRODUCTION
Large-scale MIMO can improve spectrum and energy efficiency, but uplink detection must manage increased multi-user interference and the high complexity of existing detectors. The paper proposes a GS-based near-optimal detector that avoids matrix inversion and supports low-complexity LLR computation.
- I. INTRODUCTION: Large-scale MIMO equips base stations with many antennas to serve multiple single-antenna users simultaneously.The paper gives 128 or more antennas as an example.
- I. INTRODUCTION: Large-scale MIMO can achieve orders of increase in spectrum and energy efficiency.
- I. INTRODUCTION: ML detection is impractical at scale, while FSD and TS remain unaffordable for large dimensions or high modulation orders.ZF and MMSE offer near-optimal performance with lower complexity but still require costly matrix inversion.
- I. INTRODUCTION: The proposed GS detector iteratively realizes MMSE estimation without matrix inversion and uses diagonal approximation to accelerate convergence.An approximated LLR method is also introduced for soft channel decoding.
- I. INTRODUCTION: The GS method is reported as the first use of GS for uplink large-scale MIMO signal detection and reaches near-optimal MMSE performance with few iterations.
II. SYSTEM MODEL
The system models an uplink with many base-station antennas serving fewer users and formulates MMSE signal estimation and soft-output LLR computation. MMSE is near-optimal, but its required matrix inversion has O(K^3) complexity.
- II. SYSTEM MODEL: The uplink system uses N base-station antennas to serve K single-antenna users, typically with N ≫ K.The paper gives N = 128 and K = 16 as an example.
- II. SYSTEM MODEL: The received signal contains transmitted user symbols mapped from an energy-normalized modulation constellation and additive white Gaussian noise.The noise entries follow CN(0, σ2).
- II. SYSTEM MODEL: The base station estimates the transmitted vector s from the received vector y using the MMSE linear detector.The channel matrix H is obtained through training pilots.
- II. SYSTEM MODEL: The MMSE estimate uses the matched-filter output and filtering matrix W, with G = H^H H as the Gram matrix.
- II. SYSTEM MODEL: Soft information is extracted through LLRs using the equivalent channel, NPI variance, and max-log approximation.For user k, the estimate is modeled as ŝ_k = μ_k s_k + ν_k.
- II. SYSTEM MODEL: O(K^3) matrix inversion makes MMSE estimation, channel-gain computation, and NPI-variance computation costly when K is large.
III. LOW-COMPLEXITY SOFT-OUTPUT SIGNAL DETECTION FOR UPLINK LARGE-SCALE MIMO
The proposed detector replaces direct matrix inversion with iterative GS processing, improves initialization through diagonal approximation, and approximates the quantities needed for soft-output LLRs.
- III. LOW-COMPLEXITY SOFT-OUTPUT SIGNAL DETECTION FOR UPLINK LARGE-SCALE MIMO: The method iteratively realizes the MMSE estimate with GS instead of computing an exact matrix inversion.
- III. LOW-COMPLEXITY SOFT-OUTPUT SIGNAL DETECTION FOR UPLINK LARGE-SCALE MIMO: A diagonal-approximate initial solution is introduced to accelerate GS convergence and reduce complexity.
- III. LOW-COMPLEXITY SOFT-OUTPUT SIGNAL DETECTION FOR UPLINK LARGE-SCALE MIMO: The LLR procedure approximates channel gain and NPI variance without computing the exact matrix inversion.
A. Signal detection algorithm based on Gauss-Seidel method
Because the MMSE filtering matrix is Hermitian positive definite, the detector applies GS iteration to solve the MMSE linear system without inversion. The iteration converges for any initial solution and uses a lower-triangular solve.
- A. Signal detection algorithm based on Gauss-Seidel method: The channel properties guarantee that the MMSE filtering matrix W is Hermitian positive definite.
- A. Signal detection algorithm based on Gauss-Seidel method: GS solves the MMSE linear equation iteratively rather than directly computing A^-1b.
- A. Signal detection algorithm based on Gauss-Seidel method: W is decomposed into diagonal, strictly lower-triangular, and strictly upper-triangular components.These components are denoted D, L, and L^H, respectively.
- A. Signal detection algorithm based on Gauss-Seidel method: Each iteration updates the signal estimate as s^(i) = (D + L)^-1(ȳ − L^H s^(i−1)).Because D + L is lower triangular, the update can be computed with low complexity.
- A. Signal detection algorithm based on Gauss-Seidel method: The GS-based algorithm converges for any initial solution because W is Hermitian positive definite.
B. Diagonal-approximate initial solution
The proposed diagonal-approximate initialization uses the diagonal of the MMSE filtering matrix inverse because large-scale uplink channels make that matrix diagonally dominant, yielding a closer starting point at low cost.
- The traditional GS initialization is a zero vector that is usually far from the final solution, although it does not affect convergence.
- When N ≫ K, the channel matrix is asymptotically orthogonal, making the MMSE filtering matrix W diagonally dominant.
- The proposed initial solution uses D−1 to approximate W−1, so it is expected to be closer to the final MMSE estimate than the zero-vector initialization.
- Computing D−1, or equivalently the diagonal-approximate initial solution, has very low complexity because D is diagonal.
C. Approximated method to compute LLRs
The paper develops exact and approximated GS-based routes for obtaining soft-output LLRs without repeated matrix inversion. The approximated route uses D−1 to reduce complexity while retaining the MMSE estimate and LLR computation pipeline.
- Exact method: The exact method applies GS iteratively to estimate W−1 by setting the right-hand side to a unit vector for each matrix column.
- Exact method: The exact GS-based outputs can be substituted into the MMSE LLR formulation to obtain exact max-log LLRs for soft-input channel decoding.
- Motivation: Because exact LLR computation requires K GS runs, its complexity remains O(K^3), despite obtaining the MMSE estimate with O(K^2) complexity.
- Approximated method: The approximated method replaces W−1 with the diagonal approximation D−1 to calculate the equivalent channel gain and noise-plus-interference variance.
- Approximated method: Using D−1 makes computation of the approximated equivalent-channel quantities low complexity and avoids complicated matrix inversion.
- Relation to prior work: Unlike the method in, which first computes a conjugate-gradient matrix, this method directly uses D−1 to obtain LLRs.
D. Computational complexity analysis
The proposed GS-based LLR computation has O(K^2) complexity, with costs arising from initialization, iterative equation solving, and channel-gain/NPI calculations. Compared with Cholesky-based MMSE and Neumann-based methods, it provides stronger complexity reduction as the user dimension grows.
- The diagonal-approximate initialization costs 2K complex multiplications before GS iterations begin.It computes D^-1 and multiplies it by the matched-filter output vector.
- Solving the GS linear equation requires iK^2 complex multiplications because each of K solution elements costs K multiplications per iteration.
- Approximate LLR computation requires K^2 multiplications for all elements of ˜E and 2K for the diagonal elements of ˜U.The first term uses ˜E = D^-1G; the second uses only diagonal entries of ˜U.
- The GS-based algorithm requires (i + 1)K^2 + 4K complex multiplications, yielding O(K^2) complexity for any iteration count.This total includes diagonal initialization, iterative solving, and approximate LLR computation.
- The proposed method reduces complexity from O(K^3) to O(K^2) for arbitrary iteration counts and becomes more advantageous as the MIMO dimension increases.For i = 2, it also has lower complexity than the Neumann-based algorithm.
- GS updates use current-iteration values for earlier components and previous-iteration values for later components, preventing straightforward parallelization but enabling storage and convergence benefits.Only one K × 1 storage vector is required, and later iterates become closer to the final MMSE estimate.
IV. SIMULATION RESULTS
The simulations evaluate LLR approximations, initialization, detector comparisons, antenna scaling, and channel correlation. The proposed GS-based detector approaches MMSE performance with fewer iterations while outperforming the Neumann-based alternative, though correlation slows convergence.
- LLR computation: For N × K = 128 × 16, the approximated LLR method achieves satisfying BER performance relative to exact LLR computation when iterations reach i ≥ 3.The approximation is evaluated using the diagonal-approximate initial solution.
- Initialization: At i = 3, the diagonal-approximate initial solution nearly matches the zero-vector solution at i = 4, reducing the iterations needed for comparable BER.This indicates faster convergence and lower overall complexity.
- Detector comparison: At i = 3 and BER = 10^-4, the GS-based algorithm requires 14 dB SNR versus 15 dB for the Neumann-based algorithm.Both algorithms approach the MMSE benchmark as iterations increase, but GS performs better at the same iteration count.
- Antenna scaling: With K = 16 and SNR = 13 dB, GS reaches exact MMSE performance at i = 4 regardless of the base-station antenna count N.When N/K = 8, the i = 4 GS result is also close to the optimal ML detector, whereas Neumann retains non-negligible loss.
- Channel correlation: Under spatial correlation, GS still converges to MMSE without obvious performance loss, but convergence requires i = 7 at ξ = 0.5 and i = 10 at ξ = 0.7.The simulations use an exponential correlation model with ξ as the adjacent-antenna correlation factor.
V. CONCLUSIONS
The paper proposes a low-complexity GS-based detector for uplink large-scale MIMO, enhanced by diagonal initialization and approximate LLR computation. Analysis reduces complexity from O(K^3) to O(K^2), while simulations show near-optimal MMSE performance with few iterations and superiority over the conventional method.
- Contributions: The proposed detector uses Gauss-Seidel iterations to realize near-optimal signal detection while exploiting large-scale MIMO characteristics.The method avoids directly solving the large matrix inversion in the MMSE detector.
- Contributions: The diagonal-approximate initial solution is designed to be close to the final solution and accelerate GS convergence.The paper also introduces a low-complexity approximate method for LLR computation in soft-input channel decoding.
- Complexity: O(K^3) to O(K^2) complexity reduction is established for the proposed algorithm.Here, K is the number of users.
- Conclusions: The proposed algorithm outperforms the conventional method and achieves near-optimal classical MMSE performance with a small number of iterations.The GS approach is also presented as applicable to other large matrix-inversion problems in wireless communications, such as downlink precoding.