Abstract
The LLL reduction of lattice vectors and its variants have been widely used to solve the weighted integer least squares (ILS) problem, or equivalently, the weighted closest point problem. Instead of reducing lattice vectors, we propose a parallel Cholesky-based reduction method for positive definite quadratic forms. The new reduction method directly works on the positive definite matrix associated with the weighted ILS problem and is shown to satisfy part of the inequalities required by Minkowski’s reduction of positive definite quadratic forms. The complexity of the algorithm can be fixed a priori by limiting the number of iterations. The simulations have clearly shown that the parallel Cholesky-based reduction method is significantly better than the LLL algorithm to reduce the condition number of the positive definite matrix, and as a result, can significantly reduce the searching space for the global optimal, weighted ILS or maximum likelihood estimate.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Afflerbach L, Grothe H (1985) Calculation of Minkowski-reduced lattice bases. Computing 35: 269–276
Agrell E, Eriksson T, Vardy A, Zeger K (2002) Closest point search in lattices. IEEE Trans Inf Theory 48: 2201–2214
Akhavi A (2002) Random lattices, threshold phenomena and efficient reduction algorithms. Theor Comput Sci 287: 359–385
Artés H, Seethaler D, Hlawatsch F (2003) Efficient detection algorithms for MIMO channels: a geometrical approach to approximate ML detection. IEEE Trans Signal Proc 51(11): 2808–2820
Babai L (1986) On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica 6: 1–13
Banihashemi AH, Khandani AK (1998) On the complexity of decoding lattices using the KorkinZolotarev reduced basis. IEEE Trans Inf Theory 44: 162–171
Brunetti S, Daurat A (2003) An algorithm reconstructing convex lattice sets. Theor Comput Sci 304: 35–57
Conway JH, Sloane NJA (1999) Sphere packings, lattices and groups, 3rd edn. Springer, Berlin
Damen MO, Gamal HE, Caire G (2003) On maximum-likelihood detection and the search for the closest lattice point. IEEE Trans Inf Theory 49: 2389–2402
Daudé H, Vallée B (1994) An upper bound on the average number of iterations of the LLL algorithm. Theor Comput Sci 123: 95–115
Dickson TJ (1968) A sufficient condition for an extreme covering of n-space by spheres. J Aust Math Soc 8: 56–62
Dickson TJ (1972) On Voronoi reduction of positive definite quadratic forms. J Numer Theory 4: 330–341
Fincke U, Pohst M (1985) Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math Comput 44: 463–471
Gardner RJ, Gritzmann P, Prangenberg D (1999) On the computational complexity of reconstructing lattice sets from their X-rays. Discret Math 202: 45–71
Grafarend EW (2000) Mixed integer-real valued adjustment (IRA) problems: GPS initial cycle ambiguity resolution by means of the LLL algorithm. GPS Solut 4: 31–44
Grötschel M, Lovász L, Schrijver A (1988) Geometric algorithms and combinatorial optimization. Springer, Berlin
Gruber PM, Lekkerkerker CG (1987) Geometry of numbers. North-Holland, Amsterdam
Helfrich B (1985) Algorithms to construct Minkowski reduced and Hermite reduced lattice bases. Theor Comput Sci 41: 125–139
Hofmann-Wellenhof B, Lichtenegger H, Collins J (1992) GPS—theory and practice. Springer, Berlin
Jaldén J, Seethaler D, Matz G (2008) Worst- and average-case complexity of LLL lattice reduction in MIMO wireless systems. In: Proceedings of IEEE international conference on acoustics, speech, and signal processing (ICASSP), vol 4, pp 2685–2688. Las Vegas, March 30–April 4
Joux A, Stern J (1998) Lattice reduction: a toolbox for the cryptanalyst. J Cryptol 11: 161–185
Kannan R (1987) Algorithmic geometry of numbers. Ann Rev Comput Sci 2: 231–267
Koch KR (1999) Parameter estimation and hypothesis testing in linear models, 2nd edn. Springer, Berlin
LaMacchia BA (1991) Basis reduction algorithms and subset sum problems. Master thesis, MIT
Lenstra AK, Lenstra HW, Lovász L (1982) Factoring polynomials with rational coefficients. Math Ann 261: 515–534
Li D, Sun X (2006) Nonlinear integer programming. Springer, New York
Ling C, Mow WH (2009) A unified view of sorting in lattice reduction: from V-BLAST to LLL and beyond. In: Proceedings of 2009 IEEE information theory workshop, pp 529–533
Luk FT, Tracy DM (2008) An improved LLL algorithm. Linear Algebra Appl 428: 441–452
Mahler K (1938) On Minkowski’s theory of reduction of positive definite quadratic forms. Q J Math 9: 259–262
Nemhauser G, Wolsey L (1988) Integer and combinatorial optimization. Wiley, New York
Nguyen PQ, Stehle D (2004) Low-dimensional lattice basis reduction revisited. In: ANTS 2004, LNCS, vol 3076. Springer, Berlin, pp 338–357
Nguyen PQ, Stehlé D (2009) An LLL algorithm with quadratic complexity. SIAM J Comput 39: 874–903
Pohst M (1981) On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications. ACM SIGGAM Bull 15: 37–44
Regev O (2009) On Lattices, learning with errors, random linear codes, and cryptography. J ACM 56: 34:1–34:40
Ryshkov SS (1976) The theory of Hermite–Minkowski reduction of positive definite quadratic forms. J Math Sci 6: 651–671
Schnorr CP (1987) A hierarchy of polynomial time lattice basis reduction algorithm. Theor Comput Sci 53: 201–224
Schnorr CP (2006) Fast LLL-type lattice reduction. Inf Comput 204: 1–25
Schnorr CP, Euchner M (1994) Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math Prog 66: 181–199
Seysen M (1993) Simultaneous reduction of a lattice basis and its reciprocal basis. Combinatorica 13: 363–376
Shannon CE (1959) Probability of error for optimal codes in a Gaussian channel. Bell Syst Tech J 38: 611–656
Taha H (1975) Integer programming—theory, applications, and computations. Academic Press, New York
Tammela PP (1976) The Hermite–Minkowski domain of reduction of positive definite quadratic forms in six variables. J Math Sci 6: 677–688
Tammela PP (1979) Reduction theory of positive quadratic forms. J Math Sci 11: 197–277
Tammela PP (1985) Venkov’s reduction theory of positive-quadratic forms. J Math Sci 29: 1306–1312
Teunissen PJG (1993) Least-squares estimation of the integer GPS ambiguities. In: LGR-Series No. 6, Delft Geodetic Computing Centre. Delft University of Technology, pp 59–74
Vallée B (1991) Gauss’ algorithm revisited. J Algorithm 12: 556–572
Vetter H, Ponnampalam V, Sandell M, Hoeher PA (2009) Fixed complexity LLL algorithm. IEEE Trans Signal Proc 57: 1634–1637
Waters DW, Barry JR (2005a) A reduced-complexity lattice-aided decision-feedback detector. In: Proceedings of 2005 international conference wireless networks, communications and mobile computing, pp 845–850
Waters DW, Barry JR (2005b) Noise-predictive decision-feedback detection for multiple-input multiple-output channels. IEEE Trans Signal Proc 53: 1852–1859
Wübben D, Böhnke R, Rinas J, Kühn V, Kammeyer KD (2001) Efficient algorithm for decoding layered space-time codes. Electron Lett 37: 1348–1350
Wübben D, Böhnke R, Kühn V, Kammeyer KD (2003) MMSE extension of V-BLAST based on sorted QR decomposition. In: Proceedings of IEEE 58th vehicular technology conference, VTC 2003-Fall, vol 5, pp 508–512
Wübben D, Böhnke R, Kühn V, Kammeyer KD (2004) Near-maximum-likelihood detection of MIMO systems using MMSE-based lattice-reduction. In: Proceedings of IEEE International Conference Communications, Paris, vol 2, pp 798–802
Xu PL (1998) Mixed integer geodetic observation models and integer programming with applications to GPS ambiguity resolution. J Geod Soc Japan 44: 169–187
Xu PL (2001) Random simulation and GPS decorrelation. J Geod 75: 408–423
Xu PL (2006) Voronoi cells, probabilistic bounds and hypothesis testing in mixed integer linear models. IEEE Trans Inf Theory 52: 3122–3138
Xu PL (2010) Mixed integer linear models, Chapter 38. In: Freeden W, Nashed Z, Sonar T (eds) Handbook of geomathematics. Springer, Berlin, pp 1129–1157
Xu PL, Cannon E, Lachapelle G (1995) Mixed integer programming for the resolution of GPS carrier phase ambiguities, presented at IUGG95 Assembly, Boulder, July 2–14. arXiv:1010.1052v1[cs.IT]
Xu PL, Cannon E, Lachapelle G (1999) Stabilizing ill-conditioned linear complementarity problems. J Geod 73: 204–213
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Xu, P. Parallel Cholesky-based reduction for the weighted integer least squares problem. J Geod 86, 35–52 (2012). https://doi.org/10.1007/s00190-011-0490-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00190-011-0490-y