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.