Integer least square problem is widely used in wireless communications, cryptography and some other fields. In this study, the authors propose a radius bisection algorithm with restart strategy to solve the ILS problem. Compared with the original sphere-decoding method, the algorithm can solve the ILS problem with higher speed and lower complexity. Also, users can specify a stop criterion to control the accuracy and complexity of the algorithm. Finally, some simulated experiments show the efficiency and effectiveness of the proposed algorithm.
Inspec keywords: wireless channels; decoding; least squares approximations; cryptography
Other keywords:
Subjects: Interpolation and function approximation (numerical analysis); Radio links and equipment; Cryptography; Codes
References
-
-
1)
- A. Korkin , G. Zolotarev . Sur les formes quadratiques. Math. Ann. , 366 - 389
-
2)
- J. Conway , N. Sloane . (1993) Sphere packings, lattices and graphs.
-
3)
- D. Gesbert , H. Bolcskei , A.J. Paulraj . Outdoor MIMO wireless channel: models and performance prediction. IEEE Trans. Commun. , 1926 - 1934
-
4)
- M. Grotschel , L. Lovász , A. Schriver . (1993) Geometric algorithms and combinatorial optimization.
-
5)
- X.W. Chang , T. Zhou . MILES: MATLAB package for solving mixed integer least squares problems. GPS Solut. , 289 - 294
-
6)
- U. Fincke , M. Pohst . Improved methods for calculating vectors of short length in a lattice, including a complexity analysis. Math. Comput. , 170 , 463 - 471
-
7)
- P. Wang , T. Le-Ngoc . An efficient multi-user detection scheme for overloaded group-orthogonal MC-CDMA systems. IET Commun. , 346 - 352
-
8)
- M. Pohst . On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications. ACM SIGSAM Bulletin , 37 - 44
-
9)
- B. Hassibi , S. Broyd . Integer parameter estimation in linear models with applications to GPS. IEEE Trans. Signal Process. , 2938 - 2952
-
10)
- Brutel, C., Boutros, J.: `Euclide space lattice decoding for joint deletion in CDMA systems', Proc. IEEE Information Theory and Communications Workshop, 1999, p. 129.
-
11)
- Kannan, R.: `Improved algorithms on integer programming and related lattice problems', Proc. 15th Annual ACM Symp. on Theory of Computing, 1983, p. 193–206.
-
12)
- X.W. Chang , Y. Guo . Huber's M-estimation in relative GPS positioning: computational aspects. J. Geod. , 351 - 362
-
13)
- Zhao, F., Qiao, S.: `Radius selection algorithms for sphere decoding', ‘Proc. C3S2E-09, ACM Int. Conf. Proc. Series’, 2009, p. 169–174.
-
14)
- D. Micciancio . The hardness of the closest vector problem with preprocessing. IEEE Trans. Inf. Theory , 1212 - 1215
-
15)
- B. Hassibi , H. Vikalo . On the sphere-decoding algorithm. I: Expected complexity. IEEE Trans. Signal Process. , 8 , 2806 - 2818
-
16)
- C. Schnorr , M. Euchner . Lattice basis reduction: improved practical algorithms and solving subset sum problems. Math. Comput. , 2 , 181 - 191
-
17)
- Goldreich, O., Goldwasser, S., Halevi, S.: `Public-key cryptosystems from lattice reduction problems', Proc. 17th Annual Information Cryptology Conf. on Advances in Cryptology, August 1998, p. 112–131.
-
18)
- A.K. Lenstra , H.W. Lenstra , L. Lovasz . Factoring polynomials with rational coefficients. Math. Annal. , 515 - 534
-
19)
- B. Hassibi , B.M. Hochwald . High-rate codes that are linear in space and time. IEEE Trans. Inf. Theory , 1804 - 1824
-
20)
- X.W. Chang , X. Yang , T. Zhou . MLAMBDA: A modified LAMBDA method for integer least-squares estimation. J. Geod. , 552 - 565
-
21)
- X.-W. Chang , X. Yang , T. Le-Ngoc , P. Wang . Partial regularization approach for detection problems in underdetermined linear systems. IET Commun. , 1 , 17 - 24
-
1)
Related content