Metraipolis › archive › dc_efacd6305d72
Polynomial-Time MIMO Detection at the Maximum-Likelihood Threshold — arXiv:2609.19405
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.19405
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T05:00:48.670Z
- SHA-256 of the archived text
5e2705a6c9fc72061bc059bebcb6600a48b5720116382c25e502fd7da11a82d8- Stable URL of this page
https://metraipolis.com/documento/dc_efacd6305d72
How to cite
Polynomial-Time MIMO Detection at the Maximum-Likelihood Threshold — arXiv:2609.19405 — arXiv (en), https://arxiv.org/abs/2609.19405 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_efacd6305d72 (Metraipolis archive dc_efacd6305d72, sha256 5e2705a6c9fc72061bc059bebcb6600a48b5720116382c25e502fd7da11a82d8)
BibTeX
@misc{dcefacd6305d72,
title = {Polynomial-Time MIMO Detection at the Maximum-Likelihood Threshold — arXiv:2609.19405},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.19405},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_efacd6305d72; sha256 5e2705a6c9fc72061bc059bebcb6600a48b5720116382c25e502fd7da11a82d8},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.19405. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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{\rho/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 $\rho\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<\rho\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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-18 in math.IT).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2609.19405 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T04:21:23.486Z dalla pagina https://arxiv.org/catchup/math.IT/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).