Optimality of Large MIMO Detection via Approximate Message Passing

I Introduction

We consider the problem of recovering the ${M_{\text{T}}}$-dimensional data vector $\mathbf{s}_{0}\in\mathcal{O}^{M_{\text{T}}}$ from the noisy multiple-input multiple-output (MIMO) input-output relation $\mathbf{y}=\mathbf{H}\mathbf{s}_{0}+\mathbf{n}$, by performing individually-optimal (IO) data detection

Although IO detection achieves the minimum symbol error-rate , the combinatorial nature of the (IO) problem requires prohibitive computational complexity, especially in large (or massive) MIMO systems . In order to enable data detection in such high-dimensional systems, a large number of low-complexity but sub-optimal algorithms have been proposed in the literature (see, e.g., ).

In this paper, we propose and analyze a novel, computationally efficient data-detection algorithm, referred to as IO-LAMA (short for IO large MIMO approximate message passing). We show that IO-LAMA decouples the noisy MIMO system into a set of independent additive white Gaussian noise (AWGN) channels with equal signal-to-noise ratio (SNR); see \freffig:introfigure2 for an illustration of this decoupling property. The state-evolution (SE) recursion of AMP enables us to track the effective noise variance $\sigma_{t}^{2}$ of each decoupled AWGN channel at every algorithm iteration $t$. Using these results, we provide precise conditions on the MIMO system matrix, the system ratio $\beta$, the noise variance $N_{0}$, and the modulation scheme for which IO-LAMA exactly solves the (IO) problem.

I-B Relevant Prior Art

Initial results for IO data detection in large MIMO systems reach back to where Verdú and Shamai analyzed the achievable rates under optimal data detection in randomly-spread CDMA systems. Tanaka derived expressions for the error-rate performance and the multi-user efficiency for IO detection using the replica method. While Tanaka’s results were limited to BPSK constellations, Guo and Verdú extended his results to arbitrary discrete input distributions . All these results study the fundamental performance of IO data detection in the large-system limit, i.e., for $\beta={M_{\text{T}}}/{M_{\text{R}}}$ with ${M_{\text{T}}}\to\infty$. Corresponding practical detection algorithms have been proposed for BPSK constellations —to the best of our knowledge, no computationally efficient algorithms for general constellation sets and complex-valued systems have been proposed in the open literature.

Our data-detection method, IO-LAMA, builds upon approximate message passing (AMP) , which was initially developed for the recovery of sparse signals. AMP has been generalized to arbitrary signal priors in and enables a precise performance analysis via the SE recursion . Recently, AMP-related algorithms have been proposed for data detection ; these algorithms, however, lack of a theoretical performance analysis.

I-C Notation

II IO-LAMA: Large-MIMO Detection using AMP

We now present IO-LAMA and the SE recursion, which is used in \frefsec:SE_MI_ER for our optimality analysis.

Here, $p_{a}$ designates the (known) prior probability of each constellation point $a\in\mathcal{O}$ and $\delta(\cdot)$ is the Dirac delta function; for uniform priors, we have $p_{a}=|\mathcal{O}|^{-1}$.

The IO-LAMA algorithm summarized below is obtained by using the prior distribution in \frefeq:prior within complex Bayesian AMP. A detailed derivation of the algorithm is given in .

In order to analyze the performance of IO-LAMA in the large-system limit, we next summarize the SE recursion. The SE recursion in the following theorem enables us to track the effective noise variance $\sigma_{t}^{2}$ for the decoupled MIMO system for every iteration $t$ (cf. \freffig:introfigure2), which is key for the optimality analysis in \frefsec:SE_MI_ER. A detailed derivation is given in .

The so-called mean-squared error (MSE) function is defined by

where $\mathsf{F}$ is given in \frefeq:Ffunc and $Z\sim\mathcal{C}\mathcal{N}(0,1)$.

II-B IO-LAMA Decouples Large MIMO Systems

III Optimality of IO-LAMA

We now provide conditions for which IO-LAMA exactly solves the (IO) problem.

