GNSS integer ambiguity posterior probability calculation with controllable accuracy

Abstract

Integer ambiguity resolution (IAR) is one of the key techniques in GNSS high precise positioning. However, an overlooked incorrect integer ambiguity solution may cause severe biases in the positioning results. The optimal integer aperture estimator (IAE) has the largest possible success rate given a certain fail rate. An alternative approach that take advantage of ambiguity integer nature to minimize the solution’s mean squared error (MSE) is known as the best integer equivariant (BIE) estimator. Both of which are associated with the posterior probability of the GNSS integer ambiguity. It is therefore of great significance to calculate posterior probability precisely and efficiently. Due to the occurrence of infinite sums, practical calculation approaches approximate the exact value by neglecting sufficiently small terms in the sum. As a result, they can only produce posterior probability calculation result, information about the result’s accuracy cannot be produced. In this contribution, the value of the posterior probability is bounded from below and from above by dividing the infinite sum into two parts: the major finite part and the minor infinite part. They are calculated partly by enumeration and partly by algebraical bounding. The obtained upper and lower bounds are rigorous and in closed form, so that can be conveniently used. Based on both of the bounds, a method of posterior probability calculation with controllable accuracy is proposed. It not only produces posterior probability calculation result, but also calculation error, which is always smaller than the user-defined acceptable error. Numerical experiments have verified that the proposed approach has advantages on both controllable calculation accuracy and adjustable computational workload.

1 Introduction

Global Navigation Satellite Systems (GNSS) positioning via carrier-phase observation can achieve centimeter-sized precision (Samama 2008; Leick et al. 2015). One of the preconditions of GNSS high precise positioning is that the unrecorded integer cycles of the carrier-phase must be correctly estimated (Dermanis and Rummel 2008). This procedure is referred to as GNSS integer ambiguity resolution (IAR). The linearized GNSS models on which IAR is relied can be cast in the frame of the following mixed-integer model (Teunissen 1995; Xu et al. 1995)

$$\begin{array}{cc}\mathrm{E}({\varvec{y}})={\varvec{A}}{\varvec{a}}+{\varvec{B}}{\varvec{b}};& \mathrm{D}({\varvec{y}})={{\varvec{Q}}}_{{\varvec{y}}{\varvec{y}}}\end{array}$$

(1)

where $\mathrm{E}(\cdot )$ and $\mathrm{D}(\cdot )$ are expectation and dispersion operators, respectively, ${\varvec{y}}\in {\mathbb{R}}^{l}$ is a vector of carrier phase and code observables, ${\varvec{a}}\in {\mathbb{Z}}^{n}$ is an unknown integer ambiguity vector, ${\varvec{b}}\in {\mathbb{R}}^{m}$ is a vector of unknown real-valued parameters such as baseline and atmosphere errors, ${\varvec{A}}$ and ${\varvec{B}}$ are design matrices associated with the unknown parameters and the observables, ${{\varvec{Q}}}_{{\varvec{y}}{\varvec{y}}}$ is the variance–covariance (VC) matrix of observations in ${\varvec{y}}$.

The GNSS model can be solved by first discarding the integer nature of ambiguities (Teunissen 1993; Xu et al. 1995). The user performs a standard least square (LS) adjustment, and the real-valued estimates of all the unknown parameters and their VC matrix can be obtained as follows

$$\begin{array}{cc}\left[\begin{array}{c}\widehat{{\varvec{a}}}\\ \widehat{{\varvec{b}}}\end{array}\right],& \left[\begin{array}{cc}{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}& {{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{b}}}}\\ {{\varvec{Q}}}_{\widehat{{\varvec{b}}}\widehat{{\varvec{a}}}}& {{\varvec{Q}}}_{\widehat{{\varvec{b}}}\widehat{{\varvec{b}}}}\end{array}\right]\end{array}$$

(2)

Then, the real-valued $\widehat{{\varvec{a}}}$ is adjusted to an integer-valued vector by a certain estimator $\Psi :\mathbb{R}^{n} \to \mathbb{Z}^{n} |\varvec {\mathop{a}\limits^{ \vee }} = \Psi (\widehat{\varvec{a}})$. It is usually realized by a combination of proper estimation method and efficient decorrelation (reduction) technique. Algorithms can be enumerated such as minimum pivoting method (Xu et al. 1995), multi-frequency spatial overlay resolution (Wu et al. 2015), lattice reduction resolution (Grafarend 2000; Xu 2012; Wu et al. 2017), and the most famous and widely used least squares ambiguity decorrelation adjustment (LAMBDA) (Teunissen 1993, 1995; Chang et al. 2005; Verhagen et al. 2013). Teunissen (1999) introduces a class of ‘admissible’ integer estimators (IE), and summarizes the commonly used estimators: rounding (Taha 1975), bootstrapping (Blewitt 1989; Dong and Bock 1989) and integer least squares (ILS) (Teunissen 1993) into the framework of IE theory.

The integer ambiguity solution is subject to uncertainty caused by the randomness of the data. An overlooked incorrect integer ambiguity solution may cause severe biases in the positioning results (Teunissen 2003a; Xu 2006). So, it is important to validate the quality of the integer ambiguity estimation. Early proposed validation approaches compare the minimum and the second minimum quadratic form of the residuals by different criterions. They are such as R-ratio test (Euler and Schaffrin 1991), F-ratio test (Frei and Beutler 1990), difference test (Tiberius and de Jonge 1995), projector test (Han 1997) and monitoring validation measure (Xu 1998). Motivated by making the probability of accepting the wrong ambiguity solution under control, Teunissen (2003a) introduces a class of integer aperture estimators (IAE). After that, Verhagen and Teunissen (2006) re-expresses the R-ratio test, F-ratio test, difference test and projector test in the framework of IAE. Moreover, Teunissen and Verhagen (2009), Verhagen and Teunissen (2013) suggest that the validation tests would better be used in the fixed-failure-rate way. Different IAEs perform differently, the optimal IAE in sense of maximizing the estimation success rate subjecting to a given failure rate is first introduced by Teunissen (2005a), and later by Wu and Bian (2015) in an alternative framework of Bayesian statistics. In the view of Bayesian statistics, this optimal IAE is the ambiguity posterior probability based on the observed GNSS data (Wu and Bian 2015). Wu and Bian (2015) further proposes to validate the fixed ambiguity solution by directly checking its posterior probability. The posterior probability provides a very intuitive and solid indicator in mathematics, it is therefore also reasonable to apply the validation test based on a fixed posterior probability.

An alternative approach of integer ambiguity solution is that the user never fixes the real-valued ambiguity solution to some integer, but adjusts it according to the criterion of minimizing the solution’s mean square error (MSE). This estimator is referred to as the best integer equivariant (BIE) estimator proposed by Teunissen (2003b). It takes advantage of the integer nature of the ambiguities coming up with a baseline estimator that is always superior to (integer equivariant) IE and LS estimator (Teunissen 2020). The BIE estimator comes out as the sum of all the integer vectors multiplying their posterior probabilities.

It can be seen that posterior probability plays an important role both in the optimal IAE and in the calculation of BIE estimator. It is therefore of great significance to calculate posterior probability precisely and efficiently. However, we cannot obtain the exact value of posterior probability due to the occurrence of infinite sums. Practical calculation approaches approximate the exact value by neglecting sufficiently small terms in the sum. Teunissen (2005b) replaces the sum of all over the integers space with the sum of a finite set according to the distribution property of the quadratic form of the ambiguity residuals. Wu and Bian (2015) presents another method to enumerate the integer vectors based on a lower limit defined by exponential function. The obtaining of enumerated integer vectors of Teunissen (2005b) and Wu and Bian (2015) relies on a search in the ambiguity space. These approaches, although have achieved good approximations, can only serve as upper bounds of posterior probability. Yu et al. (2017) introduces an approach to calculate the upper and lower bounds of posterior probability. These bounds can be useful in practical calculation, but not theoretically rigorous, because the derivations are based on approximated equation transformations that may bring ambiguous influences in accuracy evaluation. In brief, these approaches can only produce a calculation result of posterior probability, but cannot produce accuracy information about the result. As a consequence, the user do not know (i) whether the calculation accuracy is acceptable, (ii) whether the calculation accuracy is too much higher than the required level at the expense of unnecessary computational burden.

In this contribution, a pair of theoretically rigorous upper and lower bounds of the posterior probability are developed, based on which, a method of posterior probability calculation with known and controllable accuracy is proposed. In Sect. 2, the posterior probability of GNSS integer ambiguity is introduced. Then, some existing approaches of posterior probability calculation are introduced in Sect. 3. In Sect. 4, the approach of the derivation and the calculation of the upper and lower bounds are discussed in detail. Based on the pair of upper and lower bounds, a posterior probability calculation approach with controllable accuracy is introduced in Sect. 5. In Sect. 6, numerical experiments are used to verify the proposed approach and compare with the existing approaches. And finally, we conclude the contents of the article and stress the advantages of the proposed method in Sect. 7.

