Certify or Search: Exact MIMO Detection with Tree-Reweighted Bounds

The best possible way to recover the symbols sent by many users to a multi-antenna base station is maximum-likelihood (ML) detection: pick the combination of transmitted symbols that best explains the received signal. It is computationally hard in the worst case. So deployed and proposed receivers give it up. They use linear filters, approximate message passing, heuristically pruned belief propagation, or trained neural networks, and none of these can tell you, for a given received vector, whether the answer they return is actually the ML one. This proposal starts from a different observation. Tree-reweighted max-product (TRW) is a message-passing method that splits a loopy graph into a weighted mix of spanning trees. Every iteration it produces an upper bound on the best achievable score. When the trees agree, it proves that the decoded answer is exactly optimal. When they only partly agree, it proves that a subset of the variables is already fixed at its optimal value.

We propose a detector that runs a damped, parallel form of TRW on the MIMO detection problem. It then does one of three things. If TRW certifies the answer, it outputs it. If TRW certifies only part of the answer, it hands the remaining uncertified symbols to a sphere decoder, which is an exact but exponentially costly tree search. If nothing is certified, it falls back to full search. The output is always the exact ML answer. The open question is how much search the certificates remove, and whether the typical cost of exact detection can be brought close to the cost of iterative approximate detectors. That is the practical form of the complexity question for optimal detection: not the worst case, but the per-instance case.

Core Claim

ML detection, $\hat{x} = \arg\min_{x \in \mathcal{X}^K} \|y - Hx\|^2$, can be written as energy minimization on a fully connected pairwise graph. Here $y$ is the received vector, $H$ the channel matrix, and $\mathcal{X}^K$ the set of all possible symbol vectors for $K$ users. Each symbol is a node. The unary terms come from the matched filter $H^H y$. The pairwise couplings are the entries of the Gram matrix $G = H^H H$.

We make three claims. First, if each real-valued QAM coordinate is rewritten as a weighted sum of binary variables (for 16-QAM, $s = 2b_1 + b_2$ with $b_i \in \{\pm 1\}$), the problem becomes a binary pairwise model. That places it squarely inside the regime where On the optimality of tree-reweighted max-product message-passing proves two things: any weak-tree-agreement fixed point reaches the optimum of the linear-programming (LP) relaxation (Theorem 4), and the agreeing variables are provably optimal (Theorem 2). This sidesteps the ternary counterexamples that block native multi-level alphabets.

Second, at moderate-to-high signal-to-noise ratio (SNR) the true transmitted vector acts as a strongly "planted" solution. We hypothesize that under these conditions the LP relaxation is tight, or nearly tight, on most channel uses, including spatially correlated ones where approximate message passing breaks down.

Third, the TRW dual bound can be evaluated at every iteration. That makes it a free monitor for choosing the damping factor adaptively, so a parallel, hardware-friendly schedule can be used without a sequential ordering.

What would be new is the combination: exact ML output, a certificate per channel use, and search effort that shrinks with the certified fraction. None of the detectors in the literature we draw on offers all three.

Relation to Prior Work

The certificate machinery comes from three papers. Exact MAP Estimates by (Hyper)tree Agreement defines TRW and proves optimality under strong tree agreement. It notes that its damped ("relaxed") updates converge empirically but have no proof. Convergent tree-reweighted message passing for energy minimization gets monotone convergence through a sequential schedule, but that schedule sits poorly with the fully parallel data paths of detector hardware. The 2012 optimality paper supplies partial optimality and binary LP equivalence. We reuse all three, apply them to a problem none of them targets, and replace the sequential schedule with bound-monitored damping.