For $t\to\infty$, the SE recursion in \frefthm:CSE converges to the following fixed-point equation :

which coincides with the “fixed-point equation” developed for IO detection by Guo and Verdú using the replica method in [3, Eq. (34)]. We note that (4) may have multiple fixed-point solutions. In the case of such non-unique fixed points, Guo and Verdú choose the solution that minimizes the “free energy” [3, Sec. 2-D], whereas IO-LAMA converges, in general, to the fixed-point solution with the largest effective noise variance $\sigma^{2}$. We note that if the fixed-point solution to \frefeq:fixed_pt is unique, then IO-LAMA recovers the solution with minimal effective noise variance $\sigma^{2}$ and thus, performs IO detection. However, if there are multiple fixed-points solutions to \frefeq:fixed_pt, IO-LAMA is, in general, sub-optimal and does not necessarily converge to the fixed-point solution with the minimal “free energy.”Convergence to another fixed-point solution is possible if IO-LAMA is initialized sufficiently close to such a fixed point; see for the details. We next provide conditions for which there is exactly one (unique) fixed point with minimum effective noise variance $\sigma^{2}$ and—as a consequence—IO-LAMA solves the (IO) problem.

III-B Exact Recovery Thresholds (ERTs)

We start by analyzing IO-LAMA in the noiseless setting. We provide conditions on the system ratio $\beta$ and the constellation set $\mathcal{O}$, which guarantee exact recovery of an unknown transmit signal $\mathbf{s}_{0}\in\mathcal{O}^{M_{\text{T}}}$ in the large-system limit, i.e., $\beta$ is fixed and ${M_{\text{T}}}\to\infty$. In particular, we show that if $\beta<\beta^{\textnormal{max}}_{\mathcal{O}}$, where $\beta^{\textnormal{max}}_{\mathcal{O}}$ is the so-called exact recovery threshold (ERT), then IO-LAMA perfectly recovers $\mathbf{s}_{0}$; for $\beta\geq\beta^{\textnormal{max}}_{\mathcal{O}}$, perfect recovery is not guaranteed, in general.We assume the initialization in Algorithm 1. IO-LAMA may recover the original signal for $\beta\geq\beta^{\textnormal{max}}_{\mathcal{O}}$ if initialized appropriately; see, e.g., . To make this behavior explicit, we need the following technical result; the proof is given in \frefapp:DAMPsolvability.

For all $\sigma^{2}>0$, \freflem:DAMPsolvability guarantees that $\Psi(\sigma^{2})<\sigma^{2}$. Suppose that for some $\beta>1$, $\beta\Psi(\sigma^{2})<\sigma^{2}$ also holds for all $\sigma^{2}>0$. Then, as long as $\beta>1$ is not too large to also ensure $\beta\Psi(\sigma^{2})<\sigma^{2}$ for all $\sigma^{2}>0$, there will only be a single fixed point at $\sigma^{2}=0$. Therefore, LAMA can still perfectly recover the original signal $\mathbf{s}_{0}$ by \frefthm:CSE since $\Psi(\sigma^{2})=0$. Leveraging the gap between $\Psi(\sigma^{2})$ and $\sigma^{2}$ will allow us to find the exact recovery threshold (ERT) of LAMA for values of $\beta>1$. For the fixed (discrete) constellation set $\mathcal{O}$, the largest $\beta$ that ensures $\beta\Psi(\sigma^{2})<\sigma^{2}$ is precisely the ERT defined next.

Fix $\mathcal{O}$ and let $N_{0}=0$. Then, the exact recovery threshold (ERT) that enables perfect recovery of the original signal $\mathbf{s}_{0}$ using IO-LAMA is given by

With \frefdef:maxbeta, we state \frefthm:recovery, which establishes optimality in the noiseless case; the proof is given in \frefapp:recovery.

Let $N_{0}=0$ and fix a discrete set $\mathcal{O}$. If $\beta<\beta^{\textnormal{max}}_{\mathcal{O}}$, then IO-LAMA perfectly recovers the original signal $\mathbf{s}_{0}$ from $\mathbf{y}=\mathbf{H}\mathbf{s}_{0}+\mathbf{n}$ in the large system limit.