2 Posterior probability of GNSS integer ambiguity

Posterior probability is a concept of Bayesian statistics. In Bayesian statistics, not only the vector of observables is assumed to be random, but the vector of unknown parameters as well. The sampling probability distribution of observation vector ${\varvec{y}}$ in GNSS model (1) is denoted as $\mathrm{p}({\varvec{y}}|{\varvec{a}},{\varvec{b}})$, ${\varvec{a}}$ and ${\varvec{b}}$ are also supposed to be vectors of random quantities and have a joint prior distribution $\mathrm{p}({\varvec{a}},{\varvec{b}})$. So, the posterior probability of ${\varvec{a}}$ and ${\varvec{b}}$ can be expressed as (Koch 1990, p.4)

$$\mathrm{p}({\varvec{a}},{\varvec{b}}|{\varvec{y}})=\frac{\mathrm{p}({\varvec{y}}|{\varvec{a}},{\varvec{b}})\mathrm{p}({\varvec{a}},{\varvec{b}})}{{\sum }_{{\varvec{a}}\in {\mathbb{Z}}^{n}}{\int }_{{\varvec{b}}\in {\mathbb{R}}^{m}}\mathrm{p}({\varvec{y}}|{\varvec{a}},{\varvec{b}})\mathrm{p}({\varvec{a}},{\varvec{b}})\mathrm{d}({\varvec{b}})}$$

(3)

with ${\sum }_{{\varvec{a}}\in {\mathbb{Z}}^{n}}$ the sum of all the integer values within ${\mathbb{Z}}^{n}$, ${\int }_{{\varvec{b}}\in {\mathbb{R}}^{m}}$ the integral of ${\varvec{b}}$ allover ${\mathbb{R}}^{m}$. Bayesians treat ${\varvec{a}}$ and ${\varvec{b}}$ as varieties independent with each other, the joint prior distribution of which equals to the multiplication of their prior distribution (Lacy et al. 2002; Wu and Bian 2015)

$$\mathrm{p}({\varvec{a}},{\varvec{b}})=\mathrm{p}({\varvec{a}})\mathrm{p}({\varvec{b}})$$

(4)

where $\mathrm{p}({\varvec{a}})$ and $\mathrm{p}({\varvec{b}})$ are the prior distributions of ${\varvec{a}}$ and ${\varvec{b}}$, respectively. Although ${\varvec{a}}$ must be an integer vector, we do not know a priority which integer vector ${\varvec{a}}$ is more likely to be. That means ${\varvec{a}}$ can be any value within the integer space with identical chance. Similarly, there is also not any prior information of parameter ${\varvec{b}}$. Therefore, researchers always treat the non-informative parameters ${\varvec{a}}$ and ${\varvec{b}}$ as independent and evenly distributed as (Teunissen 2001; Zhu et al. 2001; Lacy et al. 2002; Verhagen 2005; Wu and Bian 2015)

$$\left\{\begin{array}{c}\begin{array}{cc}\mathrm{p}({\varvec{a}}=\mathbf{N})\propto 1& \mathbf{N}\in {\mathbb{Z}}^{n}\end{array}\\ {\text{p}}({\varvec{b}})\propto 1\end{array}\right.$$

(5)

where $\mathrm{p}(\cdot )$ is the probability density function (pdf) of the variable in the bracket; “$\propto$” means “is proportional to.” On the other hand, the sampling distribution of the GNSS observation model is regarded to be Gaussian as (Koch 1990, p.4)

$$\begin{aligned} \mathrm{p}({\varvec{y}}|{\varvec{a}},{\varvec{b}}) & =(2\uppi {)}^{\frac{-\mathrm{n}}{2}}{\left|{{\varvec{Q}}}_{{\varvec{y}}{\varvec{y}}}\right|}^{\frac{-1}{2}}\mathrm{exp}\{\frac{-1}{2}{\Vert {\varvec{y}}-{\varvec{A}}{\varvec{a}}-{\varvec{B}}{\varvec{b}}\Vert }_{{{\varvec{Q}}}_{{\varvec{y}}{\varvec{y}}}}^{2}\},\\ &\qquad {\varvec{a}}\in {\mathbb{Z}}^{n},{\varvec{b}}\in {\mathbb{R}}^{m}\end{aligned}$$

(6)

where “${\Vert \cdot \Vert }_{{{\varvec{Q}}}_{{\varvec{y}}{\varvec{y}}}}^{2}$” stands for $(\cdot {)}^{T}{{\varvec{Q}}}_{{\varvec{y}}{\varvec{y}}}^{-1}(\cdot )$, “$\left|\cdot \right|$” is the determinant of a matrix. The orthogonal decomposition of the least squares principle for GNSS model is (Teunissen 1993)

$${\Vert {\varvec{y}}-{\varvec{A}}{\varvec{a}}-{\varvec{B}}{\varvec{b}}\Vert }_{{{\varvec{Q}}}_{{\varvec{y}}{\varvec{y}}}}^{2}={\Vert \widehat{{\varvec{e}}}\Vert }_{{{\varvec{Q}}}_{{\varvec{y}}{\varvec{y}}}}^{2}+{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}+{\Vert \widehat{{\varvec{b}}}({\varvec{a}})-{\varvec{b}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{b}}}({\varvec{a}})\widehat{{\varvec{b}}}({\varvec{a}})}}^{2}$$

(7)

where $\widehat{{\varvec{e}}}$ is the LS residual vector, which is independent with ${\varvec{a}}$ and ${\varvec{b}}$. $\widehat{{\varvec{b}}}({\varvec{a}})$ and ${{\varvec{Q}}}_{\widehat{{\varvec{b}}}({\varvec{a}})\widehat{{\varvec{b}}}({\varvec{a}})}$ are

$$\left\{\begin{array}{c}\widehat{{\varvec{b}}}({\varvec{a}})=\widehat{{\varvec{b}}}-{{\varvec{Q}}}_{\widehat{{\varvec{b}}}\widehat{{\varvec{a}}}}{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}^{-1}(\widehat{{\varvec{a}}}-{\varvec{a}})\\ {{\varvec{Q}}}_{\widehat{{\varvec{b}}}({\varvec{a}})\widehat{{\varvec{b}}}({\varvec{a}})}={{\varvec{Q}}}_{\widehat{{\varvec{b}}}}-{{\varvec{Q}}}_{\widehat{{\varvec{b}}}\widehat{{\varvec{a}}}}{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}^{-1}{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{b}}}}\end{array}\right.$$

(8)

If (7) is substituted into (6), the posterior probability of ${\varvec{a}}$ can be obtained as the marginal posterior distribution

$$\mathrm{p}({\varvec{a}}|\widehat{{\varvec{a}}})={\int }_{{\varvec{b}}\in {\mathbb{R}}^{m}}\mathrm{p}({\varvec{a}},{\varvec{b}}|{\varvec{y}})\mathrm{d}({\varvec{b}})=\frac{\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}}{{\sum }_{{\varvec{a}}\in {\mathbb{Z}}^{n}}\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}}$$

(9)

3 Existing approaches of posterior probability calculation

Equation (9) shows that posterior probability of the integer ambiguity is a likelihood ratio of ${\varvec{a}}$ and the sum of all the integer vectors. The sum in the denominator of (9) is infinite, the exact value of which is incomputable. Fortunately, the likelihood of integer vector decays very fast with the increment of the “distance” between the integer vector and the float solution $\widehat{{\varvec{a}}}$, most of the likelihoods concentrate in a small subset of the ambiguity space. Teunissen (2005b) limit the subset by

$${\mathbb{S}}_{T}({\varvec{a}})=\left\{{\varvec{a}}|{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\le {\upchi }_{1-\alpha }^{2}(n)\right\}$$

(10)

where ${\upchi }^{2}(n)$ is a Chi-square distribution with $n$ degrees of freedom, and $\alpha$ means the significance level. Verhagen (2005) chooses $\alpha =1{0}^{-16}$, while Odolinski and Teunissen (2020) suggests $\alpha =1{0}^{-9}$ to avoid heavy computational burden. This approximation is based on the normal distribution assumption of $\widehat{{\varvec{a}}}$. Similar approximations for other elliptically contoured distributions can be found in Teunissen (2020). In this contribution, we focus on the assumption of normal distribution only.

Alternatively, Wu and Bian (2015) simply select the subset empirically as

$${\mathbb{S}}_{W}({\varvec{a}})=\left\{{{\varvec{a}}}_{(p)}|\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{{\varvec{a}}}_{(p)}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}\ge \delta \cdot {\sum }_{q=1}^{p-1}\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{{\varvec{a}}}_{(q)}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}\right\}$$

(11)

