Polynomial-time detection matches optimal threshold for square MIMO systems
Polynomial-Time MIMO Detection at the Maximum-Likelihood Threshold
Information Theory
Summary
Detecting the exact transmitted signals in certain wireless communication systems is often very slow or impossible to do quickly. The authors show that for square multiple-input multiple-output (MIMO) systems with Gaussian noise, it is possible to recover the exact transmitted signal in polynomial time at the same signal strength threshold as the best possible methods. They use a combination of rounding a linear estimate and a smart step-by-step bit flipping to find the original signal efficiently. This means the fastest known method can achieve exact recovery right up to where it becomes statistically possible.
What this means in practice
- •For wireless system designers: Optimize signal decoding algorithms in MIMO communication using polynomial-time methods that meet the theoretical performance limit.
- •For digital communication engineers: Develop efficient signal recovery procedures for high-dimensional noisy channels that guarantee exact recovery at known thresholds.
A theory result. No direct application yet.
Authors
Dimitris Papailiopoulos
Abstract
We prove that exact block recovery in the square Gaussian binary MIMO model can be achieved in polynomial time at the same first-order SNR threshold as exhaustive maximum-likelihood detection. Specifically, for $y=\sqrt{ρ/N}Hx^\star+w, \; x^\star\in\{\pm1\}^N,$ and independent standard Gaussian $H\in\mathbb R^{N\times N}$ and $w$, rounded linear MMSE followed by steepest single-bit descent recovers $x^\star$ with failure probability tending to zero, uniformly over every transmitted word and every $ρ\ge2\log N$, using $O(N^3)$ unit-cost exact-real arithmetic operations. The model is a special case of Gaussian random linear estimation, for which AMP state evolution and replica/MMSE formulas rigorously characterize fixed-parameter normalized performance. Those results predict the same $2\log N$ scale, but do not by themselves yield an all-coordinate guarantee in the dimension-dependent regime considered here. To the best of our knowledge, no prior work gives polynomial-time exact block recovery at the ML boundary for this setting; the closest prior square-system theorem, for the box relaxation, has first-order threshold $4\log N$. The proof places the rounded LMMSE estimate at sublinear Hamming distance from the truth, and then establishes, uniformly over every error set the local search can visit, that some wrong bit offers a quantified cost decrease while an objective barrier confines the search path. Conversely, if $0<ρ\le2\log N-\log\log N-s_N$ with $s_N\to\infty$ and $s_N=o(\log N)$, then a one-bit neighbor beats the transmitted word with probability tending to one, so even ML detection fails. Therefore, the statistical and polynomial-time exact-recovery thresholds coincide to first order in the stated arithmetic model.