III-C Optimality Conditions for IO-LAMA

We now study the optimality of IO-LAMA in the presence of noise, where exact recovery is no longer guaranteed. In particular, we provide conditions for which IO-LAMA converges to the fixed point with minimal effective noise variance $\sigma^{2}$, which corresponds to solving the (IO) problem. Note that such a minimum free-energy solution is also the fixed point for the IO detector in [3, Eq. (34)]. We call the fixed point with minimum effective noise variance optimal fixed point; other fixed points are called suboptimal fixed points.

We identify three different operation regimes for IO-LAMA depending on the system ratio $\beta$ (see \freftbl:IOLAMAoptimal_reg). To make these three regimes explicit, we need the following definition.

Fix the constellation set $\mathcal{O}$. Then, the minimum recovery threshold (MRT) $\beta^{\textnormal{min}}_{\mathcal{O}}$ is defined by

The definition of MRT shows that for all system ratios $\beta\leq\beta^{\textnormal{min}}_{\mathcal{O}}$, the fixed point of \frefeq:fixed_pt is unique. The following lemma establishes a fundamental relationship between MRT and ERT; the proof is given in \frefapp:MRTandERT.

We next define the minimum critical and maximum guaranteed noise variance, $N_{0}^{\textnormal{min}}(\beta)$ and $N_{0}^{\textnormal{max}}(\beta)$, that determine boundaries for the optimality regimes when $\beta>\beta^{\textnormal{min}}_{\mathcal{O}}$.

Fix $\beta\in(\beta^{\textnormal{min}}_{\mathcal{O}},\beta^{\textnormal{max}}_{\mathcal{O}})$. Then, the minimum critical noise $N_{0}^{\textnormal{min}}(\beta)$ that ensures convergence to the optimal fixed point is defined by

Fix $\beta>\beta^{\textnormal{min}}_{\mathcal{O}}$. Then, the maximum guaranteed noise $N_{0}^{\textnormal{max}}(\beta)$ that ensures convergence to the optimal fixed point is defined by

We recall that all the zero crossings of the function

correspond to all fixed points of the SE recursion of IO-LAMA; we use this function to study the algorithm’s optimality.

Figure 2 illustrates our optimality analysis for a large-MIMO system with QPSK constellations. We show \frefeq:plotfixedfunction depending on the effective noise variance $\sigma^{2}$ and for different system ratios $\beta$. The regimes $\beta\leq\beta^{\textnormal{min}}_{\mathcal{O}}$, $\beta\in(\beta^{\textnormal{min}}_{\mathcal{O}},\beta^{\textnormal{max}}_{\mathcal{O}})$, and $\beta\geq\beta^{\textnormal{max}}_{\mathcal{O}}$ are shown in \freffig:SE_QPSK1, \freffig:SE_QPSK2, and \freffig:SE_QPSK3, respectively. The special case for $\beta=1$ with $N_{0}=0$ corresponds to the solid blue line, along with the corresponding (unique) fixed point at the origin. In the following three paragraphs, we discuss the three operation regimes of IO-LAMA in detail.

In this region, the SE recursion of IO-LAMA always converges to the unique, optimal fixed point. For $\beta<\beta^{\textnormal{min}}_{\mathcal{O}}$, the slope of \frefeq:plotfixedfunction for all $\sigma^{2}$ is strictly-negative. Hence, as \frefeq:plotfixedfunction is always decreasing, there exists exactly one unique fixed point of the SE recursion regardless of the noise variance $N_{0}$. Thus, IO-LAMA converges to the optimal fixed point and consequently, solves the (IO) problem.

