Proceedings of the ... IEEE International Conference on Acoustics, Speech, and Signal Processing · 2008 · 108 citations · 11 references
EngineeringComputer ScienceElectrical EngineeringAlgorithmsInformation TheoryWireless CommunicationsChannel EstimationCommunication ComplexityComputational ComplexityMimo AntennasWireless Channel ModelingAverage-case ComplexityDecoding ComplexityDetectorsLattice ReductionMimo SystemsRayleigh FadingWorst-case BoundsWorst-case Complexity
Lattice reduction by means of the LLL algorithm has been previously suggested as a powerful preprocessing tool that allows to improve the performance of suboptimal detectors and to reduce the complexity of optimal MIMO detectors. The complexity of the LLL algorithm is often cited as polynomial in the dimension of the lattice. In this paper we argue that this statement is not correct when made in the MIMO context. Specifically, we demonstrate that in typical communication scenarios the worst-case complexity of the LLL algorithm is not even finite. For i.i.d. Rayleigh fading channels, we further prove that the average LLL complexity is polynomial and that the probability for an atypically large number of LLL iterations decays exponentially.
11
Factoring polynomials with rational coefficients
A. K. Lenstra, H. W. Lenstra, László Lovász · Mathematische Annalen · 1982 · 4K citations · Full text
Closest point search in lattices
Erik Agrell, Thomas Eriksson, Alexander Vardy et al. · IEEE Transactions on Information Theory · 2002 · 1.4K citations · Full text