where ${{\varvec{a}}}_{(p)}$ is the $p$-th successive minimum ambiguity vector of $\underset{{\varvec{a}}\in {\mathbb{Z}}^{n}}{\text{min}}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}$; $\delta$ is a fading factor. Wu and Bian (2015) suggest that $\delta =1{0}^{-8}$. To obtain all the integer vectors in ${\mathbb{S}}_{T}({\varvec{a}})$ or ${\mathbb{S}}_{W}({\varvec{a}})$, one must carry out a search in the ambiguity space. The methods of Teunissen (2005b) and Wu and Bian (2015) can produce useful approximations, which can serve as the upper bounds of posterior probability. However, they cannot tell how tight these upper bounds are. Posterior probability is a fundamental criterion in the calculation of the optimal IAE, and the BIE estimator. The user thus has the motivation to know how close the approximated value is. In other words, the calculation accuracy is an information that the user is interested in, but cannot be produced by these approaches.

Another approach is developed by Yu et al. (2017), in which the infinite sum in the denominator of (9) is divided into two parts as

$$ \mathop \sum \limits_{{\user2{a} \in {\mathbb{Z}}^{n} }} \exp \left\{ {\frac{{ - 1}}{2}2\Vert{\hat{a}} - \user2{a}\Vert_{{\user2{Q}_{{\user2{\hat{a}\hat{a}}}} }}^{2} } \right\} = K_{S} + K_{{\bar{S}}} $$

(12)

with

$$\left\{\begin{array}{c}{K}_{S}={\sum }_{i=1}^{s}\mathrm{exp} \left\{ {\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{{\varvec{a}}}_{i}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}} \right\} \\ {K}_{\overline{S}}={\sum }_{i=s+1}^{+\infty }\mathrm{exp} \left\{ {\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{{\varvec{a}}}_{i}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}} \right\} \end{array}\right.$$

(13)

where ${{\varvec{a}}}_{i=1\dots s}$ are integer vectors within a user-defined subset. This subset is designed as a cube which is centrosymmetric to the nearest integer of $\widehat{{\varvec{a}}}$, and the length of whose $j$-th dimension is (Yu et al. 2017)

$$ \Phi \left( {\frac{{\mathop {\max }\limits_{{i = 1:s}} a_{i} \left( j \right) + \frac{1}{2} - \left[\kern-0.15em\left[ \varvec{{\widehat{a}}}(j) \right]\kern-0.15em\right]}}{{\sigma _{{\varvec{\widehat{a}}(j)}} }}} \right) - \Phi \left( {\frac{{\left[\kern-0.15em\left[ {\varvec{\widehat{a}}\left( j \right)} \right]\kern-0.15em\right] - \mathop {\min }\limits_{{i = 1:s}} \varvec{a}_{i} \left( j \right) + \frac{1}{2}}}{{\sigma _{{\widehat{a}\left( j \right)}} }}} \right) \ge 1 - \beta $$

(14)

where ${{\varvec{a}}}_{i}\left({j}\right)$ is the $j$-th entry of vector ${{\varvec{a}}}_{i}$, ${\sigma }_{\widehat{{\varvec{a}}}(j)}$ is the standard deviation of $\widehat{{\varvec{a}}}\left(j\right)$, “$\left[\kern-0.15em\left[ \bullet \right]\kern-0.15em\right]$” means rounding to the nearest integer, $\beta$ is a user-defined significance level, and

$$\Phi \left(x\right)={\int }_{-\infty }^{x}\frac{1}{\sqrt{2\pi }}\mathrm{exp}(-\frac{1}{2}{t}^{2})dt$$

(15)

After the integer subset is defined, ${K}_{S}$ can be calculated precisely. And ${K}_{\overline{S}}$ is evaluated by transforming it from based on ${{\varvec{a}}}_{i=s+1\dots +\infty }$ to based on ${{\varvec{a}}}_{i=1\dots s}$. Yu et al. (2017) suggests an approach of evaluating it by regional integration. The result is further used to develop a pair of upper and lower bounds of the posterior probability. However, the integration result in the derivation is approximated rather than strict, which leads to the upper and lower bounds less theoretically rigorous. The error caused by the approximated integration is neglected in general when $\beta$ is smaller than 0.3% (Yu et al. 2017).

4 A pair of bounds of the posterior probability

In this section, we bound the value of the posterior probability from below and from above. Obviously, an upper bound of posterior probability can be obtained from either Teunissen (2005b) or Wu and Bian (2015), by directly dropping the likelihoods outside the enumerating region (10) or (11). Compared with upper bound, a proper lower bound of the posterior probability would be more important in application, because an appreciated lower bound can prevent the user from validating the ambiguity resolution result by using an over optimistic criterion.

In some degree, the basic ideal of bounding the upper and lower bounds is similar to that of Yu et al. (2017), in dividing the infinite sum of likelihoods in (9) into two parts: the major finite part and the minor infinite part. The finite part can be calculated by an enumeration of the elements. The infinite part is bounded algebraically. The division of the upper and lower bounds is based on the following space partitioning.

4.1 Space partitioning

All the integer points in the $n$-dimensional space can be partitioned into the following two parts

$${\mathbb{Z}}^{n}=\{{\varvec{a}}|{\varvec{a}}\in {\mathbb{S}}\left({\varvec{x}}\right)+\overline{\mathbb{S} }({\varvec{x}})\}$$

(16)

where ${\mathbb{S}}({\varvec{x}})$ is a cuboid whose length equals to ${N}_{i}-1$ as

$$\begin{array}{cc}{\mathbb{S}}({\varvec{x}})=\bigcap_{i=1}^{n}\{{\varvec{x}}\in {\mathbb{R}}^{n}|\left|{\varvec{x}}\left(i\right)\right|\le {N}_{i}-1\},& {N}_{i}\in {\mathbb{N}}^{*}\end{array}$$

(17)

and $\overline{\mathbb{S} }({\varvec{x}})$ is the remaining space as

$$\overline{\mathbb{S} }({\varvec{x}})={\bigcup }_{i=1}^{n}\left\{{\varvec{x}}\in {\mathbb{R}}^{n}|\left|{\varvec{x}}\left(i\right)\right|\ge {N}_{i}\right\}$$

(18)

Obviously, the space $\overline{\mathbb{S} }({\varvec{x}})$ satisfies the following inequality

$$\overline{\mathbb{S} }\left({\varvec{x}}\right)<{\sum }_{i=1}^{n}{\overline{\mathbb{S}} }_{i}\left({\varvec{x}}\right)$$

(19)

where

$${\overline{\mathbb{S}} }_{i}({\varvec{x}})=\{{\varvec{x}}\in {\mathbb{R}}^{n}|\left|{\varvec{x}}\left(i\right)\right|\ge {N}_{i}\}$$

(20)

A sketch map of the partitioning of ${\mathbb{S}}({\varvec{x}})$ and ${\overline{\mathbb{S}} }_{i}\left({\varvec{x}}\right)$ in space ${\mathbb{R}}^{2}$ is shown in Fig. 1.

Fig. 1

A sketch map of partitioning of ${\mathbb{S}}({\varvec{x}})$, ${\overline{\mathbb{S}} }_{1}({\varvec{x}})$ and ${\overline{\mathbb{S}} }_{2}({\varvec{x}})$ in space ${\mathbb{R}}^{2}$, where ${N}_{1}$ and ${N}_{2}$ are both chosen equal to 3, the corners (top left, top right, bottom left, bottom right) are overlapped by ${\overline{\mathbb{S}} }_{1}({\varvec{x}})$ and ${\overline{\mathbb{S}} }_{2}({\varvec{x}})$, simultaneously

As a consequence, the likelihoods in the space ${\mathbb{Z}}^{n}$ can be divided into different regions. Based on this partitioning, upper and lower bounds of posterior probability will be discussed.

4.2 4.2 Upper and lower bounds

4.2.1 Upper bound

As interpreted in the previous subsection, the infinite sum in the denominator of (9) can be divided into different parts ${B}_{S}$ and ${B}_{\overline{S}}$, which are the sum of likelihoods within the region ${\mathbb{S}}({\varvec{x}})$ and $\overline{\mathbb{S} }({\varvec{x}})$, respectively, as

$$\left\{\begin{array}{c}{B}_{\mathrm{S}}=\sum_{{\varvec{a}}\in {\mathbb{S}}({\varvec{x}})}\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}\\ {B}_{\overline{S}}=\sum_{{\varvec{a}}\in \overline{\mathbb{S} }({\varvec{x}})}\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}\end{array}\right.$$

(21)

Note that, ${\mathbb{S}}({\varvec{x}})$ defined in (17) is a cuboid with finite integer vectors in it. Thus, ${B}_{\mathrm{S}}$ can be easily obtained by enumerating all the likelihoods within ${\mathbb{S}}({\varvec{x}})$. As a result, an upper bound of the posterior probability can be directly obtained by dropping the likelihoods outside ${\mathbb{S}}({\varvec{x}})$, as