We emphasize that we still obtain exactly one fixed point even when $\beta$ is equal to the MRT. Since $\beta=\beta^{\textnormal{min}}_{\mathcal{O}}$, there exists at least one $\sigma_{\star}^{2}$ that satisfies \beta^{\textnormal{min}}_{\mathcal{O}}\frac{\textnormal{d}}{\textnormal{d}\sigma^{2}}\Psi(\sigma^{2})\big{|}_{\sigma^{2}=\sigma_{\star}^{2}}=1. By definition of $\beta^{\textnormal{min}}_{\mathcal{O}}$, \frefeq:plotfixedfunction at $\sigma_{\star}^{2}$ implies that $\sigma_{\star}^{2}$ is a saddle-point, so \frefeq:plotfixedfunction has exactly one zero at $\sigma_{\star}^{2}$. We observe that if $\sigma_{\star}^{2}$ is unique, then $N_{0}^{\textnormal{min}}(\beta^{\textnormal{min}}_{\mathcal{O}})=N_{0}^{\textnormal{max}}(\beta^{\textnormal{min}}_{\mathcal{O}})$. For all other $\sigma^{2}\neq\sigma_{\star}^{2}$, the construction of $\sigma_{\star}^{2}$ implies that $\beta^{\textnormal{min}}_{\mathcal{O}}\frac{\textnormal{d}}{\textnormal{d}\sigma^{2}}\Psi(\sigma^{2})<1$, so the fixed point of \frefeq:plotfixedfunction remains to be unique.

The green, dash-dotted and red, dotted line in \freffig:SE_QPSK1 shows \frefeq:plotfixedfunction for $\beta=\beta^{\textnormal{min}}_{\mathcal{O}}$ with $N_{0}=0$ and $N_{0}=N_{0}^{\textnormal{min}}(\beta^{\textnormal{min}}_{\mathcal{O}})=N_{0}^{\textnormal{max}}(\beta^{\textnormal{min}}_{\mathcal{O}})$, respectively. In both cases, we see that the SE recursion of IO-LAMA converges to the unique fixed point.

In this region, the SE recursion of IO-LAMA converges to the unique, optimal fixed point if $N_{0}<N_{0}^{\textnormal{min}}(\beta)$ or $N_{0}>N_{0}^{\textnormal{max}}(\beta)$.

The green, dash-dotted line, cyan, dashed line, and magenta, dotted line in \freffig:SE_QPSK2 shows \frefeq:plotfixedfunction for $\beta^{\star}=(\beta^{\textnormal{min}}_{\mathcal{O}}+\beta^{\textnormal{max}}_{\mathcal{O}})/{2}$ with $N_{0}=0$, $N_{0}>N_{0}^{\textnormal{max}}(\beta^{\star})$ and $N_{0}<N_{0}^{\textnormal{min}}(\beta^{\star})$, respectively. We note that for the three cases, the fixed point is unique, labeled in \freffig:SE_QPSK2 by a circle. On the other hand, the red, dotted line in \freffig:SE_QPSK2 shows \frefeq:plotfixedfunction with $\beta^{\star}$ under noise $N_{0}\in[N_{0}^{\textnormal{min}}(\beta^{\star}),N_{0}^{\textnormal{max}}(\beta^{\star})]$. In this case, however, we observe that SE recursion of IO-LAMA converges to the rightmost suboptimal fixed point labeled by the crossed circle $\otimes$. Hence, IO-LAMA does not, in general, solve the (IO) problem when $N_{0}^{\textnormal{min}}(\beta)\leq N_{0}\leq N_{0}^{\textnormal{max}}(\beta)$.

In this region, the SE recursion of IO-LAMA converges to the unique, optimal fixed point when $N_{0}>N_{0}^{\textnormal{max}}(\beta)$. As $\beta\rightarrow\beta^{\textnormal{max}}_{\mathcal{O}}$, the low noise $N_{0}<N_{0}^{\textnormal{min}}(\beta)$ (or high SNR) region of optimality disappears because $N_{0}^{\textnormal{min}}(\beta)\rightarrow 0$ as $\beta\rightarrow\beta^{\textnormal{max}}_{\mathcal{O}}$ from \frefeq:beta_recover.

