Parallel Cholesky-based reduction for the weighted integer least squares problem

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.