The damping design is constrained by two papers. On Loopy Belief Propagation - Local Stability Analysis for Non-Vanishing Fields shows that damping cures oscillations driven by negative eigenvalues but not instabilities dominated by positive eigenvalues. It also shows that strong local fields stabilize the iteration. Both points matter here, because MIMO couplings have mixed sign and the matched-filter fields grow with SNR. On the convergence of approximate message passing with arbitrary matrices ties the damping needed to the channel's singular-value spread and shows that a fixed heavy damping slows convergence. Bilinear Generalized Approximate Message Passing. supplies the idea of adapting damping by monitoring an energy. We transfer that idea from the heuristic Bethe free energy to the TRW dual bound, which is always a valid bound, so a decrease in it is a reliable signal to damp harder.

The detection papers motivate the gap. MIMO Detection for High-Order QAM Based on a Gaussian Tree Approximation keeps a single Chow-Liu spanning tree and discards every other edge. In our view it is the degenerate case of TRW with all tree weight on one tree, and it has no bound. Belief-Selective Propagation Detection for MIMO Systems prunes symbols and edges heuristically and comes close to sphere decoding, but it cannot certify anything. Optimal Data Detection in Large MIMO reaches individually optimal performance only when the channel is large and i.i.d. A Deep-Unfolding-Optimized Coordinate-Descent Data-Detector ASIC for mmWave Massive MIMO needs offline training for each scenario. Finally, Message Passing for Max-weight Independent Set warns that message-passing failure tracks the LP integrality gap. This is the main risk for our proposal: if correlated channels produce frustrated cycles, the certified fraction may collapse.

Research Program

We will build the detector in three layers.

Layer 1: the graph. We build the binary-lifted pairwise model from $(H, y, \sigma^2)$ and compare it against a native multi-label model on the QAM levels. Binary lifting adds couplings within each symbol and may loosen the relaxation. Native labels lose the binary guarantees. Which effect dominates is an empirical question we will answer directly.

Layer 2: the solver. This is parallel TRW with edge appearance probabilities $\rho_e$. Each $\rho_e$ is the fraction of trees in the mix that contain edge $e$. We will try uniform weights ($\rho_e = 2/n$ on the complete graph over $n$ binary variables) and weights biased toward high mutual-information edges, which interpolates toward the single-tree method. Damping follows $m_{t+1} = (1-\delta_t) m_t + \delta_t F(m_t)$, where $m_t$ are the messages at iteration $t$, $F$ is the TRW update, and $\delta_t$ is cut in half whenever the dual bound worsens and slowly increased otherwise.

Layer 3: the fallback. Variables certified by agreement are fixed. A sphere decoder then searches only over the rest, starting from a radius given by the partially fixed TRW decoding, and the dual bound prunes branches. Together the three layers output exact ML.

Alongside the build, we will analyze when the relaxation is tight. We will fit the certified fraction against SNR, load $K/N$, constellation order, and a correlation measure such as the condition number of $G$. We will also test whether the stability picture of the non-vanishing-fields analysis predicts where damping fails.

Baselines

The naive reference point is a linear minimum-mean-square-error (LMMSE) detector. On QuaDRiGa mmWave channels, the deep-unfolded coordinate-descent detector is reported to beat it by "4 dB to 10 dB" in high-load settings (A Deep-Unfolding-Optimized Coordinate-Descent Data-Detector ASIC for mmWave Massive MIMO). We will reproduce LMMSE on the same channel draws.

The strongest competitor on the question we care about, exact ML at low cost, is a sphere decoder given an LMMSE-derived starting radius. It already returns exact ML, so our detector wins only if it visits fewer search nodes and uses fewer floating-point operations for identical output. We will count nodes and operations for both on identical channel realizations. No reported sphere-decoder complexity figure was found on Lacuna for these configurations, so both will be measured here.

The strongest approximate competitor is belief-selective propagation. On $8\times 4$ 16-QAM Rayleigh channels it reports a 4 dB gain over plain BP at a bit error rate (BER) of $10^{-4}$, performance within 0.2 dB of sphere decoding, and roughly four orders of magnitude less complexity than plain BP (Belief-Selective Propagation Detection for MIMO Systems). It will be run in that configuration with its published candidate and edge settings. Our detector matches ML by construction, so beating it means lower or comparable operation counts at equal-or-better BER.

