Numerical Methods for Integer Least Squares Problems
Xiao-Wen Chang (Computer Science, McGill University, Canada)
Abstract. Integer least squares (ILS) problems may arise from many applications such as communications, cryptograph, global positioning systems, etc. Unlike real LS problems, ILS problems are NP-hard. Solving an ILS problem usually consists of two phases: reduction and search. The goal of the reduction is to make the search process more efficient. In this talk, first we consider ordinary ILS problems and introduce the typical algorithms. Then we consider box-constrained overdetermined ILS problems, box-constrained underdetermined ILS problems, and ellipsoid-constrained overdetermined ILS problems, which all have applications in communications. New effective and efficient reduction algorithms and search algorithms will be presented. Numerical simulation results will be given to show our algorithms can be much faster than the existing ones.