Closest point search in lattices

By Erik Agrell, Thomas Eriksson, Alexander Vardy, Kenneth Zeger. IEEE Transactions on Information Theory, 2002

1,533 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/96451ca0c14181169789197a4c7955ca989235b0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Electrical and Electronic Engineering

Citations in the corpus

Complex Lattice Reduction Algorithm for Low-Complexity Full-Diversity MIMO Detection (2009, background): “The transmitted vector is drawn from a finite set , representing the complex constellation being used.”
Quantized Precoding for Massive MU-MIMO (2016, methodology): “This prevents the straightforward use of conventional algorithms to approximate CVPs [55], [56].”
Near-maximum-likelihood detection of MIMO systems using MMSE-based lattice reduction (2004, background): “A feasible alternative is the application of sphere detector (SD) [2], which restricts the search space to a sphere.”
A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations (2010, methodology): “To this end, we use a method of [1] to compute the Voronoi cell of a lattice Λ, making 2 calls to a CVPP oracle for the same lattice Λ.”
Lattice Enumeration Using Extreme Pruning (2010, background): “Algorithms for these problems can be used to solve a wide range of problems, such as integer programming [16], factoring polynomials with rational coefficients [17], integer relation finding [15], as well as problems in communication theory (see [1,25] and references therein).”
Soft-output sphere decoding: algorithms and VLSI implementation (2008, positive): “The basic building block underlying the two tree traversal strategies described in the next section is the Schnorr-Euchner (SE) sphere decoder (SESD) with radius reduction [15], [16], briefly summarized as follows: The search in the tree is constrained to nodes which lie within a radius r around ỹ a”
Fifty Years of MIMO Detection: The Road to Large-Scale MIMOs (2015, methodology): “15Recall that the lattice perspective—many detection problems can be interpreted as the problem of finding the closest lattice point [54], [57], [453]—is also the foundation for the tree-search based MIMO detectors described in Section VIII-D.”
Fixing the Complexity of the Sphere Decoder for MIMO Detection (2008, background): “• Application of some form of lattice reduction or ordering on the channel matrix during the preprocessing stage of the SD to reduce the average complexity of the search stage [7], [8].”
Large-Scale MIMO Detection for 3GPP LTE: Algorithms and FPGA Implementations (2014, background): “tion [13]–[15] or soft-output sphere decoding (SD) [16]–[18],”
Deep MIMO detection (2017, background): “It can be implemented via efﬁcient search algorithms, e.g., the sphere decoder [2].”
Locality sensitive hashing: A comparison of hash function types and querying mechanisms (2010, neutral): “Moreover, finding the nearest lattice point of a vector can be performed with an algebraic method (Agrell et al., 2002).”
On maximum-likelihood detection and the search for the closest lattice point (2003, background): “In this paper we consider a class of algorithms, generally known as sphere decoders [2], [3], [4], [5], [6], [8], that compute or approximate (4) with a polynomial expected complexity within a wide range of system parameters.”
Algorithm and implementation of the K-best sphere decoding for MIMO detection (2006, methodology): “The other notations used below are in conformity with those in [10].”
Faster exponential time algorithms for the shortest vector problem (2010, methodology): “Several variants of this algorithm have been proposed (see [1] for a survey,) including the Schnorr-Euchner enumeration method [30], currently used in state of the art”
Low-complexity near-maximum-likelihood detection and precoding for MIMO systems using lattice reduction (2003, methodology): “In [1] a general procedure for efficient lattice decoding, which performs the minimization in (4) with respect to 2K , was presented.”
A semidefinite programming method for integer convex quadratic minimization (2015, methodology): “The enumeration method is based on various algorithms developed in [1,9,13,25].”