Polynomial-Time MIMO Detection at the Maximum-Likelihood Threshold
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=√(ρ/N)Hx⋆+w, x⋆∈{±1}N, and independent standard Gaussian H∈ℝN× N and w, rounded linear MMSE followed by steepest single-bit descent recovers x⋆ with failure probability tending to zero, uniformly over every transmitted word and every ρ≥2log N, using O(N3) 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 2log 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 4log 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<ρ≤2log N−loglog N−sN with sN→∞ and sN=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.
Related
- A Sharp Signal-to-Noise Threshold for Quasi-Maximum Likelihood Breakpoint Estimation
- Consistency of penalized maximum likelihood estimation for multidimensional change-in-velocity detection
- Estimating Effects of Time-Varying Special Education Regimes Using Targeted Maximum Likelihood
- Restricted Maximum Likelihood Estimation in Generalized Linear Mixed Models
- Maximum Likelihood Estimation and Likelihood Ratio Tests for the Power Spherical Distribution
BibTeX
@misc{papailiopoulos2026polynomialtime,
title = {{Polynomial-Time MIMO Detection at the Maximum-Likelihood Threshold}},
author = {Dimitris Papailiopoulos},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19405},
eprint = {2609.19405},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19405},
}
RIS
TY - UNPB
TI - Polynomial-Time MIMO Detection at the Maximum-Likelihood Threshold
AU - Dimitris Papailiopoulos
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.19405
UR - https://arxiv.org/abs/2609.19405
AB - 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=√(ρ/N)Hx^⋆+w, x^⋆∈{±1}^N, and independent standard Gaussian H∈ℝ^N× N and w, rounded linear MMSE followed by steepest single-bit descent recovers x^⋆ with failure probability tending to zero, uniformly over every transmitted word and every ρ≥2log 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 2log 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 4log 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<ρ≤2log N−loglog N−s_N with s_N→∞ 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.
ER -