$$\mathrm{p}\left({\varvec{a}}|\widehat{{\varvec{a}}}\right)=\frac{\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}}{{B}_{S}+{B}_{\overline{S}}}<\frac{\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}}{{B}_{S}}$$

(22)

4.2.2 Lower bound

Unlike the upper bound, the lower bound of the posterior probability is not such straightforward to get. According to (19), the sum of likelihoods in $\overline{\mathbb{S} }({\varvec{x}})$ is smaller than the sum in ${\sum }_{i=1}^{n}{\overline{\mathbb{S}} }_{i}\left({\varvec{x}}\right)$. Therefore, a lower bound of the posterior probability can be expressed as

$$\mathrm{p}\left({\varvec{a}}|\widehat{{\varvec{a}}}\right)=\frac{\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}}{{B}_{S}+{B}_{\overline{S}}}>\frac{\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}}{{B}_{S}+{B}_{{\sum }_{i=1}^{n}{\overline{\mathbb{S}} }_{i}\left({\varvec{x}}\right)}}$$

(23)

where ${B}_{{\sum }_{i=1}^{n}{\overline{\mathbb{S}} }_{i}\left({\varvec{x}}\right)}$ is the sum of likelihoods in space ${\sum }_{i=1}^{n}{\overline{\mathbb{S}} }_{i}\left({\varvec{x}}\right)$. Note that, ${\sum }_{i=1}^{n}{\overline{\mathbb{S}} }_{i}\left({\varvec{x}}\right)$ contains infinite integer vectors, which means ${B}_{{\sum }_{i=1}^{n}{\overline{\mathbb{S}} }_{i}\left({\varvec{x}}\right)}$ cannot be calculated like ${B}_{S}$ by enumerating. In this contribution, ${B}_{{\sum }_{i=1}^{n}{\overline{\mathbb{S}} }_{i}\left({\varvec{x}}\right)}$ is algebraically bounded from above, the bounding discussion of which goes as follows.

Without loss of generality, we define that

$$\varvec{ \widehat{a}}: = \varvec{\widehat{a}} - \left[\kern-0.15em\left[ \varvec{{\widehat{a}}} \right]\kern-0.15em\right] $$

(24)

in the following discuss, where “$\left[\kern-0.15em\left[ \bullet \right]\kern-0.15em\right]$” means rounding to the nearest integer. The eigenvalue decomposition of ${{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}^{-1}$ is introduced as (Shores 2007)

$${{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}^{-1}={{\varvec{V}}}^{T}{\boldsymbol{\Lambda }}_{\sigma }{\varvec{V}}$$

(25)

where ${\varvec{V}}$ is a unitary matrix and ${\boldsymbol{\Lambda }}_{\sigma }$ is a diagonal matrix whose elements ${\sigma }_{i}^{2}$ are the eigenvalues of ${{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}^{-1}$, with ${\sigma }_{1}^{2}\ge {\sigma }_{2}^{2}\cdots \ge {\sigma }_{n}^{2}$. Therefore,

$${\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}={\left(\widehat{{\varvec{a}}}-{\varvec{a}}\right)}^{{\varvec{T}}}{{\varvec{V}}}^{{\varvec{T}}}{\boldsymbol{\Lambda }}_{{\varvec{\sigma}}}{\varvec{V}}(\widehat{{\varvec{a}}}-{\varvec{a}})\ge {\sigma }_{n}^{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }^{2}$$

(26)

and the following inequalities can be obtained from (26)

$${B}_{{\sum }_{i=1}^{n}{\overline{\mathbb{S}} }_{i}\left({\varvec{x}}\right)}=\sum_{{\varvec{a}}\in {\sum }_{i=1}^{n}{\overline{\mathbb{S}} }_{i}\left({\varvec{x}}\right)}\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}\le \sum_{{\varvec{a}}\in {\sum }_{i=1}^{n}{\overline{\mathbb{S}} }_{i}\left({\varvec{x}}\right)}\prod_{i=1}^{n}\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}{\left({\widehat{a}}_{i}-{a}_{i}\right)}^{2}\}$$

(27)

where ${\widehat{a}}_{i}$ and ${a}_{i}$ are the $i$-th entry of $\widehat{{\varvec{a}}}$ and ${\varvec{a}}$, respectively. The sum in the region ${\overline{\mathbb{S}} }_{k}\left({\varvec{x}}\right)$ can be unfolded as a continued product of the sum of the ambiguity entries as

$$ \begin{aligned} & \sum_{{\varvec{a}}\in {\overline{\mathbb{S}} }_{k}\left({\varvec{x}}\right)}\prod_{i=1}^{n}\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}{\left({\widehat{a}}_{i}-{a}_{i}\right)}^{2}\}\\ &\quad ={\sum }_{{a}_{1}=-\infty }^{+\infty }\dots {\sum }_{{a}_{k-1}=-\infty }^{+\infty }{\sum }_{{a}_{k+1}=-\infty }^{+\infty }\dots {\sum }_{{a}_{n}=-\infty }^{+\infty }\\ &\quad \sum_{{a}_{k}\notin (-{N}_{k},{N}_{k})}\prod_{i=1}^{n}\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}{\left({\widehat{a}}_{i}-{a}_{i}\right)}^{2}\}\\ &\quad ={\sum }_{i=1,i\ne k}^{n}{\sum }_{{a}_{i}=-\infty }^{+\infty }\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}{\left({\widehat{a}}_{i}-{a}_{i}\right)}^{2}\}\\ &\quad \sum_{{a}_{k}\notin (-{N}_{k},{N}_{k})}\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}{\left({\widehat{a}}_{k}-{a}_{k}\right)}^{2}\} \end{aligned} $$

(28)

Note that, $\left|{\widehat{a}}_{i}\right|\le 1/2$ from (24), thus

$$({\widehat{a}}_{i}-{a}_{i}{)}^{2}={a}_{i}^{2}+{\widehat{a}}_{i}^{2}-2{\widehat{a}}_{i}{a}_{i}>{a}_{i}^{2}-\left|{a}_{i}\right|$$

(29)

Therefore,

$$\sum_{{a}_{k}\notin \left(-{N}_{k},{N}_{k}\right)}\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}{\left({\widehat{a}}_{k}-{a}_{k}\right)}^{2}\}<2{\sum }_{{a}_{k}={N}_{k}}^{+\infty }\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\left({a}_{k}^{2}-{a}_{k}\right)\}<2{\sum }_{k={N}_{k}^{2}-{N}_{k}}^{+\infty }\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}k\}=\frac{2\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\left({N}_{k}^{2}-{N}_{k}\right)\}}{1-\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\}}$$

(30)

where the factor 2 in front of the summation notation is owing to that the sum of ${a}_{k}$ from $-\infty$ to ${-N}_{k}$ equals to the sum from ${N}_{k}$ to $+\infty$. And

$${\sum }_{{a}_{i}=-\infty }^{+\infty }\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}{\left({\widehat{a}}_{i}-{a}_{i}\right)}^{2}\}<\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}{\widehat{a}}_{i}^{2}\}+\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}{\left({\widehat{a}}_{i}-1\right)}^{2}\}+\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}{\left({\widehat{a}}_{i}+1\right)}^{2}\}+2{\sum }_{{a}_{i}=2}^{+\infty }\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\left({a}_{i}^{2}-{a}_{i}\right)\}<{\Delta }_{i}+\frac{2\mathrm{exp}\{-{\sigma }_{n}^{2}\}}{1-\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\}}$$

(31)

with

$${\Delta }_{i}=\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}{\widehat{a}}_{i}^{2}\}+\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}{\left({\widehat{a}}_{i}-1\right)}^{2}\}+\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}{\left({\widehat{a}}_{i}+1\right)}^{2}\}$$

(32)

Inserting (30) and (31) into (28), and repeating this operation to the remain entries of ${\varvec{a}}$ yields

$$\sum_{{\varvec{a}}\in {\overline{\mathbb{S}} }_{1}\left({\varvec{x}}\right)}\prod_{i=1}^{n}\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}{\left({\widehat{a}}_{i}-{a}_{i}\right)}^{2}\}<\frac{2\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\left({N}_{k}^{2}-{N}_{k}\right)\}}{1-\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\}}{\left(\Delta +\frac{2\mathrm{exp}\{-{\sigma }_{n}^{2}\}}{1-\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\}}\right)}^{n-1}$$

(33)

where $\Delta =\underset{i=1:n}{\text{max}}{\Delta }_{i}$ is the maximum value of ${\Delta }_{i}$, $i=1\dots n$. Thus, the likelihoods in ${\sum }_{i=1}^{n}{\overline{\mathbb{S}} }_{i}\left({\varvec{x}}\right)$ can be bounded from above by

