On the Optimal Integer-Forcing Precoding: A Geometric Perspective and a Polynomial-Time Algorithm
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914346884399104 |
|---|---|
| author | Qin, Junren Jiang, Fan Yang, Tao Lyu, Shanxiang Liu, Rongke Jin, Shi |
| author_facet | Qin, Junren Jiang, Fan Yang, Tao Lyu, Shanxiang Liu, Rongke Jin, Shi |
| contents | The joint optimization of the integer matrix $\mathbf{A}$ and the power scaling matrix $\mathbf{D}$ is central to achieving the capacity-approaching performance of Integer-Forcing (IF) precoding. This problem, however, is known to be NP-hard, presenting a fundamental computational bottleneck. In this paper, we reveal that the solution space of this problem admits a intrinsic geometric structure: it can be partitioned into a finite number of conical regions, each associated with a distinct full-rank integer matrix $\mathbf{A}$. Leveraging this decomposition, we transform the NP-hard problem into a search over these regions and propose the Multi-Cone Nested Stochastic Pattern Search (MCN-SPS) algorithm. Our main theoretical result is that MCN-SPS finds a near-optimal solution with a computational complexity of $\mathcal{O}\left(K^4\log K\log_2(r_0)\right)$, which is polynomial in the number of users $K$. Numerical simulations corroborate the theoretical analysis and demonstrate the algorithm's efficacy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_20529 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Optimal Integer-Forcing Precoding: A Geometric Perspective and a Polynomial-Time Algorithm Qin, Junren Jiang, Fan Yang, Tao Lyu, Shanxiang Liu, Rongke Jin, Shi Information Theory Signal Processing The joint optimization of the integer matrix $\mathbf{A}$ and the power scaling matrix $\mathbf{D}$ is central to achieving the capacity-approaching performance of Integer-Forcing (IF) precoding. This problem, however, is known to be NP-hard, presenting a fundamental computational bottleneck. In this paper, we reveal that the solution space of this problem admits a intrinsic geometric structure: it can be partitioned into a finite number of conical regions, each associated with a distinct full-rank integer matrix $\mathbf{A}$. Leveraging this decomposition, we transform the NP-hard problem into a search over these regions and propose the Multi-Cone Nested Stochastic Pattern Search (MCN-SPS) algorithm. Our main theoretical result is that MCN-SPS finds a near-optimal solution with a computational complexity of $\mathcal{O}\left(K^4\log K\log_2(r_0)\right)$, which is polynomial in the number of users $K$. Numerical simulations corroborate the theoretical analysis and demonstrate the algorithm's efficacy. |
| title | On the Optimal Integer-Forcing Precoding: A Geometric Perspective and a Polynomial-Time Algorithm |
| topic | Information Theory Signal Processing |
| url | https://arxiv.org/abs/2602.20529 |