An efficient ‘P1’ algorithm for dual mixed-integer least-squares problems with scalar real-valued parameters

Abstract In this contribution we consider mixed-integer least-squares problems, where the integer ambiguities <m:math xmlns:m="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <m:mi>a</m:mi> <m:mo>∈</m:mo> <m:msup> <m:mi mathvariant="double-struck">Z</m:mi> <m:mi>n</m:mi> </m:msup> </m:math> $a\in {\mathbb{Z}}^{n}$ and real-valued parameters <m:math xmlns:m="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <m:mi>b</m:mi> <m:mo>∈</m:mo> <m:msup> <m:mi mathvariant="double-struck">R</m:mi> <m:mi>p</m:mi> </m:msup> </m:math> $b\in {\mathbb{R}}^{p}$ are estimated. Both a primal and a dual formulation can be considered, with the latter concerning the ambiguity resolution process taking place into the parameters’ domain. We study the p = 1 case, where an ad hoc ‘P1’ algorithm is introduced, and some geometrical insights are provided. It is demonstrated how the algorithm’s complexity (i.e. number of candidate integer solutions to be evaluated) grows linearly with the ambiguity dimensionality n , differently from the primal formulation where an exponential growth is observed. By means of numerical simulations, here based on Global Navigation Satellite System (GNSS) models, we show the efficiency of this proposed ‘P1’ algorithm, meanwhile also demonstrating its quasi-optimal statistical performance.