$${B}_{{\sum }_{i=1}^{n}{\overline{\mathbb{S}} }_{i}\left({\varvec{x}}\right)}\le \sum_{{\varvec{a}}\in {\sum }_{i=1}^{n}{\overline{\mathbb{S}} }_{i}\left({\varvec{x}}\right)}\prod_{i=1}^{n}\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}{\left({\widehat{a}}_{i}-{a}_{i}\right)}^{2}\}<\frac{2{\sum }_{i=1}^{n}\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\left({N}_{i}^{2}-{N}_{i}\right)\}}{1-\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\}}{\left(\Delta +\frac{2\mathrm{exp}\{-{\sigma }_{n}^{2}\}}{1-\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\}}\right)}^{n-1}$$

(34)

Finally, we can obtain a lower bound of the posterior probability as

$$\mathrm{p}\left({\varvec{a}}|\widehat{{\varvec{a}}}\right)>\frac{\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}}{{B}_{S}+{B}_{{\sum }_{i=1}^{n}{\overline{\mathbb{S}} }_{i}\left({\varvec{x}}\right)}}>\frac{\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}}{{B}_{S}+{B}_{\overline{S} }^{^{\prime}}}$$

(35)

where ${B}_{\overline{S} }^{\mathrm{^{\prime}}}$ is the upper bound of ${B}_{{\sum }_{i=1}^{n}{\overline{\mathbb{S}} }_{i}\left({\varvec{x}}\right)}$ as

$${B}_{\overline{S} }^{^{\prime}}=\frac{2{\sum }_{i=1}^{n}\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\left({N}_{i}^{2}-{N}_{i}\right)\}}{1-\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\}}{\left(\Delta +\frac{2\mathrm{exp}\{-{\sigma }_{n}^{2}\}}{1-\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\}}\right)}^{n-1}$$

(36)

Note that, the size of the cuboid ${\mathbb{S}}({\varvec{x}})$ in (17) is defined by the user, if ${N}_{i}$, $i=1\dots n$, are set equal, namely, $N$, ${\mathbb{S}}({\varvec{x}})$ becomes to a cube, and a simplified lower bound of $\mathrm{p}\left({\varvec{a}}|\widehat{{\varvec{a}}}\right)$ can be calculated by

$${B}_{\overline{S} }^{^{\prime}}=\frac{2n\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\left({N}^{2}-N\right)\}}{1-\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\}}{\left(\Delta +\frac{2\mathrm{exp}\{-{\sigma }_{n}^{2}\}}{1-\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\}}\right)}^{n-1}$$

(37)

The upper bound (22) and lower bound (35) are theoretically rigorous and in closed form, so that they would be easily calculated and conveniently used. Moreover, a posterior probability calculation method with guaranteed accuracy would be developed based on both of the bounds.

5 Posterior probability calculation with controllable accuracy

Existing approaches, such as Teunissen (2005b) and Wu and Bian (2015), calculate posterior probability by directly dropping the likelihoods outside the enumerating region (10) or (11). Therefore, how large the enumerating region should be set is of great significance. However, the chosen of these “significance level” in (10) “fading factor” in (11) are mostly empirical. For example, Verhagen (2005) chooses $\alpha =1{0}^{-16}$, Odolinski and Teunissen (2020) suggests $\alpha =1{0}^{-9}$ to avoid heavy computational burden, Wu and Bian (2015) suggest $\delta =1{0}^{-8}$.

More importantly, there is not any obvious evidence about the relationship between the chosen “significance level” or “fading factor” and the calculation accuracy of the posterior probability. In other words, we do not know whether these parameters are set too optimistic or too conservative. As a result, the following two aspects are unknown: (i) how precise the calculated posterior probability is; (ii) how large the enumerating region is enough for the predefined calculation accuracy, because an unessential large region will lead to unnecessary heavy computational burden for enumerating the integer points in it.

Fortunately, given rigorous upper and lower bounds, a method of posterior probability calculation with known and controllable accuracy could be developed. Theoretically, the upper and lower bounds could be infinitely close to the true value of the posterior probability, according to the expression

$$\frac{\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}}{{B}_{S}+{B}_{\overline{S} }^{^{\prime}}}<\mathrm{p}\left({\varvec{a}}|\widehat{{\varvec{a}}}\right)<\frac{\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}}{{B}_{S}}$$

(38)

as ${B}_{\overline{S} }^{\mathrm{^{\prime}}}$ fading to 0 with the increment of the enumerating region

$$\underset{N\to +\infty }{\text{lim}}{B}_{\overline{S} }^{^{\prime}}=0$$

(39)

Luckily enough, ${B}_{\overline{S} }^{\mathrm{^{\prime}}}$ fades to 0 rather quickly with the expanding of $N$ because of

$${B}_{\overline{S} }^{^{\prime}}\propto O(\mathrm{exp}\{-{N}^{2}\})$$

(40)

where “$O(x)$” means “comparable to $x.$”

However, the major issue hampering (38) in practical calculation is the complexity of enumerating all the integers in ${\mathbb{S}}({\varvec{x}})$ in order to obtain the value of ${B}_{S}$. It is obvious that there are ${\left(2N-1\right)}^{n}$ integer vectors in a $n$-dimensional cube ${\mathbb{S}}({\varvec{x}})$ with side length $2N-1$, enumerating all of them would be a heavy workload if $N$ or $n$ going to large. An alternative method to treat this problem is just enumerating a part of integer vectors within ${\mathbb{S}}({\varvec{x}})$. Without loss of generality, we assume $m$ most likely integer vector candidates within ${\mathbb{S}}({\varvec{x}})$ are found as ${{\varvec{a}}}_{(1)}$, ${{\varvec{a}}}_{(2)}$…${{\varvec{a}}}_{(m)}$, which can be conveniently obtained by LAMBDA or other reduction-and-search software (Verhagen et al. 2013; Xu 2012). They are listed in decreasing order with respect to their likelihoods. We use the following inequality

$${B}_{S}\le {\sum }_{i=1}^{m}\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{{\varvec{a}}}_{\left(i\right)}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}+\left[{\left(2N-1\right)}^{n}-m\right]\mathrm{exp}\{\frac{-1}{2}{\xi }^{2}\}$$

(41)

where the squared distance ${\xi }^{2}$ is chosen as

$${\Vert \widehat{{\varvec{a}}}-{{\varvec{a}}}_{\left(m\right)}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\le {\xi }^{2}\le {\Vert \widehat{{\varvec{a}}}-{{\varvec{a}}}_{\left(m+1\right)}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}$$

(42)

to ensure (41) always being satisfied and ${B}_{S}$ not being enlarged too much, simultaneously. In this approach, only $m$ most likely integer vectors are needed to be enumerated. As a consequence, the upper and lower bounds in (38) are changed to

$$\frac{\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}}{{B}_{{S}_{m}}+{B}_{{S}_{\overline{m}} }+{B}_{\overline{S} }^{^{\prime}}}<\mathrm{p}\left({\varvec{a}}|\widehat{{\varvec{a}}}\right)<\frac{\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}}{{B}_{{S}_{m}}}$$

(43)

with

$$\left\{\begin{array}{c}{B}_{{S}_{m}}={\sum }_{i=1}^{m}\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{{\varvec{a}}}_{\left(i\right)}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}\\ {B}_{{S}_{\overline{m}} }=\left[{\left(2N-1\right)}^{n}-m\right]\mathrm{exp}\{\frac{-1}{2}{\xi }^{2}\}\\ {B}_{\overline{S} }^{^{\prime}}=\frac{2n\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\left({N}^{2}-N\right)\}}{1-\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\}}{\left(\Delta +\frac{2\mathrm{exp}\{-{\sigma }_{n}^{2}\}}{1-\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\}}\right)}^{n-1}\end{array}\right.$$

(44)

Figure 2 is a sketch map of this approach of calculation in two-dimensional case. The enumerated $m$ most likely integer vectors ${{\varvec{a}}}_{(1)}$, ${{\varvec{a}}}_{(2)}$…${{\varvec{a}}}_{(m)}$ belongs to the ellipse ${\mathbb{E}}(x)$ within ${\mathbb{S}}({\varvec{x}})$. Likelihoods of other integer vectors in ${\mathbb{S}}({\varvec{x}})$ but out of ${\mathbb{E}}(x)$ are bounded by ${B}_{{S}_{\overline{m}} }$ rather than enumerated. Likelihoods of integer vectors out of ${\mathbb{S}}({\varvec{x}})$, namely, in ${\overline{\mathbb{S}} }_{1}({\varvec{x}})$ or ${\overline{\mathbb{S}} }_{2}({\varvec{x}})$, are bounded by ${B}_{\overline{S} }^{\mathrm{^{\prime}}}$.

Fig. 2

A sketch map of ${\mathbb{E}}(x)$ ${\mathbb{S}}({\varvec{x}})$, ${\overline{\mathbb{S}} }_{1}({\varvec{x}})$ and ${\overline{\mathbb{S}} }_{2}({\varvec{x}})$ in space ${\mathbb{R}}^{2}$, the corners (top left, top right, bottom left, bottom right) are overlapped by ${\overline{\mathbb{S}} }_{1}({\varvec{x}})$ and ${\overline{\mathbb{S}} }_{2}({\varvec{x}})$, simultaneously

