Massive multiple-input multiple-output (MIMO) is an enabling technology for next-generation wireless systems because it provides significant improvements in data rates compared to existing small-scale MIMO systems. However, the increased number of antennas results in high computational complexity for data detection, and requires more efficient detection algorithms. In this paper, we propose a new data detector based on a box-constrained complex-valued dichotomous coordinate descent (BCC-DCD) algorithm for large-scale MIMO systems. The proposed detector involves two steps. First, a transmitted data vector is detected using the BCC-DCD algorithm with a large number of iterations and high solution precision. Second, an improved soft output is generated by reapplying the BCC-DCD algorithm, but with a considerably smaller number of iterations and 1-bit solution precision. Numerical results demonstrate that the proposed method outperforms existing advanced detectors while possessing lower complexity. Specifically, the proposed method provides significantly better detection performance than a BCC-DCD algorithm with similar complexity. The performance advantage increases as the signal-to-noise ratio and the system size increase.

In many communications applications, maximum-likelihood decoding reduces to solving an integer least-squares problem, which is NP-hard in the worst case. It has recently been shown that over a wide range of dimensions and SNRs, the branch and bound (BB) algorithm can be used to find the exact solution with an expected complexity that is roughly cubic in the dimension of the problem. However, the computational complexity becomes prohibitive if the SNR is too low and/or the dimension of the problem is too large. The dichotomous coordinate descent (DCD) algorithm provides low complexity, but its detection performance is not as good as that of the BB detector. Two methods are developed to bound the optimal detector cost to reduce the complexity of BB in this paper. These methods are DCD-based detectors for MIMO and multiuser detection in the scenario of a large number of transmitting antennas/users. First, a combined detection technique based on the BB and DCD algorithms is proposed. The technique maintains the advantages of both algorithms and achieves a good trade-off between performance and complexity compared to using only the BB or DCD algorithm. Second, since the first feasible solution obtained from the BB search is the solution of the decorrelating decision feedback (DF) method and because DCD results in better accuracy than the decorrelating DF solution, we propose that the first feasible solution of the BB algorithm be obtained by the box-constrained DCD algorithm rather than the decorrelating DF detector. This method improves the precision of the initial solution and identifies more branches that can be eliminated from the search tree. The results show that the DCD-based BB detector provides optimal detection with reduced worst-case complexity compared to that of the decorrelating DF-based BB detector.