The green, dash-dotted line and red, dotted line in \freffig:SE_QPSK3 shows \frefeq:plotfixedfunction for $\beta=\beta^{\textnormal{max}}_{\mathcal{O}}$ with $N_{0}=0$ and $0<N_{0}\leq N_{0}^{\textnormal{max}}(\beta)$, respectively. We observe that the SE recursion of IO-LAMA converges to the suboptimal fixed point when $\beta=\beta^{\textnormal{max}}_{\mathcal{O}}$ even with $N_{0}=0$. On the other hand, the cyan, dashed line refers to \frefeq:plotfixedfunction for $\beta=\beta^{\textnormal{max}}_{\mathcal{O}}$ with $N_{0}>N_{0}^{\textnormal{max}}(\beta)$. While the noiseless case resulted the SE recursion of IO-LAMA to converge to the suboptimal fixed point, we observe that for strong noise (or equivalently low SNR), the SE recursion of IO-LAMA actually recovers the IO solution. Therefore, when $\beta\geq\beta^{\textnormal{max}}_{\mathcal{O}}$, IO-LAMA solves the (IO) problem when the noise is greater than the maximum guaranteed noise $N_{0}^{\textnormal{max}}(\beta)$.

III-D ERT, MRT, and Critical Noise Levels

The MRTs for 16-QAM and 64-QAM indicate that small system ratios $\beta<1$ are required to always guarantee that IO-LAMA solves the (IO) problem in the presence of noise. For instance, we require $\beta\leq\beta^{\text{min}}_{\text{64-QAM}}\approx 0.8424$, i.e. ${M_{\text{T}}}\leq 0.8424{M_{\text{R}}}$, to ensure that IO-LAMA solves the IO problem for 64-QAM in the large system limit. As $\beta\rightarrow\beta^{\text{max}}_{\text{64-QAM}}\approx 1.1573$, IO-LAMA is only optimal for $N_{0}>N_{0}^{\textnormal{max}}(\beta^{\text{max}}_{\text{64-QAM}})\approx 5.868\cdot 10^{-3}$. From \freftbl:exact_recovery, we see that IO-LAMA is a suitable candidate algorithm for the detection of higher-order QAM constellations in massive multi-user MIMO systems as one typically assumes ${M_{\text{R}}}\gg{M_{\text{T}}}$.

IV Conclusions

We have presented the IO-LAMA algorithm along with the state-evolution recursion. Using these results, we have established conditions on the MIMO system matrix, the noise variance $N_{0}$, and the constellation set for which IO-LAMA exactly solves the (IO) problem. While the presented results are exclusively for the large-system limit, our own simulations indicate that IO-LAMA achieves near-optimal performance in realistic, finite-dimensional systems; see for more details.

Appendix A Proof of \freflem:DAMPsolvability

Here, equality holds for all $\sigma^{2}$ if and only if $S$ is complex normal with variance $\sigma_{s}^{2}$ . Note that if $\sigma^{2}=0$, then \frefeq:MSIbeta1 is achieved for any $\sigma_{s}^{2}$. If $\sigma^{2}>0$, then $\Psi(\sigma^{2})<\sigma^{2}$ by \frefeq:MSIbeta1.

Appendix B Proof of \frefthm:recovery

We assume the initialization in Algorithm 1. Since $N_{0}=0$, if LAMA perfectly recovers the original signal $\mathbf{s}_{0}$, then the fixed point in \frefeq:fixed_pt is unique at $\sigma^{2}=0$. This happens if the system ratio is strictly less than the ERT $\beta^{\textnormal{max}}_{\mathcal{O}}$ because otherwise, i.e., $\beta\geq\beta^{\textnormal{max}}_{\mathcal{O}}$, there exists a non-unique fixed point to \frefeq:fixed_pt for some $\sigma^{2}>0$ by \frefdef:maxbeta.

Appendix C Proof of \freflem:MRTandERT

We show that under a fixed constellation set $\mathcal{O}$, $\beta^{\textnormal{min}}_{\mathcal{O}}\leq\beta^{\textnormal{max}}_{\mathcal{O}}$. The proof is straightforward as,

where (a) and (b) follow from the MRT and ERT definitions.

References