.png){kind=icon}
.png){kind=icon}
Return
An Efficient Optimal Algorithm for the Successive Minima Problem
.png){kind=icon}
OA
AI
DOI：10.1109/TCOMM.2018.2877460.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In many applications, including integer-forcing linear multiple-input and multiple-output (MIMO) receiver design, one needs to solve a successive minima problem (SMP) on an n-dimensional lattice to get an optimal integer coefficient matrix A* is an element of Z(nxn). In this paper, we first propose an efficient optimal SMP algorithm with an O(n(2)) memory complexity. The main idea behind the new algorithm is it first initializes with a suitable suboptimal solution, which is then updated via a novel algorithm with only O(n(2)) flops in each updating, until A* is obtained. Different from existing algorithms which find A* column by column through using a sphere decoding search strategy n times, the new algorithm uses a search strategy once only. We then rigorously prove the optimality of the proposed algorithm. Furthermore, we theoretically analyze its complexity. In particular, we not only show that the new algorithm is Omega(n) times faster than the most efficient existing algorithm with polynomial memory complexity, but also assert that it is even more efficient than the most efficient existing algorithm with exponential memory complexity. Finally, numerical simulations are presented to illustrate the optimality and efficiency of our novel SMP algorithm.
Keywords:
Integer-forcing linear receiver
successive minima problem
sphere decoding
LLL reduction
Schnorr-Euchner enumeration
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
8.3
Papers:
1.2W
Citations:
3.6W