MSE-optimal 1-bit Precoding for Multiuser MIMO via Branch and Bound

Sven Jacobsson, Weiyu Xu, Giuseppe Durisi, Christoph Studer

TL;DR

This paper introduces a novel branch-and-bound algorithm (BB-1) that exactly solves the sum mean-squared error (MSE)-optimal 1-bit precoding problem for multiuser MIMO systems. By reformulating the NP-hard problem as a tree search and employing several clever pruning strategies, BB-1 achieves optimal performance while significantly reducing computational complexity compared to exhaustive search.

What Problem Does This Paper Address?

Next-generation wireless systems, particularly massive multiuser MIMO (MU-MIMO), promise increased data rates by using a base station with a vast number of antennas to serve multiple users simultaneously. However, this massive antenna count leads to significant challenges in terms of power consumption and interconnect bandwidth, especially at millimeter-wave frequencies. A promising solution is to use low-resolution digital-to-analog converters (DACs) at the base station, which requires quantizing the precoded signals to a finite alphabet. The core problem is finding the optimal precoding strategy under these 1-bit quantization constraints, which is known to be NP-hard. Existing methods often resort to suboptimal approximations to manage complexity.

Methods

The authors tackle the NP-hard sum MSE-optimal 1-bit precoding problem by reformulating it as a tree search problem. They develop a 1-bit branch-and-bound (BB-1) precoding algorithm that systematically explores the space of possible precoded vectors. To make this search tractable, they introduce several key innovations:

  • Problem Reformulation: The original problem is rewritten into a form amenable to tree search, focusing on minimizing a specific objective function related to MSE.
  • Branch-and-Bound Framework: The algorithm explores a tree where each level corresponds to a precoding antenna. At each node, it decides which child node (representing a quantized symbol for an antenna) to explore next and which branches can be pruned.
  • Pruning Strategies (The "Five Tricks"): To significantly reduce the search space without sacrificing optimality, the authors propose five crucial techniques:
  • Depth-First Best-First Tree Traversal with Radius Reduction: This strategy prioritizes exploring promising branches and dynamically updates a "radius" (bound) to prune less likely paths.
  • Radius Initialization: The initial bound is set using a Wiener-filter (WF) solution, which is computationally cheap and provides a good starting point for pruning.
  • Sorted QR Decomposition: Permuting the channel matrix columns based on QR decomposition helps to sort diagonal elements, leading to more effective pruning early in the search.
  • Predicting the Future: A sophisticated method is used to find a non-trivial lower bound on the future cost, improving pruning efficiency.
  • Prepruning the Search Tree: Exploiting symmetry in the 1-bit alphabet ({+1, -1}) allows for pre-pruning half of the search tree, halving the search space from the outset.

Datasets

Not discussed in the paper. The evaluation uses simulated channel matrices (Rayleigh fading) and standard modulation schemes (QPSK).

Key Insights and Ideas

  • Exact Optimality is Achievable: The most significant insight is that the NP-hard sum MSE-optimal 1-bit precoding problem can be solved exactly for practical system sizes (e.g., 12 BS antennas) using a carefully designed branch-and-bound approach.
  • Pruning is Key: The effectiveness of BB-1 hinges entirely on its sophisticated pruning strategies. Without these, the complexity would be prohibitive. The "five tricks" demonstrate a deep understanding of how to optimize tree search for this specific problem.
  • Trade-off Between Complexity and Optimality: While BB-1 provides the optimal solution, its complexity is still higher than many suboptimal algorithms. However, the paper shows that the complexity can be managed to be practical for moderate-sized systems, and it serves as a crucial benchmark.
  • Generalizability: The core branch-and-bound framework is adaptable to different constant-modulus alphabets and constellations beyond QPSK, making it a versatile tool.

Key Results

  • Bit Error Rate (BER) Performance: The BB-1 precoder achieves near-optimal performance, with a gap of only 4 dB to the infinite-resolution case for a target BER of 10⁻³. It outperforms or matches several state-of-the-art suboptimal 1-bit precoders (WF, WF-DP, C1PO, SQUID, SP) in terms of BER.
  • Complexity Reduction: Figure 3 vividly illustrates the impact of the five tricks. With all tricks enabled, the number of visited nodes (a measure of complexity) is drastically reduced compared to an exhaustive search. Even with just the first trick, the reduction is orders of magnitude.
  • Benchmark Value: BB-1 provides a valuable benchmark for evaluating the performance of other, potentially simpler and faster, suboptimal 1-bit precoding algorithms.

Limitations and Future Work

  • Complexity for Large Systems: While BB-1 is exact for small-to-moderate sized systems (e.g., 12 BS antennas), its complexity will still grow exponentially with the number of antennas. The paper acknowledges that for very large systems, suboptimal methods or approximations will be necessary.
  • Computational Cost vs. Suboptimal Methods: The paper notes that while BB-1 is optimal, algorithms like Sphere Precoding (SP) can achieve near-optimal performance with noticeably lower complexity.
  • Future Directions: The authors suggest that other tree-traversal strategies (like K-best) could be used to further reduce complexity at the cost of optimality. For applications where the channel is constant over multiple symbol intervals (e.g., millimeter-wave), precomputing precoded vectors and storing them in a codebook is a practical implementation idea. The framework is also extensible to other modulation schemes and alphabets.

Summary updated

Abstract

In this paper, we solve the sum mean-squared error (MSE)-optimal 1-bit quantized precoding problem exactly for small-to-moderate sized multiuser multiple-input multiple-output (MU-MIMO) systems via branch and bound. To this end, we reformulate the original NP-hard precoding problem as a tree search and deploy a number of strategies that improve the pruning efficiency without sacrificing optimality. We evaluate the error-rate performance and the complexity of the resulting 1-bit branch-and-bound (BB-1) precoder, and compare its efficacy to that of existing, suboptimal algorithms for 1-bit precoding in MU-MIMO systems.
BibTeX
@inproceedings{jacobsson2018mse,
  author = {Sven Jacobsson and Weiyu Xu and Giuseppe Durisi and Christoph Studer},
  title = {{MSE-optimal 1-bit Precoding for Multiuser MIMO via Branch and Bound}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2018},
  doi = {10.1109/icassp.2018.8462212},
}
Figure