Reduction in Solving Some Integer Least Squares Problems
arXiv:1101.0382
Abstract
Solving an integer least squares (ILS) problem usually consists of two stages: reduction and search. This thesis is concerned with the reduction process for the ordinary ILS problem and the ellipsoid-constrained ILS problem. For the ordinary ILS problem, we dispel common misconceptions on the reduction stage in the literature and show what is crucial to the efficiency of the search process. The new understanding allows us to design a new reduction algorithm which is more efficient than the well-known LLL reduction algorithm. Numerical stability is taken into account in designing the new reduction algorithm. For the ellipsoid-constrained ILS problem, we propose a new reduction algorithm which, unlike existing algorithms, uses all the available information. Simulation results indicate that new algorithm can greatly reduce the computational cost of the search process when the measurement noise is large.
109 pages
Cited by in corpus (3)
- Optimized Markov Chain Monte Carlo for Signal Detection in MIMO Systems: an Analysis of Stationary Distribution and Mixing Time
- Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection
- An Algorithm for Integer Least-squares with Equality, Sparsity and Rank Constraints