For large i.i.d. channels, the reference is the large-MIMO message-passing detector, reported near the individually optimal bound within 15 iterations for $128\times 128$ 16-QAM (Optimal Data Detection in Large MIMO). We run it together with its damped-GAMP variant on correlated channels, where it is expected to fail.

Four ablations isolate the key ingredients. The first is the single-tree method, which removes tree reweighting. The second is TRW with fixed damping, which removes the bound monitor. The third is sequential TRW-S, which trades parallelism for guaranteed monotonicity. The fourth is an exact solver for the binary LP optimum; for binary quadratic problems this can be done with roof duality by max-flow. It separates what the relaxation can certify from what our iterative solver actually reaches. All methods share the same channel draws, a matched iteration or operation budget, and the same tuning grid for their free parameters.

Why not just…?

Why not just run a sphere decoder with a good initial radius? At high SNR on small systems it may already be cheap, and that is a real threat. Our method helps only where search is expensive: moderate SNR, high load, 64-QAM, and correlated channels. The node-count comparison on identical draws settles the question directly. If the certified fraction is low exactly where search is expensive, the proposal fails, and we will report that.

Why not just use damped loopy BP or belief-selective propagation, and fall back to search when messages fail to converge? Convergence of plain BP does not imply correctness. Plain BP on loopy graphs can settle on wrong fixed points, as the integrality-gap analysis in Message Passing for Max-weight Independent Set explains, so such a trigger cannot guarantee ML. We will measure how often converged BP disagrees with ML. Those silent errors are exactly what a certificate prevents.

Why not just solve the binary LP with a max-flow roof-dual solver instead of TRW? For the binary lift this computes the same relaxation, and it is a genuine alternative. We include it as an ablation. TRW's case rests on three things: its parallel iteration suits hardware, it can be stopped at any time with a valid bound, and it extends to the native multi-label model where max-flow does not directly apply. If max-flow is uniformly cheaper at equal certification, we will adopt it as the certifier and keep the certify-then-search contribution.

Why not just use semidefinite relaxation for bounds? It gives tighter bounds but costs $O(N^6)$ as reported in Meysam Sadeghi et al.. That rules it out as a per-channel-use certificate. We will use it offline on small instances only, to measure how much tightness the LP gives up.

Proposed Experiments

We will evaluate on three families of channels. The first is i.i.d. Rayleigh at $8\times 4$ and $16\times 8$ with 16- and 64-QAM, following Belief-Selective Propagation Detection for MIMO Systems. The second is $12\times 12$ 16-QAM, following MIMO Detection for High-Order QAM Based on a Gaussian Tree Approximation. The third is QuaDRiGa mmMAGIC urban-microcell channels with 128 antennas and 16 users at up to 256-QAM, following A Deep-Unfolding-Optimized Coordinate-Descent Data-Detector ASIC for mmWave Massive MIMO. There, exact search is feasible only for the uncertified residual variables.

The metrics are the fraction of channel uses fully certified, the fraction of variables certified, sphere-decoder nodes visited, total operations and iterations, the gap between the dual bound and the achieved cost, and BER. BER must equal that of the sphere decoder whenever the detector outputs a certified or completed solution.

There are three decisive checks. First, on QuaDRiGa channels at operating SNRs, does TRW certify a majority of variables while approximate message passing diverges? Second, does certify-then-search cut sphere-decoder node counts by a large factor at 64-QAM and high load, relative to the LMMSE-radius sphere decoder? Third, does bound-monitored damping reach weak tree agreement as often as sequential TRW-S within the same iteration budget, while retaining parallel updates? Failure on the first check would mean the LP relaxation is too loose for correlated MIMO. That would still be a useful negative result, because it would locate where optimal detection is hard per instance and not only in the worst case.