Based on (43), we discuss the posterior probability calculation method with under-controlled accuracy. If an acceptable calculation error, $\upgamma$, is given, the upper and lower bounds must satisfy

$$\frac{\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}}{{B}_{{S}_{m}}}-\frac{\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}}{{B}_{{S}_{m}}+{B}_{{S}_{\overline{m}} }+{B}_{\overline{S} }^{^{\prime}}}<\upgamma $$

(45)

to guarantee calculation accuracy. Note that, ${B}_{{S}_{\overline{m}} }$ and ${B}_{\overline{S} }^{\mathrm{^{\prime}}}$ can be viewed as functions of $N$, it yields from (45) that

$${B}_{{S}_{\overline{m}} }(N)+{B}_{\overline{S} }^{\mathrm{^{\prime}}}(N)<\frac{\upgamma {B}_{{S}_{m}}^{2}}{\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}-\upgamma {B}_{{S}_{m}}}$$

(46)

Although there is not straightforward approach to resolve (46), it is easy to observe that (46) is satisfied when the following equation is satisfied

$${\left(2N-1\right)}^{n}\mathrm{exp}\{\frac{-1}{2}{\xi }^{2}\}+{B}_{\overline{S} }^{\mathrm{^{\prime}}}\left(N\right)=\frac{\upgamma {B}_{{S}_{1}}^{2}}{\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}-\upgamma {B}_{{S}_{1}}}$$

(47)

where ${B}_{{S}_{1}}$ means ${B}_{{S}_{m}}$ with parameter $m=1$. So, ${\xi }^{2}$ can be obtained when $N$ is given, as

$${\xi }^{2}=2n\mathrm{log}\left(2N-1\right)-2\mathrm{log}\left(\frac{\upgamma {B}_{{S}_{1}}^{2}}{\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}-\upgamma {B}_{{S}_{1}}}-{B}_{\overline{S} }^{\mathrm{^{\prime}}}\left(N\right)\right)$$

(48)

The problem now is that $N$ is not actually given. Nevertheless, value in the “log” operator must be positive, thus

$${B}_{\overline{S} }^{\mathrm{^{\prime}}}\left(N\right)<\frac{\upgamma {B}_{{S}_{1}}^{2}}{\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}-\upgamma {B}_{{S}_{1}}}$$

(49)

Inserting (44) into (49) yields

$${N}^{2}-N>\beta =\frac{2\left(n-1\right)}{{\sigma }_{n}^{2}}\mathrm{log}\left(\Delta +\frac{2\mathrm{exp}\{-{\sigma }_{n}^{2}\}}{1-\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\}}\right)-\frac{2}{{\sigma }_{n}^{2}}\mathrm{log}\frac{\upgamma {B}_{{S}_{1}}^{2}\left(1-\mathrm{exp}\{\frac{-1}{2}{\sigma }_{n}^{2}\}\right)}{2n\left(\mathrm{exp}\{\frac{-1}{2}{\Vert \widehat{{\varvec{a}}}-{\varvec{a}}\Vert }_{{{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}}^{2}\}-\upgamma {B}_{{S}_{1}}\right)}$$

(50)

Therefore,

$$ N \ge \left\lceil {\frac{{1 + \sqrt {1 + 4\beta } }}{2}} \right\rceil $$

(51)

where “$\left\lceil \bullet \right\rceil$” means rounding up to the nearest integer. Keeping in mind that ${B}_{\overline{S} }^{\mathrm{^{\prime}}}$ fades rapidly with the increment of $N$, so we can try the smallest value of $N$ as (51), then test whether the corresponding $m$ integer vectors ${{\varvec{a}}}_{(1)}$, ${{\varvec{a}}}_{(2)}$…${{\varvec{a}}}_{(m)}$ are within ${\mathbb{S}}({\varvec{x}})$, and adjust the value of $N$ according to the result. For example, the distance ${\xi }^{2}$ can be directly obtained from (48) with $N$ being given as the smallest value of (51). Then, we search all the integer vectors whose squared distance are smaller than ${\xi }^{2}$. It is easy to observe whether these integer vectors belong to a cube or not. If the searched vectors are all in cube ${\mathbb{S}}({\varvec{x}})$, (46) and (47) are both satisfied; otherwise, we enlarge size $N$ until the vectors are within region ${\mathbb{S}}({\varvec{x}})$.

Another important aspect is the reparameterization of ambiguities. The eigenvalues of ${{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}$ are adjusted by the parameterization of the ambiguities, so does the upper and lower bounds of posterior probability. This observation allows one to use reparameterization techniques to obtain tighter bounds. In this contribution, we suggest to apply LAMBDA decorrelation (Teunissen 1995) or lattice reduction techniques (Grafarend 2000; Xu 2012; Wu et al. 2017; Wu and Bian 2022) before bounding the posterior probability.

Finally, the process of the posterior probability calculation with controllable accuracy can be summarized as follows

Algorithm: Posterior probability calculation with controllable accuracy

Input: Solution $\widehat{{\varvec{a}}}$, VC matrix ${{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}$, integer vector ${\varvec{a}}$ and acceptable error $\upgamma$

Output: Posterior probability $\mathrm{p}\left({\varvec{a}}|\widehat{{\varvec{a}}}\right)$ upper and lower bounds, calculated error

Step 1: Decorrelating (reducing) the ambiguity solution $\widehat{{\varvec{a}}}$ and VC matrix ${{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}$;

Step 2: Calculating $N$ by (51), then calculating ${\xi }^{2}$ by (48);

Step 3: Enumerating all the integer vectors whose squared distance is smaller than ${\xi }^{2}$; If not all the vectors are in cube ${\mathbb{S}}({\varvec{x}})$, $N=N+1$ and back to step 2;

Step 4: Calculating ${B}_{{S}_{m}}$ by (44), and the upper bound of $\mathrm{p}\left({\varvec{a}}|\widehat{{\varvec{a}}}\right)$ by (43);

Step 5: Calculating ${B}_{{S}_{\overline{m}} }$ and ${B}_{\overline{S} }^{\mathrm{^{\prime}}}$ by (43), the lower bound by (44), and calculation accuracy by the upper and lower bounds

6 6. Experimental validation

6.1 6.1 A numerical example

This numerical example is selected from data of single-frequency-single-epoch double differenced GPS positioning based on carrier phase and code observables. After a standard least squares resolution is performed, the float solution $\widehat{{\varvec{a}}}$ and its VC matrix ${{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}$ are obtained as

$$\widehat{{\varvec{a}}}={[-1.6885\,1.6169\,-0.2531 \,-0.7284\, 2.1540\,-0.4375]}^{T}$$

and

$${{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}=\left[\begin{array}{cc}\begin{array}{ccc}0.7837& -0.2526& -0.0412\\ -0.2526& 0.5410& 0.0360\\ -0.0412& 0.0360& 0.3797\end{array}& \begin{array}{ccc}0.3189& -0.6593& 0.0169\\ -0.1086& 0.4116& -0.1367\\ 0.0470& -0.1945& 0.0180\end{array}\\ \begin{array}{ccc}0.3189& -0.1086& 0.0470\\ -0.6593& 0.4116& -0.1945\\ 0.0169& -0.1367& 0.0180\end{array}& \begin{array}{ccc}0.1440& -0.3167& 0.0083\\ -0.3167& 0.8160& -0.0759\\ 0.0083& -0.0759& 0.0497\end{array}\end{array}\right]$$

6.1.1 Calculation process

In the following, the posterior probability of the ILS estimator $\mathop a\limits^{ \vee }$ is calculated. The predefined calculation accuracy is set as $\upgamma =1{0}^{-6}$. In order to illustrate our method clearly, the process of calculation will be shown step by step.

Step 1 Decorrelating the ambiguity solution and VC matrix by reduction techniques. The decorrelation matrix ${\varvec{Z}}$ is

$${\varvec{Z}}=\left[\begin{array}{cc}\begin{array}{ccc}-2& 2& 2\\ 1& 0& -1\\ -1& 1& 1\end{array}& \begin{array}{ccc}0& 1& 1\\ 0& -1& -1\\ 0& 1& 1\end{array}\\ \begin{array}{ccc}6& -5& -5\\ 0& 0& 0\\ 3& 0& -3\end{array}& \begin{array}{ccc}2& -1& -1\\ 1& 1& 1\\ 1& -1& -2\end{array}\end{array}\right]$$

the decorrelated float solution $\widehat{{\varvec{a}}}$ and its VC matrix ${{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}$ are obtained as

$$\widehat{{\varvec{a}}}={[-0.4359\,0.0119\,-0.2925\,0.2597\,-0.2386\,0.1989]}^{T}$$

and

$${{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}}=\left[\begin{array}{cc}\begin{array}{ccc}0.1074& -0.0322& -0.0119\\ -0.0322& 0.1017& -0.0030\\ -0.0119& -0.0030& 0.0604\end{array}& \begin{array}{ccc}-0.0018& 0.0024& -0.0080\\ 0.0103& 0.0155& 0.0052\\ -0.0186& 0.0031& 0.0052\end{array}\\ \begin{array}{ccc}-0.0018& 0.0103& -0.0186\\ 0.0024& 0.0155& 0.0031\\ -0.0080& 0.0052& 0.0052\end{array}& \begin{array}{ccc}0.0563& -0.0081& 0.0015\\ -0.0081& 0.0437& 0.0060\\ 0.0015& 0.0060& 0.0180\end{array}\end{array}\right]$$

The ILS estimator $\mathop a\limits^{ \vee }$ is

$$\stackrel{ \vee}{{\varvec{a}}}{=[0\,0\,0\,0\,0\,0]}^{T}$$

Step 2: From (51), the value of $N$ is obtained as

$$N\ge 3$$

Setting $N=3$, then ${\xi }^{2}$ is obtained from (48) as

$${\xi }^{2}=55.8808$$

Step 3: Enumerating all the integer vectors whose squared distance is smaller than ${\xi }^{2}$, 305 integer nodes are searched and 127 integer vectors are found. All of the vectors are in cube ${\mathbb{S}}({\varvec{x}})=\bigcap_{i=1}^{n}\{{\varvec{x}}\in {\mathbb{R}}^{n}|\left|{\varvec{x}}\left(i\right)\right|\le 2\}$, algorithm goes down.

Step 4: Calculating ${B}_{{S}_{m}}$ by (44) as

$${B}_{{S}_{m}}=0.02396575$$

and then the upper bound of $\mathrm{p}\left(\stackrel{ \vee}{{\varvec{a}}}|\widehat{{\varvec{a}}}\right)$ is obtained by (43) as

$$\mathrm{p}\left(\stackrel{ \vee}{{\varvec{a}}}|\widehat{{\varvec{a}}}\right)<0.79589659$$

step 5: Calculating ${B}_{{S}_{\overline{m}} }$ and ${B}_{\overline{S} }^{\mathrm{^{\prime}}}$ as

${B}_{{S}_{\overline{m}} }=1.19\times 1{0}^{-8}$ and ${B}_{\overline{S} }^{\mathrm{^{\prime}}}=7.61\times 1{0}^{-9}$

and the lower bound is obtained by (44) as

$$\mathrm{p}\left(\stackrel{ \vee}{{\varvec{a}}}|\widehat{{\varvec{a}}}\right)>0.79589594$$

From the upper and lower bounds above, we know that the calculation error is $6.5\times 1{0}^{-7}$. It is smaller than the predefined acceptable error $\upgamma =1{0}^{-6}$.

6.1.2 Calculation performances under different acceptable errors

In the previous content, the posterior probability of the ILS estimator $\stackrel{ \vee}{{\varvec{a}}}$ is calculated, with the acceptable error being fixed as $\upgamma =1{0}^{-6}$. In order to show the accuracy controllable property of the proposed approach, calculation accuracy and complexity under different acceptable errors are investigated in the following content. Integer search is the heaviest workload in the calculation, a canonical complexity measurement of which is the amount of searched integer points during the search process (Chang et al. 2013; Wu and Bian 2022). Therefore, number of searched integer nodes is used as the measurement of calculation complexity in this contribution.

The results of calculation accuracy and complexity under acceptable errors from $\upgamma =1{0}^{-4}$ to $\upgamma =1{0}^{-8}$ are shown in Table 1. It reveals that the calculation accuracy is enhanced with the increment of required accuracy, and all of the calculated errors are smaller than their required counterparts. For example, the calculation errors decrease from $6.9\times 1{0}^{-5}$ to $6.6\times 1{0}^{-9}$ as the acceptable errors going from $1{0}^{-4}$ to $1{0}^{-8}$. At the same, the searched points only increase from 173 to 491, which means this approach can produce calculation results with satisfied accuracy at the expense of a very low computational burden.

Table 1 calculation accuracy and complexity under different acceptable errors

6.1.3 Comparisons with existing approaches

In this part, we calculate the posterior probability of the top five most likely integer vectors using the new method. Then, the results are compared with the corresponding results obtained by Teunissen (2005b) with $\alpha =1{0}^{-16}$ (Verhagen 2005), $\alpha =1{0}^{-9}$ (Odolinski and Teunissen 2020), and Wu and Bian (2015) with $\delta =1{0}^{-8}$. The result of Yu et al. (2017) is not theoretically rigorous, so it is not contained in the comparison.

Using the search algorithm in LAMBDA software, top five most likely integer vector candidates can be easily found (Verhagen et al. 2013). They are listed in Table 2 in descending order with respect to their likelihoods.

Table 2 Top five integer vectors in decreasing order with respect to their likelihoods

Their posterior probabilities, calculated by the new approach and by Verhagen (2005), Odolinski and Teunissen (2020), Wu and Bian (2015), respectively, are shown in Table 3. It reveals that all of the results produced these approaches have achieved high accuracy. However, only the new approach can produce the lower bound of the posterior probability and evaluate the accuracy of the calculation result. In this example, the required accuracy is $\upgamma =1{0}^{-6}$, and all of the calculation accuracy obtained by the new approach is higher than 10^–6. Results of other approaches are actually the lower bound of posterior probability. Therefore, accuracy of these approaches cannot be evaluated by themselves. Although the obtained result may be very accurate, the user still does not know how accurate it is, whether it can meet the required accuracy. On the contrary, the calculation accuracy of the new method can be produced and can always meet the requirements.

Table 3 Posterior probability results of top five integer vectors obtained by different approaches (Methods: ① Teunissen (2005b) with $\alpha =1{0}^{-16}$ (Verhagen 2005); ② Teunissen (2005b) with $\alpha =1{0}^{-9}$ (Odolinski and Teunissen 20202020); ③ Wu and Bian (2015) with $\delta =1{0}^{-8}$)

On the aspect of computational complexity, Verhagen (2005) enumerates the most integer points, followed by Odolinski and Teunissen (2020), and then by Wu and Bian (2015). The new approach searches comparable number of integers with Odolinski and Teunissen (2020) in order 1 and 2, and comparable number of integers with Wu and Bian (2015) in order 3 to 5. In the existing approaches, the amount of enumerated integer points cannot be adjusted by the required accuracy, because the “significance level” $\alpha$ and “fading factor” $\delta$ are fixed to the empirical values. It means that they might enumerate too many integers if the acceptable accuracy is not set that high. On the contrary, the enumerating region of the new method can be adjusted flexibly according to the predefined accuracy. For example, if $\upgamma$ equals to $1{0}^{-6}$, method ①, ②, ③ and the new method search 986, 270, 165 and 305 points, respectively. If $\upgamma$ changes to 10^–4, method ①, ② and ③ still search 986, 270 and 165 points, respectively; while the searched points of new method reduce to 173 (seen Table 1). It shows that Verhagen (2005), Odolinski and Teunissen (2020) search an unessential large region leading to unnecessary heavy computational burden for the required accuracy. Another issue needed to be clarified is that the new method searches different amount of integer points for different integer vectors. For example, the new method searches 305, 248, 203, 165, 163 points for integer vector in order 1, 2, 3, 4, 5, respectively. The reason is that the search region ${\xi }^{2}$ is a function of integer vector ${\varvec{a}}$, which has been shown in (48).

6.2 Experimental verification by real collected data

In this subsection, experimental verification is made using GPS data collected from two Hong Kong continuously operating reference stations (CORS) sites. A 7.8-km-long short baseline is formed by the two stations. Performance of posterior probability calculation method is verified using the integer ambiguities and functions produced in baseline precise positioning.

GNSS single-epoch double-differenced RTK functional model is used in data processing. The standard deviations of code and phase observations are set 0.3 and 0.003 m, respectively, and a simple equal-weighted model is used. We apply single frequency ambiguity resolution by the means that all the ambiguities in each epoch are fixed as new ones. As an essential procedure in posterior probability calculation of Teunissen (2005b), Wu and Bian (2015) and the new method, integer search strategy used herein is determinate-region search in LAMBDA software (Verhagen et al. 2013). Specifications of the processing strategy are summarized in Table 4.

Table 4 Specifications of the processing strategy

During the experiment, changes of the visible satellites and the geometry dilution of precision (GDOP) are presented in Fig. 3. It shows that the visible satellites are between 6 and 12, and the GDOP is below 8. The ambiguity dilution of precision (ADOP) and the dimension of the ambiguities are demonstrated in Fig. 4. The ADOP is defined by the following equation (Teunissen 1997)

Fig. 3

GDOP and the number of common-view satellites

Fig. 4

ADOP values and dimensions of the ambiguity

$$\mathrm{ADOP}={\left(\mathrm{det}({{\varvec{Q}}}_{\widehat{{\varvec{a}}}\widehat{{\varvec{a}}}})\right)}^{\frac{1}{n}}$$

(52)

The dimensions of the ambiguities are between 4 and 10, while most of the ADOP values are smaller than 0.02. Figures 3 and 4 have revealed that the strength of the GNSS positioning model is strong. As a result, 2846 out of 2880 epochs are resolvable, posterior probability calculation is carried on in theses epochs, then comparisons are made. The comparisons are mainly twofold: (i) performance of the new approach under different acceptable accuracies, and (ii) performance of the new approach and the existing ones, such as Verhagen (2005), Odolinski and Teunissen (2020), Wu and Bian (2015).

6.2.1 Performance under different acceptable accuracies

In the experiment, the posterior probability of the ILS estimator $\stackrel{ \vee}{{\varvec{a}}}$ in each epoch is calculated. We first set the predefined calculation accuracy as $\upgamma =1{0}^{-4}$. The calculated upper and lower bounds of the posterior probability in all of the 2846 epochs are shown in Fig. 5, which reveals that the posterior probability value vibrates severely, even in adjacent epochs. It is due to the fact that posterior probability not only refers to the model strength, such as the GODP and ADOP, which changes mildly with time, it also determined by the introduced observation noise which changes randomly each time. The doted red line and the aqua line in Fig. 5 are almost overlapped, which means the calculated values of the upper and lower bounds are close. The calculation error, obtained by upper bound minus lower bound, is plot in Fig. 6(a). None of the calculation error surpass the predefined acceptable error $\upgamma =1{0}^{-4}$, which demonstrates that the calculation accuracy meets the requirement.

Fig. 5

Upper and lower bounds of the posterior probability under $\upgamma =1{0}^{-4}$

Fig. 6

Posterior probability calculation error under different acceptable errors: a $\upgamma =1{0}^{-4}$, b $\upgamma =1{0}^{-6}$, c $\upgamma =1{0}^{-8}$

The predefined accuracy is now changed to $\upgamma =1{0}^{-6}$ and $\upgamma =1{0}^{-8}$, respectively, in order to investigate the calculation accuracy and calculation complexity under different acceptable accuracies. As interpreted in the previous subsection, number of searched integer nodes is used as the measurement of calculation complexity. The calculation error, under required error $\upgamma =1{0}^{-6}$ and $\upgamma =1{0}^{-8},$ is plotted in Fig. 6 (b) and (c), respectively. Similar with the plot in Fig. 6 (a), none of the calculation error exceeds the predefined $\upgamma$, which demonstrates the proposed approach, as shown in Algorithm 1, can adjust the calculation according to the user defined accuracy.

This adjustment results in different search region and therefore different computational workload. The number searched integer points under acceptable error $\upgamma =1{0}^{-4}$, $\upgamma =1{0}^{-6}$ and $\upgamma =1{0}^{-8}$ is plotted in Fig. 7, in which the green line lies above the red line and below the blue line. The percentage distribution of searched nodes under $\upgamma =1{0}^{-4}$, $\upgamma =1{0}^{-6}$ and $\upgamma =1{0}^{-8}$ is shown in Fig. 8(a–c), respectively. They show that the number of searched nodes concentrated in three clusters. The clusters are 0–1000, 1000–2000, and 6000–7000 under $\upgamma =1{0}^{-4}$; 0–2000, 2000–4000, and 8000–10,000 under $\upgamma =1{0}^{-6}$; and 0–2000, 3000–4000, and 12,000–14,000 under $\upgamma =1{0}^{-8}$. These results show that the searched integer nodes increase with the enhancement of the required accuracy, which finally leads to computation burden increment.

Fig. 7

Searched integer nodes during posterior probability calculation under different acceptable errors

Fig. 8

Percentage distribution of searched integer nodes under different acceptable errors: a $\upgamma =1{0}^{-4}$, b $\upgamma =1{0}^{-6}$, c $\upgamma =1{0}^{-8}$

6.2.2 Computational burden adjustment comparison with existing approaches

Compared with the existing approaches such as Verhagen (2005), Odolinski and Teunissen (2020), Wu and Bian (2015), a major advantage of the proposed approach is that it can produce calculation result and calculation accuracy, simultaneously, while other approaches can only produce calculation result, without knowing its calculation accuracy. This advantage is explicit and has shown in the 3^rd part of Sect. 6.1. So, it will not be compared again in the following.

Another advantage is that the proposed method can produce calculation result always satisfying the user required accuracy, by adjusting the search region. On the contrary, search region of other approaches cannot be adjusted by the required accuracy. As a result, they might enumerate too many or too few integers compared with the acceptable accuracy. We are now focusing on comparison of this issue.

Assuming acceptable errors $\upgamma =1{0}^{-4}$ and $\upgamma =1{0}^{-8}$, the searched integer nodes of these approaches are plotted in Fig. 9(a) and (b). It shows in Fig. 9(a) that the black line lies above, followed by the blue line, red line, and green line, respectively, which means the computational burden is arranged by Verhagen (2005) > Odolinski and Teunissen (2020)  > new method > Wu and Bian (2015). Note that, the results of Verhagen (2005), Odolinski and Teunissen (2020), Wu and Bian (2015) are obtained by only adding the likelihoods of the enumerated integer points rather than the likelihoods of all the integer points in the space. Approaches of Verhagen (2005), Odolinski and Teunissen (2020) enumerate too many integer points than the user required accuracy ($\upgamma =1{0}^{-4}$) need, which leads to a waste of computational resource and a degrade of computational efficiency. On the contrary, using the proposed approach, this part of computational resource is reserved and time efficiency could therefore be guaranteed.

Fig. 9

Searched integer nodes during posterior probability calculation using different approaches: a $\upgamma =1{0}^{-4}$, b $\upgamma =1{0}^{-8}$

It shows in Fig. 9 (b) that the black line lies above, followed by the red line, blue line, and green line, respectively, which means the computational burden is arranged by Verhagen (2005) > new method > Odolinski and Teunissen (2020)  > Wu and Bian (2015). Note that, the searched nodes amount of Verhagen (2005), Odolinski and Teunissen (2020), Wu and Bian (2015) remain the same as the experiment under $\upgamma =1{0}^{-4}$ (seen in Fig. 9 (a)), because the “significance level” $\alpha$ and “fading factor” $\delta$ are unchanged. As a consequence, approaches of Odolinski and Teunissen (2020), Wu and Bian (2015) may enumerate too few integer points, which has a risk of calculation accuracy lower than required. On the contrary, using the proposed approach, calculation accuracy could always be guaranteed.

7 Conclusions

GNSS high precise positioning requires correct estimation of the integer ambiguity. However, the integer ambiguity solution is subject to uncertainty caused by the randomness of the data. So, it is important to validate the quality of the integer ambiguity estimation. The optimal validation criterion, in sense of maximizing the estimation success rate subjecting to a given failure rate, is the ambiguity posterior probability. An alternative approach is giving up fixing the real-valued ambiguity solution to some integer, but adjusting it according to the criterion of minimizing the solution’s mean square error (MSE) instead. This estimator comes out as the sum of all the integer vectors multiplying their posterior probabilities.

It is therefore of great significance to calculate posterior probability precisely and efficiently. However, we cannot obtain the exact value of posterior probability due to the occurrence of infinite sums. Practical calculation approaches approximate the exact value by neglecting sufficiently small terms in the sum. These calculations, although have achieved good approximation, can only serve as the upper bounds of posterior probability. Compared with upper bound, a proper lower bound of the posterior probability would be more important in application. An appreciated lower bound can prevent the user from validating the ambiguity resolution result by using an over optimistic criterion. However, these approaches can only produce an upper bound as the posterior probability calculation result, but cannot produce accuracy information about the result.

In this contribution, a pair of upper and lower bounds of the posterior probability is derived by dividing the infinite sum into two parts: the major finite part and the minor infinite part. The finite part can be calculated by an enumeration of all the elements in it. The infinite part is bounded by algebraical derivation. As a result, theoretically rigorous upper and lower bounds of the posterior probability are obtained. Based on the bounds, a posterior probability calculation approach with controllable accuracy is proposed. Meanwhile, the computational burden of the proposed approach can be adjusted flexibly according to the required accuracy. The process of the algorithm is summarized, which can be conveniently used by the user. Numerical experiments have verified the calculation accuracy and computational workload adjustment properties of the proposed approach under different acceptable error levels, which are superior to existing approaches.

The significances of this research are mainly of twofold. Theoretically, the posterior probability is bounded from below and from above simultaneously, both of the bounds are in closed form and can achieve very high precision. As far as we are concerned, it is the first theoretically rigorous lower bound of the posterior probability ever reported. Practically, compared with the existing approaches, the calculation accuracy of the proposed approach is known and under control; at the same time, the computational burden can be adjusted flexibly according to the required accuracy.