Abstract
Estimability and \(\mathcal {S}\)-systems are important concepts when dealing with rank-defect models. In this contribution, we generalize the concept of estimability to integer estimability and determine the necessary and sufficient conditions that need to be satisfied for parameter functions to be integer estimable. This is then worked out and applied to the integer estimability analysis of GNSS observation equations. We hereby consider both network ambiguity resolution and single-receiver PPP-RTK ambiguity resolution. In our analyses, use is made of graph theory and properties of the ambiguity incidence matrices of the bipartite and connected network graphs.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
The undifferenced GNSS observation equations of phase \(\phi _{r, j}^{s}\) and code \(p_{r,j}^{s}\) of receiver r (\(r=1,\ldots ,n\)) tracking satellite s (\(s=1,\ldots ,m\)) on frequency \(f_j\) (\(j=1,\ldots ,f\)) are given as (Teunissen and Kleusberg 1998; Leick 2004; Hofmann-Wellenhof et al. 2008; Teunissen and Montenbruck 2017)
with \(\rho _r^s\) being the non-dispersive term that contains positioning parameters, zenith tropospheric delays and clock parameters, and \(\iota _r^{s}\) the first-order slant ionospheric delay on the first frequency, having as coefficient \(\mu _j=(f_1^2/f_j^2)\), with \(f_j\) being the jth frequency. The receiver and satellite phase biases are denoted as \(\bar{\delta }_{r,j}\) and \(\bar{\delta }_{,j}^{s}\), respectively, and likewise the receiver and satellite code biases as \(d_{r,j}\) and \(d_{,j}^s\). The wavelength of \(f_{j}\) is \(\lambda _j\), and the integer ambiguities of \(\phi _{r,j}^{s}\) are denoted as \(z_{r,j}^s\) and are given in units of cycles.
The advantages and flexibility of using an undifferenced model formulation, as opposed to a priori differencing or combining, have already been recognized for a long time (Goad 1985; Teunissen 1995b; de Jonge 1998; Schönemann et al. 2011; Lannes and Prieur 2013). With an undifferenced approach, one can work with the simplest observational variance matrix and have all parameters remain available for a possible further model strengthening, while parameters that are not of interest are easily eliminated at the reduction level of the normal equations.
Working with an undifferenced approach implies in case of GNSS, however, that one has to account for rank deficiencies as not all unknown parameters can be estimated unbiasedly. A proper understanding of the estimability of the computed parameters is therefore essential, as different sets of estimable parameters, each with its own interpretation, exist, and each such set is defined by the chosen singularity-basis or \(\mathcal {S}\)-basis (Baarda 1973; Teunissen 1985; Koch 1999). Such analysis was presented in Odijk et al. (2015), where the rank deficiencies and null space of the multi-epoch, multi-frequency undifferenced GNSS network model were identified and used to construct a basis matrix of the network’s null space, thus allowing the formulation of proper \(\mathcal {S}\)-transformations, see also (Teunissen and Khodabandeh 2015; Zhang et al. 2018).
In all studies until now however, the standard concept of estimability (Rao 1973; Arnold 1981) was employed, which, as we show in this contribution, is too limited when dealing with rank-defect models that have parameters of which some are also integer. We show that for integer parameters, such as the carrier-phase ambiguities, estimability is not guaranteed by merely asking of the estimable functions that they are integer. We therefore generalize the concept of estimability to integer estimability and determine the necessary and sufficient conditions that need to be satisfied for parameter functions to be integer estimable. This is then worked out using concepts from graph theory for the integer estimability analysis of GNSS observation equations. We hereby consider both network ambiguity resolution and single-receiver PPP-RTK ambiguity resolution.
This contribution is organized as follows. We start by providing a brief review of the required estimability concepts of rank-defect linear models in Sect. 2. It discusses estimable functions, their invariance and \(\mathcal {S}\)-bases. This is then generalized to the estimability of parameter subsets as needed when working with partitioned GNSS models. It shows that although there are generally fewer estimable functions under weaker models, all these functions are linear combinations of the estimable functions under the stronger model. In Sect. 3, we discuss the ambiguity graph and the incidence matrix of a GNSS network. Then in Sect. 4, we introduce the concept of integer estimability and show how for GNSS networks it is driven by the structure and properties of the incidence matrix. It is hereby important to find that integer estimability is not guaranteed by merely asking of the estimable functions that they are integer. We derive the necessary and sufficient conditions that enable integer estimability and apply these findings in Sects. 5 and 6, first for ‘all-in-view’ networks and then for the general case. It is hereby proven that choosing spanning trees of the network ambiguity graph as \(\mathcal {S}\)-basis automatically guarantees that the estimable ambiguity functions are integer estimable. In Sect. 7, we apply the concept of integer estimability and its rulings to PPP-RTK and show that PPP-RTK’s single-receiver ambiguity resolution should be seen as a special case of network ambiguity resolution. The contribution is concluded with a summary in Sect. 8.
Some of the notations used are as follows: \(\mathbb {R}^{m}\) denotes the m-dimensional space of real numbers and \(\mathbb {Z}^{n}\) the n-dimensional space of integers. \({\mathsf {E}}(.)\) and \({\mathsf {D}}(.)\) denote the expectation and dispersion operators, respectively. The range and null space of a matrix A are denoted as \(\mathcal {R}(A)\) and \(\mathcal {N}(A)\), whereas \(\mathcal {R}(A)^{\perp }\) denotes the orthogonal complement of \(\mathcal {R}(A)\). A basis matrix is said to be a matrix of which the columns form a basis of its range space. Two subspaces \(\mathcal {U}\) and \(\mathcal {V}\) of \(\mathbb {R}^{m}\) are said to be complementary, denoted as \(\mathbb {R}^{m}=\mathcal {U} \oplus \mathcal {V}\), when the matrix [U, V], formed from their basis matrices U and V, is square and invertible.
2 Estimability under different model strength
2.1 Estimable functions
Consider the rank-defect linear model
Since the model is rank defect, not all parameters nor all functions of the parameters are estimable. Recall that a function \(f^{T}x\) is said to be estimable if it can be unbiasedly estimated by a linear function of y (Rao 1973; Arnold 1981). The following lemma characterizes the class of estimable functions.
Lemma 1a
(Estimable functions) Let \(F \in \mathbb {R}^{n \times p}\). Then
is estimable under model (2) if and only if (iff)
Thus, since \(\tilde{x}\) is estimable iff \(F=A^\mathrm{{T}}L\) for some \(L \in \mathbb {R}^{m \times p}\), a function \(f^\mathrm{{T}}x\) is estimable iff f can be written as a linear combination of the rows of A. Since \(\mathcal {R}(A^\mathrm{{T}})=\mathcal {N}(A)^{\perp }\), an equivalent condition of \(f^\mathrm{{T}}x\) being estimable is that f needs to annihilate that part of x that lies in the null space of A. Estimable functions of x are thus invariant for any changes in x that lie in \(\mathcal {N}(A)\). Note, since \(\mathrm{dim}\mathcal {R}(A^\mathrm{{T}})=r\), that the maximum number of such linear independent functions equals r.
The workings of the above Lemma can now be seen as follows. Consider \(\hat{x}=A^{-}y\), with \(A^{-}\) an arbitrary g-inverse of A (i.e. \(AA^{-}A=A\)). Then \({\mathsf {E}}(\hat{x})=A^{-}Ax \ne x\), showing that \(\hat{x}\) is not an unbiased estimator of x. The estimator \(F^\mathrm{{T}}\hat{x}\), however, is an unbiased estimator of \(F^\mathrm{{T}}x\), since \(F=A^\mathrm{{T}}L\) for some \(L \in \mathbb {R}^{m \times p}\), and therefore, \({\mathsf {E}}(F^\mathrm{{T}}\hat{x})=F^\mathrm{{T}}A^{-}Ax=L^\mathrm{{T}}AA^{-}Ax=L^\mathrm{{T}}Ax=F^\mathrm{{T}}x\).
The above shows one way of computing unbiased estimators for the rank-defect linear model (2): first compute \(\hat{x}\) and then \(F^\mathrm{{T}}\hat{x}\), with F satisfying (4). The flexibility of this approach lies in the fact that one only needs to compute \(\hat{x}\) once, from which one can then compute any estimable function one is interested in. Instead of this two-step approach, however, it is also possible to use a more direct approach, namely one in which one reparametrizes the linear model (2) directly into the required estimable functions. To see this, consider the reparametrization
in which \(V_{0}\) is a basis matrix of the null space \(\mathcal {N}(A)\) and \(S \in \mathbb {R}^{n \times r}\) is a basis matrix having a range space complementary to that of \(V_{0}\), i.e. \(\mathbb {R}^{n} = \mathcal {N}(A) \oplus \mathcal {R}(S)\). Then matrix \([V_{0}, S]\) is square and invertible, having the inverse
with \(E= S^{\perp }(V_{0}^\mathrm{{T}}S^{\perp })^{-1}\), \(F=V_{1}(S^\mathrm{{T}}V_{1})^{-1}\) and where the matrices \(V_{1} \in \mathbb {R}^{n \times r}\) and \(S^{\perp } \in \mathbb {R}^{n \times (n-r)}\) are basis matrices of \(\mathcal {N}(A)^{\perp }\) and \(\mathcal {R}(S)^{\perp }\), respectively, see (Teunissen 1985). Substitution of (5) into (2) gives the model
which is of full rank and directly parametrized in \(\tilde{x}\). As (7) is of full rank, it can be directly solved to obtain an unbiased solution of \(\tilde{x}\). Note that with (3) the range space of F needs to be orthogonal to \(\mathcal {N}(A)\), while with (5), and thus (7), one only needs to choose S such that its range space is complementary to \(\mathcal {N}(A)\).
Also note that the full-rank model (7) can be interpreted as being obtained from adding the minimum constraints
to the rank-defect model (2). These constraints are referred to as the \(\mathcal {S}\)-basis. They contain, by setting the inestimable part of (5) to a given arbitrary value (here \(\alpha =0\)), the minimum information needed to eliminate the singularity in (2). That is, the basis matrix \(S^{\perp }\) is chosen such that its range is complementary to the space of estimable functions \(\mathcal {R}(A^\mathrm{{T}})=\mathcal {N}(A)^{\perp }\).
2.2 Estimability in a partitioned model
As we will be considering estimability of parameter subsets in the following, we need to generalize Lemma 1a accordingly. With \(A=[A_{1}, A_{2}]\) and \(x=[x_{1}^\mathrm{{T}}, x_{2}^\mathrm{{T}}]^\mathrm{{T}}\), model (2) can be written in partitioned form as
Instead of considering the estimable functions of all parameters, we now restrict attention to those of \(x_{1}\) only. Then Lemma 1a generalizes as follows.
Lemma 1b
(Estimable functions) Let \(F_{1} \in \mathbb {R}^{n_{1} \times p}\). Then
is estimable under the partitioned model (9) iff
in which \(B_{2}\) is a basis matrix of \(\mathcal {R}(A_{2})^{\perp }\). \(\square \)
This result can be understood as follows. As, according to Lemma 1a, \(F=A^\mathrm{{T}}L\) for some \(L \in \mathbb {R}^{m \times p}\), it follows with \(F=[F_{1}^\mathrm{{T}}, 0]^\mathrm{{T}}\) and \(A=[A_{1}, A_{2}]\), that \(F_{1}=A_{1}^\mathrm{{T}}L\) and \(0=A_{2}^\mathrm{{T}}L\), from which the result follows. Thus if we would compare unbiased estimation of \(F_{1}^\mathrm{{T}}x_{1}\) by \(L^\mathrm{{T}}y\) under model \({\mathsf {E}}(y)=A_{1}x_{1}\) to that under the weaker model \({\mathsf {E}}(y)=A_{1}x_{1}+A_{2}x_{2}\), then \(\mathcal {R}(F_{1}) \subset \mathcal {R}(A_{1}^\mathrm{{T}})\) is a necessary and sufficient condition for estimability under the stronger model, but only necessary under the weaker model. For it to become necessary and sufficient under the weaker model, one needs, next to the condition \(F_{1}=A_{1}^\mathrm{{T}}L\), also that \(0=A_{2}^\mathrm{{T}}L\), i.e. that the linear functions of the data nullify the effect of \(x_{2}\).
Finally note, since \(\mathcal {R}(A_{1}^\mathrm{{T}}B_{2}) \subset \mathcal {R}(A_{1}^\mathrm{{T}})\), that although under the weaker model there are in general fewer estimable functions of \(x_{1}\), all these functions are linear combinations of the estimable functions under the stronger model.
3 Ambiguity graph and incidence matrix
In the following, attention is focused on that part of the GNSS observation equations that contains the undifferenced (UD) integer ambiguities and receiver- and satellite phase-delays (cf. 1),
where since each receiver–satellite pair corresponds to one real-valued ambiguity per frequency, we have omitted for the sake of presentation the frequency subscript j. In this section, we show that the design matrix of the ‘phase-delays’ can be interpreted as being the incidence matrix of the network ambiguity graph. This is helpful as it allows us to use results from graph theory.
It will be clear that in a network generally not all the satellites are tracked by each receiver. To visualize the interaction between the network receivers and their tracked satellites, one can make use of a graph, see, e.g. (de Jonge 1998; Lannes and Gratton 2009; Lannes and Teunissen 2011; Lannes and Prieur 2013). An example of such ambiguity graph is shown in Fig. 1. The vertices of the graph are the network receivers (solid triangles) and the tracked satellites (solid squares). The presence of an edge (grey lines) between vertices r and s indicates whether satellite s is tracked by receiver r or not. Thus, the edge r–s corresponds to the ambiguity \(a_r^s\). The ambiguity graph of Fig. 1 represents a GNSS network setup of three receivers, in which the receiver \(r=1\) tracks the satellites \(s=1,2\), while the receiver \(r=3\) tracks the satellites \(s=2,3\). The receiver \(r=2\) however, tracks all the visible satellites \(s=1,2,3\). Thus, the graph has seven edges and six vertices (three receivers plus three satellites). As there is no interaction between the satellites themselves nor between the receivers (i.e. there is no edge between the satellites nor between the receivers), the ambiguity graph is a special case of a ‘bipartite’ graph.
3.1 The ambiguity graph incidence matrix
Let a network of r receivers, tracking m satellites, have q network ambiguities \(a_r^s\) (per frequency). Then the corresponding ambiguity graph has q edges and \(n_v=m+n\) vertices. We define the ambiguity vector as \(a=[a_r^s]\) containing all the UD ambiguities \(a_r^s\). The vectorial form of (12) is then given as
where z contains the integer ambiguities \(z_r^s\) and \(\bar{\delta }\) contains the real-valued phase-delays \(\bar{\delta }_r\), \(\bar{\delta }^s\). The \(q\times n_v\) matrix \(\bar{P}\) has either 0 or \(\pm 1\) as its entries. For the ambiguity graph of Fig. 1, (13) reads
Every row of \(\bar{P}\) corresponds to an edge of the graph, whereas every column of \(\bar{P}\) corresponds to a vertex. As shown in (14), every row of \(\bar{P}\) contains exactly one entry equal to \(+1\) and another equal to \(-1\). These nonzero entries (i.e. \(\pm 1\)) indicate whether their corresponding row is incident with the graph’s vertices or not. For instance in (14), the fifth row of \(\bar{P}\) (corresponding to \(a_2^3\)) has \(\pm 1\) entries on its ‘second’ (\(r=2\)) and ‘sixth’ (three receivers plus \(s=3\)) columns, showing that there exists an edge between the vertices \(r=2\) and \(s=3\). In the context of graph theory, matrix \(\bar{P}\) is therefore referred to as the incidence matrix of a graph, see, e.g. (Coxeter 1973; Wilson 1996). As \(\bar{P}\) captures the complete incidence structure of a graph, it uniquely specifies its associated graph. In the context of GNSS observation equations, the incidence matrix \(\bar{P}\) is nothing else but the design matrix of the phase-delays \(\bar{\delta }_r\) and \(\bar{\delta }^s\). Thus, a network ambiguity graph can be fully specified by the network’s phase-delay design matrix.
3.2 Reduced incidence matrix
Note that the columns of \(\bar{P}\) sum up to zero, showing that \(\bar{P}\) is ‘rank-deficient’. The size of its rank deficiency is driven by the ‘connectivity’ of its associated graph (Coxeter 1973; Wilson 1996). A graph is said to be connected, if every vertex is linked to all other vertices at least through one ‘path’ (i.e. a set of edges). The incidence matrix of a connected graph is shown to have a rank deficiency of size 1 (see “Appendix A”). From now on, we assume that the ambiguity graph is connected, i.e. the rank of \(\bar{P}\) is \(n_v-1\). If the ambiguity graph would not be connected, then it could be partitioned into multiple connected subgraphs. This assumption is therefore of no consequence for our analysis.
For a connected graph, a maximum number of independent columns of \(\bar{P}\) simply follow by ‘excluding’ an arbitrary column (see “Appendix A”). The resultant matrix, of size \(q\times (n_v-1)\), is referred to as the reduced incidence matrix and is denoted by P. Thus, the phase-delay combinations \(\bar{P}\,\bar{\delta }\), given in (13), can be alternatively expressed by \(P\delta \), with \(\delta \) being a linear function of the phase-delay vector \(\bar{\delta }\). For instance in the case of (14), we have
in which the reduced incidence matrix P is formed by removing the first column of \(\bar{P}\). The identity \(\bar{P}\bar{\delta }=P\delta \), together with (13), gives
where \(\delta \) contains \({\delta }_r=\bar{\delta }_r-\bar{\delta }_1\) (\(r=2,\ldots ,n\)) and \({\delta }^s=\bar{\delta }^s-\bar{\delta }_1\) (\(s=1,\ldots ,m\)).
4 Integer ambiguity estimability
4.1 Estimability
For the purpose of ambiguity resolution (Teunissen 1995b), it would be ideal if the complete vector \(z \in \mathbb {Z}^{q}\) of (16) would be unbiased estimable. This is, however, not the case due to the presence of the unknown phase-delays. According to Lemma 1b (cf. 11), a necessary condition for functions of the integer ambiguities, say \(D^\mathrm{{T}}z\), to be estimable is that \(D^\mathrm{{T}}P=0\) must hold true. Finding an independent set of such estimable ambiguities boils thus down to finding a basis matrix D of the \(\tilde{q}\)-dimensional subspace \(\mathcal {R}(P)^{\perp }\), where \(\tilde{q}=q-n_{v}+1\).
With the space of estimable ambiguity functions given by \(\mathcal {R}(D) \subset \mathbb {R}^{q}\), any space complementary to it can be used for choosing an ambiguity \(\mathcal {S}\)-basis. Therefore, if C is a \(q \times (n_{v}-1)\) basis matrix having a range space complementary to that of D, i.e. \(\mathbb {R}^{q}=\mathcal {R}(C) \oplus \mathcal {R}(D)\), then \(C^\mathrm{{T}}z\) is a set of inestimable functions that can be chosen as \(\mathcal {S}\)-basis.
As the two basis matrices C and D together form a square and invertible matrix, we can now reparametrize the integer ambiguity vector z into its inestimable and estimable part by making use of the inverse
in which \(q \times \tilde{q}\) matrix R is a basis matrix of \(\mathcal {R}(C)^{\perp }\), i.e. \(C^\mathrm{{T}}R=0\). With the help of this inversion, we can decompose z into an inestimable and estimable part as \( z = P \left[ (C^\mathrm{{T}}P)^{-1}C^\mathrm{{T}}z\right] + R\left[ (D^\mathrm{{T}}R)^{-1}D^\mathrm{{T}}z\right] \), which, when substituted into (16), gives
with
The above reparametrization has thus achieved that the rank-defect matrix \([P, I_{q}]\) of (16) gets replaced by the full-rank matrix [P, R], and the inestimable parameters \(\delta \) and z, by their estimable versions \(\tilde{\delta }\) and \(\tilde{z}\), respectively. The estimable phase-delays are hereby formed from lumping the inestimable part of z to the original phase-delay vector \(\delta \).
4.2 Integer estimability
Although the entries of \(\tilde{z}\) in (18) are estimable ambiguity functions, they are not necessarily integer. For the purpose of integer ambiguity resolution however, they need to be integer. This implies that important additional restrictions apply to the basis matrix \(\tilde{D}=D (R^\mathrm{{T}}D)^{-1}\) of \(\tilde{z}=\tilde{D}^\mathrm{{T}}z\). Firstly, since \(\tilde{z}\) should be integer for every \(z \in \mathbb {Z}^{q}\), matrix \(\tilde{D}\) should be integer as well. A necessary condition for \(\tilde{z}\) to be integer estimable is thus that \(\tilde{D}\) should not only be a basis matrix of \(\mathcal {R}(P)^{\perp }\), but it should be an integer matrix as well. This condition is, however, not yet sufficient. To see this, we first consider the ambiguity transformations that are implied by (19).
Note that in the construction of estimable functions, different choices for the range space of the basis matrix C (i.e. different ambiguity \(\mathcal {S}\)-bases, say \(C_{1}\) and \(C_{2}\), with \(\mathcal {R}(C_{1}) \ne \mathcal {R}(C_{2})\)) lead to different sets of estimable ambiguity functions, say \(\tilde{z}_{R_{1}}=\tilde{D}_{1}^\mathrm{{T}}z\) and \(\tilde{z}_{R_{2}}=\tilde{D}_{2}^\mathrm{{T}}z\), with \(\tilde{D}_{1}^\mathrm{{T}}= (D^\mathrm{{T}}R_{1})^{-1}D^\mathrm{{T}}\) and \(\tilde{D}_{2}^\mathrm{{T}}= (D^\mathrm{{T}}R_{2})^{-1}D^\mathrm{{T}}\). The transformations between \(\tilde{z}_{R_{1}}\) and \(\tilde{z}_{R_{2}}\), i.e. \(\tilde{z}_{R_{2}}=\mathcal {Z}_{21}\tilde{z}_{R_{1}}\) and its inverse \(\tilde{z}_{R_{1}}=\mathcal {Z}_{12}\tilde{z}_{R_{2}}\), are then given as
which is easily checked by recognizing that \(P_{\mathcal {R}(P)^{\perp }}= \tilde{D}_{1}(\tilde{D}_{1}^\mathrm{{T}}\tilde{D}_{1})^{-1}\tilde{D}_{1}^\mathrm{{T}}\) is a projector that projects along the null space of \(\tilde{D}_{2}^\mathrm{{T}}\), and thus, \(\mathcal {Z}_{21}\tilde{D}_{1}^\mathrm{{T}}=\tilde{D}_{2}^\mathrm{{T}}P_{\mathcal {R}(P)^{\perp }}=\tilde{D}_{2}^\mathrm{{T}}\).
The result shows, although integerness of \(\tilde{D}_{1}\) and \(\tilde{D}_{2}\) guarantees that both \(\tilde{z}_{R_{1}}\) and \(\tilde{z}_{R_{2}}\) are integer whenever z is, that this condition is not sufficient to guarantee that the transformations (20) themselves are integer preserving, i.e. they are admissible as ambiguity \(\mathcal {Z}\)-transformations. A \(\mathcal {Z}\)-transformation is namely only admissible as ambiguity transformation if both \(\mathcal {Z}\) and its inverse are integer, or equivalently, if \(\mathcal {Z}\) is integer with determinant \(\mathrm{det}(Z) = \pm 1\) (Teunissen 1995a). Only then will integerness be preserved, i.e. any integer \(\tilde{z}_{1}\) be mapped to an integer \(\tilde{z}_{2}\) and vice versa.
The reason for the lack of admissibility of (20) can also be understood as follows. With \(\tilde{D}\) being only an integer basis matrix, it is not guaranteed that an integer solution of \(\tilde{z}=\tilde{D}^\mathrm{{T}}z\) exists for every integer \(\tilde{z}\) (think for instance of the simple case: \(1=[2, 4] [z_{1}, z_{2}]^\mathrm{{T}}\)). This sufficiency condition is needed however, since without it one has no guarantee that an integer-resolved estimable ambiguity would actually correspond with an integer value of the undifferenced ambiguity vector z. A necessary and sufficient condition for \(\tilde{z}\) to be integer estimable is thus that the transpose of the basis matrix \(\tilde{D}\) maps \(\mathbb {Z}^{q}\)onto\(\mathbb {Z}^{\tilde{q}}\) (\(\tilde{q}=q-n_{v}+1\)). The following result provides the corresponding integer characterization of estimable ambiguity functions.
Theorem
(Integer estimability) Let the functions \(\tilde{z}=\tilde{D}^\mathrm{{T}}z\) be estimable, i.e. \(\tilde{D}\) is a basis matrix of a subspace of \(\mathcal {R}(P)^{\perp }\). Then \(\tilde{z}\) is integer estimable iff a \(\mathcal {Z}\)-transformation (i.e. \(\mathcal {Z}, \mathcal {Z}^{-1} \in \mathbb {Z}^{q \times q}\)) exists such that \(\tilde{D}^\mathrm{{T}}\mathcal {Z}=[0, I_{\tilde{q}}]\), with \(\tilde{q}\) being the dimension of the subspace of \(\mathcal {R}(P)^{\perp }\). \(\square \)
For a proof, see “Appendix B”. Using the result of this theorem, we can now verify that the transformations (20) are indeed admissible if both \(\tilde{z}_{1}\) and \(\tilde{z}_{2}\) are constructed as integer estimable ambiguity vectors. With \(\tilde{D}_{1}^\mathrm{{T}}\mathcal {Z}_{1}=[0, I_{\tilde{q}}]\) and \(\tilde{D}_{2}^\mathrm{{T}}\mathcal {Z}_{2}=[0, I_{\tilde{q}}]\), it follows from (20) that \(\mathcal {Z}_{21}=\tilde{D}_{2}^\mathrm{{T}}\mathcal {Z}_{1}[0, I_{\tilde{q}}]^\mathrm{{T}}\) and \(\mathcal {Z}_{12}=\tilde{D}_{1}^\mathrm{{T}}\mathcal {Z}_{2}[0, I_{\tilde{q}}]^\mathrm{{T}}\), which indeed are now both integer. The following example provides further insights into the condition \(\tilde{D}^\mathrm{{T}}\mathcal {Z}=[0, I_{\tilde{q}}]\) of the theorem.
Example 1
(Multi-frequency combinations) In view of the recent multi-frequency modernized signals, several contributions propose ‘combined’ carrier-phase observations to reduce the impact of the ionosphere and/or to minimize the variance of the resultant combinations, see, e.g. (Richert and El-Sheimy 2007; Feng 2008; Cocard et al. 2008; Shu et al. 2017; Duong et al. 2019). We now show that care has to be exercised when forming multi-frequency carrier-phase combinations. Using a geometry-free zero-baseline setup (Teunissen 1997), 20,000 DD ambiguity samples of the Galileo satellite pair E13–E26 have been collected on the three frequencies E1 (\(z_1\)), E5a (\(z_2\)) and E5b (\(z_3\)). The goal is to integer-resolve their multi-frequency combined version \(\tilde{z}=[2,~ 4, -6][z_1,~ z_2,~ z_3]^\mathrm{{T}}=2z_1+4z_2-6z_3\), see (Feng 2008). As the DD ambiguities \(z_j\) (\(j=1,2,3\)) are estimable and integer, \(\tilde{z}\) is estimable and integer as well. However, \(\tilde{z}\) is not integer estimable since
thereby not satisfying the condition \(\tilde{D}^\mathrm{{T}}\mathcal {Z}=[0, I_{\tilde{q}}]\). This can also be understood from the fact \(\tilde{z}\) only takes ‘even’ numbers, i.e. \(\tilde{z}=2(z_1+2z_2-3z_3)\). Figure 2 shows a histogram of fixed solutions for \(\tilde{z}\) (top) compared to those for the corresponding integer-estimable ambiguity \(\tilde{\tilde{z}}=[1,~ 2, -3][z_1,~ z_2,~ z_3]^\mathrm{{T}}=z_1+2z_2-3z_3\) (bottom). Only 11.5% of the samples deliver correct solution (green bar) for \(\tilde{z}\), whereas 49.9% of the samples lead to odd numbers and therefore non-admissible solutions (red bars). By taking the integer-estimable \(\tilde{\tilde{z}}\) however, the percentage of correctly fixed samples becomes almost double (22.7%), while all solutions are now admissible (as \(\tilde{\tilde{z}}\) can take any integer number). \(\boxtimes \)
Another important consequence of the theorem is that it shows how R (cf. 18), and thereby C (cf. 17), needs to be chosen so as to guarantee that \(\tilde{z}\) is integer estimable. Since \((D^\mathrm{{T}}R)^{-1}D^\mathrm{{T}}[P, R]=[0, I_{\tilde{q}}]\), it follows that the integer estimability of \(\tilde{z}=(D^\mathrm{{T}}R)^{-1}D^\mathrm{{T}}z\) is automatically guaranteed if R is chosen such that [P, R] becomes a \(\mathcal {Z}\)-transformation. In the next two sections, we show how this works out for GNSS networks, starting with the all-in-view case, followed by the general case.
5 Finding integer-estimable GNSS ambiguities: the all-in-view case
Finding representations for the required GNSS network matrices C, D, P and R is made simpler if we may assume the all-in-view case, i.e. when all n receivers of the network track all the m satellites. The number of UD ambiguities \(z_{r}^{s}\) (per frequency) is then equal to mn, and the network ambiguity graph attains its maximum number of edges \(q=mn\). This ‘all-in-view’ situation is of course not always realized with large-scale networks (e.g. Fig. 4), meaning that in general \(q< mn\). But to gain insight, it helps to start with the simpler case \(q=mn\) and thus assume that we are dealing with a sufficiently small network having an ambiguity graph that attains its maximum number of edges.
5.1 The reduced incidence matrix
If we define the network undifferenced (UD) ambiguity vector \(z\in \mathbb {R}^{mn}\) for the all-in-view case as
for \(r=1,\ldots ,n\), the graph incidence matrix \(\bar{P}\), i.e. the design matrix of the phase-delays, is given as (Odijk et al. 2015)
where \(e_n\) denotes the n-vector of ones and \(\otimes \) denotes the Kronecker matrix product (Henderson et al. 1983). The first n columns, i.e. \(I_n\otimes e_m\), form the design matrix of the receiver phase-delays \([\bar{\delta }_1,\ldots ,\bar{\delta }_n]^\mathrm{{T}}\), whereas the remaining m columns \(-e_n\otimes I_m\) form the design matrix of the satellite phase-delays \([\bar{\delta }^1,\ldots ,\bar{\delta }^m]^\mathrm{{T}}\).
As the reduced incidence matrix P can be obtained by removing the first column from \(\bar{P}\), we partition the identity matrix as \(I_n=[c_n,C_n]\), in which the n-vector \(c_n\) denotes the first column and the \(n\times (n-1)\) matrix \(C_n\) contains the other \((n-1)\) columns of \(I_n\). By removing the first column of \(\bar{P}\) in (23), the reduced incidence matrix P follows as
5.2 Estimable ambiguities
It is now not difficult to find a basis matrix of the \(mn-m-n+1=(m-1)(n-1)\) dimensional space \(\mathcal {R}(P)^{\perp }\). Let
Then clearly \(D_n^\mathrm{{T}}e_n=0\) and \(D_m^\mathrm{{T}}e_m=0\). An \(mn \times (m-1)(n-1)\) basis matrix D, satisfying \(D^\mathrm{{T}}P=0\), follows therefore as
As the \((n-1)\times n\) matrix \(D_n^\mathrm{{T}}\) forms between-receiver differences, while the \((m-1)\times m\) matrix \(D_m^\mathrm{{T}}\) forms between-satellite differences, the transpose of (26) is known as the double-differencing operator (Khodabandeh and Teunissen 2017). With D being a basis matrix of \(\mathcal {R}(P)^{\perp }\), it follows from Lemma 1b that the entries of \(D^\mathrm{{T}}z\) form an independent set of estimable functions of the undifferenced ambiguities. We can therefore immediately conclude the following.
Corollary 1
(DD ambiguities) Functions of UD ambiguities are estimable iff they are double-differenced (DD) ambiguities or functions thereof.
This result shows that undifferenced (UD) and single-differenced (SD) ambiguities are not estimable. This holds true not only for network ambiguity resolution, but also for single-receiver ambiguity resolution as, for instance, used in PPP-RTK (Ge et al. 2008; Laurichesse et al. 2009b; Odijk et al. 2015). PPP-RTK ambiguity resolution is thus not an undifferenced or a zero-difference ambiguity resolution (Laurichesse et al. 2009a; Collins et al. 2010), but one which is still of a double-differenced nature (see also Sect. 7).
As estimability depends on the underlying model, estimability of parameters may change if assumptions of the underlying model change. The following gives such an example concerning ambiguity estimability.
Example 2
(Frequency-differenced ambiguities) Consider the ambiguity equations for \(a_{r,j}^s\) (\(j=1,2\)) of a single receiver–satellite pair r–s,
If we now change our underlying assumptions and assume that the phase-delays are not frequency dependent, but common for both frequencies \(j=1,2\), i.e. \(\bar{\delta }_{r,j}=\bar{\delta }_{r}\) and \(\bar{\delta }_{,j}^s=\bar{\delta }^s\), then the above Eq. (27) simplify to
In this case, the rows of P are copies of one another, and the integer basis matrix (vector) \(D=[-1,+1]^\mathrm{{T}}\) fulfils \(D^\mathrm{{T}}P=0\), thus showing that estimable ambiguities will now be of frequency-differenced form, \(z_{r,2}^s-z_{r,1}^s\), or functions thereof. \(\square \)
5.3 Constructing the \(\mathcal {Z}\)-transformation
To find a representation for R such that [P, R] is a \(\mathcal {Z}\)-transformation, note, since D of (26) is integer, that \(\tilde{z}=(D^\mathrm{{T}}R)^{-1}D^\mathrm{{T}}z\) will also be integer if we choose R to be a right-inverse of D, i.e. \(D^\mathrm{{T}}R=I_{\tilde{q}}\), \(\tilde{q}=(n-1)(m-1)\). Since the \(D_{n}\) and \(D_{m}\) of (25) satisfy \(D_{n}^\mathrm{{T}}C_{n}=I_{n-1}\) and \(D_{m}^\mathrm{{T}}C_{m}=I_{m-1}\), the simplest such \(mn \times \tilde{q}\) matrix R is given as
As it can be verified that [P, R] is now indeed a \(\mathcal {Z}\)-transformation satisfying \(D^\mathrm{{T}}[P, R]=[0, I_{\tilde{q}}]\), it directly follows from the theorem that D of (26) provides integer estimability and not only estimability.
The following example illustrates the importance of both [P, R] and \([P, R]^{-1}\) being integer.
Example 3
(\([P, R]^{-1}\) integer or not) Let the reduced incidence matrix be given as
and choose R as \(R=[0, 0, 0, 1]^\mathrm{{T}}\). Then [P, R] is integer having the integer inverse
In the last row of the inverse matrix, we recognize \(\tilde{D}=[1,-1,-1,1]^\mathrm{{T}}\) as a DD basis matrix that indeed guarantees integer estimability.
Now, let the reduced incidence matrix P be augmented with another matrix, e.g. \(R=[0, 0, 0, 2]^\mathrm{{T}}\). Then the corresponding inverse reads
Although the last row of the inverse matrix, i.e. \(\tilde{D}^\mathrm{{T}}=[0.5,-0.5,-0.5,0.5]\), is still of DD form, it now does not guarantee integer estimability. \(\square \)
5.4 Choosing the ambiguity \(\mathcal {S}\)-basis
To find the corresponding ambiguity \(\mathcal {S}\)-basis of (29), recall that its \(mn \times (m+n-1)\) basis matrix C satisfies \(C^\mathrm{{T}}R=0\) (cf. 17). Since \(c_{n}^\mathrm{{T}}C_{n}=0\) and \(c_{m}^\mathrm{{T}}C_{m}=0\), both \(c_{n} \otimes I_{m}\) and \(I_{n} \otimes c_{m}\) have range spaces orthogonal to that of R. However, they are not linearly independent, since they have \(c_{n} \otimes c_{m}\) in common. To avoid counting these twice, we eliminate one of them and thus obtain
We can now determine how the integer-estimable ambiguity vector \(\tilde{z} \in \mathbb {Z}^{(m-1)(n-1)}\) and estimable phase-delay vector \(\tilde{\delta } \in \mathbb {R}^{m+n-1}\) are related to the original undifferenced ambiguities and phase-delays. With the above D (cf. 26), R (cf. 29) and C (cf. 33), they read as
which works out in components as
in which use is made of the differencing notations \((.)_{1r}^{1s}= (.)^{1s}-(.)_{1r}\), \((.)_{1r} = (.)_{r}-(.)_{1}\) and \((.)^{1s} = (.)^{s}-(.)^{1}\).
As \(C^\mathrm{{T}}z\) constitutes the ambiguity \(\mathcal {S}\)-basis, the choice (33), that leads to the estimable functions (34), is given in components as
This ambiguity \(\mathcal {S}\)-basis is thus formed from the \(m+n-1\) edges that connect receiver \(r=1\) with all m satellites and the remaining \(n-1\) receivers with the first satellite \(s=1\). Such set of edges is called a spanning tree of the ambiguity graph. As we will see below, this approach of generating integer-estimable ambiguities by choosing the edges of a spanning tree as ambiguity \(\mathcal {S}\)-basis holds true for the general case as well.
6 Finding integer-estimable GNSS ambiguities: the general case
6.1 Spanning trees
As spanning trees play a pivotal role in automatically generating integer-estimable ambiguities by means of their choice of ambiguity \(\mathcal {S}\)-basis, we first give their definition.
Definition
(Spanning tree) A connected subgraph of a graph is called a spanning tree if it includes all of the vertices of the main graph, with minimum possible number of edges.
Spanning trees are not unique. Figure 3 shows all 15 spanning trees of the ambiguity graph given in Fig. 1. In each case, pivot edges (in red) form a spanning tree, leaving only two rover edges (in blue).
With P being the reduced incidence matrix of the network and D an integer basis matrix that guarantees integer estimability, the total number of spanning trees of a network ambiguity graph is given by (cf. 54 and 55 in “Appendices A and B”)
That the number of spanning trees of a graph is finite shows that ambiguity pivoting can be done in a ‘finite’ number of ways. Depending on the number of receivers and tracked satellites however, this finite number can be very large.
Example 4
(All-in-view case) One can substitute the ’all-in-view’ basis matrix \(D = D_n\otimes D_m\) into the second expression of (36) to compute the total number of spanning trees of this particular graph. This yields
The second equality follows from the matrix identity \((A_1A_2\otimes B_1B_2)=(A_1\otimes B_1)(A_2\otimes B_2)\), whereas the third equality follows from the determinant identity \(\mathrm{det}(A\otimes B)= \{\mathrm{det}(A)\}^{l}\{\mathrm{det}(B)\}^{k}\) for any \(A\in \mathbb {R}^{k\times k}\) and \(B\in \mathbb {R}^{l\times l}\). The last equality follows from \(\mathrm{det}(D_n^\mathrm{{T}}D_n)=n\) (“Appendix B”). For instance, the ambiguity graph of a network of 20 receivers (\(n=20\)), all commonly tracking 10 satellites (\(m=10\)), has \(20^9\times 10^{19}=5.12\times 10^{30}\) different spanning trees.
Example 5
(General case) Figure 4 shows an ambiguity graph of 24 permanent stations (\(n=24\)) tracking 12 GPS satellites (\(m=12\)) over Australia. The number of edges, i.e. the number of UD ambiguities (per frequency), is \(q = 187\). To compute the total number of spanning trees of the graph, one can form matrix P by removing the first column of the network’s phase-delay design matrix \(\bar{P}\) (cf. 14). Given matrix P, we follow the first expression of (36) and compute \(\mathrm{det}(P^\mathrm{{T}}\!P)\). Accordingly, the total number of spanning trees that the graph in Fig. 4 has is approximately \(4.1579\times 10^{31}\).
Although the number of spanning trees can be very high, for our purpose of establishing integer estimability fortunately only one of them is needed. There exist several efficient algorithms to form a spanning tree, see, e.g. Kruskal’s and Prim’s algorithms (Kruskal 1956; Prim 1957; de Jonge 1998; Cormen et al. 2009). The spanning tree, shown in Fig. 4 (the red edges), has been formed using Prim’s algorithm.
6.2 Ambiguity \(\mathcal {S}\)-basis
Although the concept of integer estimability did not yet exist, de Jonge (1998) was the first to find that by fixing the edges of an ambiguity spanning tree, integer combinations of the network’s undifferenced ambiguities could be computed, see also (Lannes and Prieur 2013). In the context of integer estimability, this can be formulated as follows.
Lemma 2
(Ambiguity \(\mathcal {S}\)-basis) Choosing the edges of a spanning tree of an ambiguity graph as ambiguity \(\mathcal {S}\)-basis automatically produces integer-estimable ambiguities.\(\square \)
As no general proof was given in de Jonge (1998), we give the proof here with the help of our integer estimability theorem. First note, since a spanning tree is a subgraph, that its reduced incidence matrix consists of rows of the reduced incidence matrix of the graph. Furthermore, since a spanning tree has a minimum number of edges, the reduced incidence matrix of a spanning tree is square and invertible. We can therefore always sort the edges of a connected ambiguity graph such that the first \(n_{v}-1\) rows of its \(q \times (n_{v}-1)\) reduced incidence matrix P correspond with the edges of a spanning tree, to give \(P=[P_{1}^\mathrm{{T}}, P_{2}^\mathrm{{T}}]^\mathrm{{T}}\), where \(P_{1}\) is the reduced incidence matrix of the spanning tree. And since a spanning tree’s reduced incidence matrix and its inverse are both integer (see “Appendix A.3”), removing \(C=[I_{n_{v}-1}, 0]^\mathrm{{T}}\) from \([P, I_{q}]=[P, [C,R]]\) gives an integer matrix [P, R] that has an integer inverse as well,
This shows, as \(\tilde{D}= [-P_{2}P_{1}^{-1} , I_{q-n_{v}+1}]^\mathrm{{T}}\) satisfies the conditions of the theorem, that by choosing the ambiguity \(\mathcal {S}\)-basis as \(C=[I_{n_{v}-1}, 0]^\mathrm{{T}}\), one automatically produces a \(\tilde{D}\)-matrix having the integer estimability properties. Thus more generally, this shows that by eliminating the columns of the unit matrix \(I_{q}\) that correspond with the edges of the chosen spanning tree, the resulting \(q \times \tilde{q}\) matrix R extends the reduced incidence matrix to a \(\mathcal {Z}\)-transformation having the property that \(\tilde{D}\) of \([P, R]^{-1}=[\tilde{C}, \tilde{D}]^\mathrm{{T}}\) satisfies the required property of the theorem.
We now give a few examples to see this at work.
Example 6
(Spanning trees forming DD combinations) According to (15), the ambiguity vector z and the reduced incidence matrix P of the ambiguity graph in Fig. 1 read
The goal is to extend the \(7\times 5\) matrix P into a square and invertible matrix, with integer inverse \([P,R]^{-1}=[\tilde{C}, \tilde{D}]^\mathrm{{T}}\). Let us choose the ‘first’ spanning tree given in Fig. 3. Accordingly, the pivot edges (in red) correspond to the ambiguities \(z_1^1\) (1st edge), \(z_1^2\) (2nd edge), \(z_2^2\) (4th edge), \(z_2^3\) (5th edge) and \(z_3^2\) (6th edge). The corresponding \(7\times 2\) matrix R follows then by eliminating the first, second, fourth, fifth and sixth columns of the identity matrix \(I_7\). Inversion of [P, R] gives
The corresponding integer-estimable ambiguities \(\tilde{D}^\mathrm{{T}}z\) are thus formed as follows
in which use is made of the differencing notations \((.)_{1r} = (.)_{r}-(.)_{1}\) and \((.)^{1s} = (.)^{s}-(.)^{1}\). As shown, both the integer-estimable ambiguities \(-z_{12}^{12}\) and \(z_{23}^{23}\) are of the DD form. These DD ambiguities correspond to the rover ambiguities \(z_2^1\) (third edge) and \(z_3^3\) (seventh edge), i.e. the edges in blue.
Now let us, instead of the ‘first’ spanning tree, choose the ‘tenth’ spanning tree in Fig. 3. Accordingly, the rover ambiguities (edges in blue) become \(z_1^1\) (first edge) and \(z_2^2\) (fourth edge). The corresponding \(7\times 2\) matrix R follows then by selecting the first and fourth columns of the identity matrix \(I_7\). Inversion of [P, R] gives
The corresponding integer-estimable ambiguities \(\tilde{D}^\mathrm{{T}}z\) are thus formed as follows
While \(z_{23}^{23}\) is a DD ambiguity, \(+z_{12}^{12}-z_{23}^{23}\) is an integer function of the DD ambiguities \(+z_{12}^{12}\) and \(z_{23}^{23}\). \(\square \)
7 Relation to PPP-RTK
So far, our discussion was restricted to typifying integer estimability for ambiguity resolution in a network of GNSS receivers. PPP-RTK, however, is a precise point positioning concept that allows users of a single receiver to apply ambiguity resolution as well, see, e.g. (Ge et al. 2008; Laurichesse et al. 2009b; Collins et al. 2010; Teunissen et al. 2010; Odijk et al. 2015). In this section, we will show how this can be reconciled with Corollary 1. We show, by means of an application of the theorem, that PPP-RTK ambiguity resolution is to be interpreted as a special case of network ambiguity resolution.
7.1 Network + single − receiver user
As before, a network of n receivers is tracking m satellites. Let a user with a single receiver u track \(m_u\) out of those m satellites (\(s=1,\ldots ,m\)). Thus, \(m_u\le m\). Similar to (12), we can write for the user ambiguities and phase-delays \(a_u^i=z_u^i-\bar{\delta }^i+\bar{\delta }_u\) or \(a_u^i=z_u^i-(\bar{\delta }^i-\bar{\delta }_{1})+(\bar{\delta }_u-\bar{\delta }_{1})\), \(i \in \{1, \ldots , m\}\). Collecting them in an \(m_{u} \times 1\) vector \(a_u=[a_u^i]\), we can write, similar to (16), in vector–matrix form
where \({\delta }_u=\bar{\delta }_u-\bar{\delta }_1\). As \(\delta _u\) is present in all \(m_{u}\) user ambiguities \(a_u^j\), the associated design matrix is given as the vector of ones \(e_{m_u}\). The coefficient matrix \(P_u\) links \(\delta \), given in (16), to the user ambiguity vector \(a_u\).
Note that the first \((n-1)\) entries of \(\delta \) are the network receiver phase-delays \(\delta _r\) (\(r=2,\ldots ,n\)) that are not present in \(a_u\) (cf. 15). Thus, the first \((n-1)\) columns of \(P_u\) are zeros. Only \(m_u\) columns out of the remaining m columns of \(P_u\) are nonzeros. These \(m_u\) nonzero columns form the identity matrix \(I_{m_u}\) that correspond to the \(m_u\) satellites tracked by the user receiver u. This shows that the \(m_u\times (n_v-1)\) matrix \(P_u\) has \(m_u\) independent columns, meaning that there is no nonzero vector d that can fulfil \(d^\mathrm{{T}}P_u=0\). In other words, as no basis matrix D with the property \(D^\mathrm{{T}}P_u=0\) can be found, one must conclude with reference to Lemma 1b that no estimable functions of the integer user ambiguities \(z_{u}\) exist. This proves the following.
Corollary 2
Unaided single-receiver integer ambiguity resolution is not possible.
As unaided single-receiver ambiguity resolution is not possible, we now bring the network into play. Combining (16) and (44) gives
This set of \(q+m_{u}\) equations is the equivalent to (16), i.e. it can again be seen as a set of network equations but now of a network that includes the user receiver. The \((q+m_{u}) \times (n_{v}-1+1)\) matrix \(P^{+}\) can thus be seen as the reduced incidence matrix of this extended network. It is therefore this matrix that in combination with the theorem will determine whether or not functions of the integer ambiguities are integer estimable.
7.2 Integer recovery of real-valued ambiguities
Writing (45) as
we note that the rank defect of the \((q+m_{u}) \times (n_{v}+m_{u})\) matrix is now \(n_{v}-1 +1 = m+(n+1)-1\). Thus, the addition of the user receiver increased the rank defect by 1, which implies that the dimension of the \(\mathcal {S}\)-basis needs to be increased by 1 as well. A simple choice would be to take the one of the network (i.e. replace \([P, I_{q}]\) by [P, R]) and include the user phase-delay \(\delta _{u}\) in it (i.e. replace \([e_{m_{u}}, I_{m_{u}}]\) by \(I_{m_{u}}\)). This would then indeed result in estimable parameters and even in an integer matrix with integer inverse. However, this would not result in integer-estimable ambiguities, since the inclusion of the user phase-delay in the \(\mathcal {S}\)-basis implies that one is not taking functions of only the integer ambiguities.
The elimination of the additional rank defect thus needs to be found in reducing the \(I_{m_{u}}\)-matrix of (46) to rank \(m_{u}-1\). The simplest such choice is to have one of the user integer ambiguities, say the first \(z_{u}^{1}\), become part of the extended \(\mathcal {S}\)-basis, thus replacing \(I_{m_{u}}\) by \(C_{m_{u}}\). The resulting full-rank system, parametrized in estimable parameters, reads then
It is easily verified with the use of \([e_{m_{u}}, C_{m_{u}}]^{-1}=[c_{m_{u}}, D_{m_{u}}]^\mathrm{{T}}\) that also the integer coefficient matrix \(\mathcal {Z}\) of (47) has an integer inverse. The system (47) can therefore be seen as the ‘network + user’ extension of (18).
If we now solve (47) for the estimable user phase-delay \(\tilde{\delta }_{u}\) and integer-estimable user ambiguities \(\tilde{z}_{u}\), we obtain
This result now clearly shows the integer-recovery role that is played by the network-determined satellite phase-delays. By adding the estimable satellite phase-delays of the user-tracked satellites, \(-P_{u}\tilde{\delta }\) (note that the nonzero entries of \(P_{u}\) are negative), to the real-valued user ambiguities \(a_{u}\), one obtains, after taking satellite differences through \(D_{m_{u}}^\mathrm{{T}}\), the integer-estimable user ambiguities \(\tilde{z}_{u}\).
7.3 Integer-estimable user ambiguities interpreted
We will now prove the following.
Corollary 3
(PPP-RTK) Single-receiver ambiguity resolution is a special case of network ambiguity resolution.
For the proof, we will express \(\tilde{z}_{u}\) of (48) in the original undifferenced integer ambiguities z and \(z_{u}\). Substitution of (44) and \(\tilde{\delta }=\delta +(C^\mathrm{{T}}P)^{-1}C^\mathrm{{T}}z\) of (19) into (48) gives
This shows that the integer-estimable user ambiguities not only depend on the user ambiguities \(z_{u}\), but by default also on the network ambiguities z. That it is this combination that makes \(\tilde{z}_{u}\) integer estimable follows directly from the theorem by recognizing that the combinations of (49), i.e. \(\tilde{D}^\mathrm{{T}}=[-D_{m_{u}}^\mathrm{{T}}P_{u}(C^\mathrm{{T}}P)^{-1}C^\mathrm{{T}}, D_{m_{u}}^\mathrm{{T}}]\), satisfy the required condition \(\tilde{D}^\mathrm{{T}} \mathcal {Z} = [0, 0, 0, I_{m_{u}-1}]\).
In (49), we recognize that the network contribution to the integer-estimable user ambiguities is actually given by the network’s ambiguity \(\mathcal {S}\)-basis \(C^\mathrm{{T}}z\). Would one then, for instance, choose (35) as network \(\mathcal {S}\)-basis, the components of (49) would work out as \(\tilde{z}_{u}:= [z_{1u}^{pi}]\), with p the user-defined reference satellite and i running through the remaining \(m_{u}-1\) user-tracked satellites. This shows that the integer ambiguity resolution of the user ambiguity vector \(\tilde{z}_{u}\) is thus always one of double-differenced form (cf. Corollary 1). Hence, whether or not \(\tilde{z}\) would have been resolved as integer, the separate PPP-RTK ambiguity resolution of the integer-estimable single-receiver user ambiguities \(\tilde{z}_{u}\) is actually one of partial network ambiguity resolution.
8 Conclusions
As the undifferenced approach to GNSS requires the accounting for rank deficiencies, a proper understanding of the concept of estimability is essential, since different sets of estimable parameters exist, each with their own interpretation. In all studies until now, the standard concept of estimability was employed, which, as we have shown in this contribution, is too limited when dealing with rank-defect models that have parameters of which some are integer. Integer estimability is namely not guaranteed by merely asking of the estimable functions that they are integer. We therefore generalized the concept of estimability to integer estimability and determined the necessary and sufficient conditions that need to be satisfied for parameter functions to be integer estimable.
We showed that an independent set of ambiguity functions are integer estimable if and only if they are integer, nullify the incidence matrix and together with the \(\mathcal {S}\)-basis can be brought into the form of an admissible ambiguity transformation. These findings were then applied and worked out, first for ’all-in-view’ networks and then for the general case. It was hereby proven that functions of undifferenced ambiguities are estimable if and only if they are in double-differenced form and that spanning trees of the network ambiguity graph, when chosen as \(\mathcal {S}\)-basis, automatically produce integer-estimable ambiguity functions.
We also applied the concept of integer estimability and its rulings to PPP-RTK, thereby demonstrating that also the integer-estimable PPP-RTK user ambiguities are of double-differenced form and that PPP-RTK’s single-receiver ambiguity resolution should be seen as a special case of network ambiguity resolution.
References
Arnold SF (1981) The theory of linear models and multivariate analysis. Wiley, Hoboken
Baarda W (1973) S-transformations and criterion matrices. Technical report, Netherlands Geodetic Commission, Publ. on Geodesy, New Series, vol 5(1), Delft
Cocard M, Bourgon S, Kamali O, Collins P (2008) A systematic investigation of optimal carrier-phase combinations for modernized triple-frequency GPS. J Geod 82(9):555–564
Collins P, Bisnath S, Lahaye F, Heroux P (2010) Undifferenced GPS ambiguity resolution using the decoupled clock model and ambiguity datum fixing. Navigation 57(2):123–135
Cormen TH, Leiserson CE, Rivest LR, Stein C (2009) Introduction to algorithms, 3rd edn. MIT press, Cambridge
Coxeter HSM (1973) Regular polytopes. Dover Publications, New York
de Jonge PJ (1998) A processing strategy for the application of the GPS in networks. PhD thesis, Delft University of Technology, Publication on Geodesy, 46, Netherlands Geodetic Commission, Delft
Duong V, Harima K, Choy S, Laurichesse D, Rizos C (2019) An optimal linear combination model to accelerate PPP convergence using multi-frequency multi-GNSS measurements. GPS Solut 23(2):49
Feng Y (2008) GNSS three carrier ambiguity resolution using ionosphere-reduced virtual signals. J Geod 82(12):847–862
Ge M, Gendt G, Rothacher M, Shi C, Liu J (2008) Resolution of GPS carrier-phase ambiguities in precise point positioning (PPP) with daily observations. J Geod 82(7):389–399
Goad C (1985) Precise relative position determination using global positioning system carrier phase measurements in a nondifference mode. In: Proceedings of 1st international symposium on precies positioning with GPS, pp 347–356
Henderson HV, Pukelsheim F, Searle SR (1983) On the history of the Kronecker product. Linear Multilinear Algebra 14(2):113–120
Hofmann-Wellenhof B, Lichtenegger H, Wasle E (2008) GNSS: global navigation satellite systems: GPS, glonass, galileo, and more. Springer, New York
Khodabandeh A, Teunissen PJG (2017) On the impact of GNSS ambiguity resolution: geometry, ionosphere, time and biases. J Geod. https://doi.org/10.1007/s00190-017-1084-0
Koch KR (1999) Parameter estimation and hypothesis testing in linear models. Springer, Berlin
Kruskal JB (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc Am Math Soc 7(1):48–50
Lannes A, Gratton S (2009) GNSS networks in algebraic graph theory. J Glob Position Syst 8(1):53–75
Lannes A, Prieur JL (2013) Calibration of the clock-phase biases of GNSS networks: the closure-ambiguity approach. J Geod 87(8):709–731
Lannes A, Teunissen PJG (2011) GNSS algebraic structures. J Geod 85(5):273–290
Laurichesse D, Mercier F, Berthias J (2009a) Zero-difference integer ambiguity fixing on single frequency receivers. In: Proceedings of ION ITM-2009, Anaheim, pp 26–28
Laurichesse D, Mercier F, Berthias J, Broca P, Cerri L, CNES F (2009b) Integer ambiguity resolution on undifferenced GPS phase measurements and its application to PPP and satellite precise orbit determination. Navigation 56(2):135–149
Leick A (2004) GPS satellite surveying, 3rd edn. Wiley, Hoboken
Odijk D, Zhang B, Khodabandeh A, Odolinski R, Teunissen PJG (2015) On the estimability of parameters in undifferenced, uncombined GNSS network and PPP-RTK user models by means of S-system theory. J Geod 90(1):15–44
Prim RC (1957) Shortest connection networks and some generalizations. Bell Syst Tech J 36(6):1389–1401
Rao CR (1973) Linear statistical inference and its applications, 2nd edn. Wiley, Hoboken
Richert T, El-Sheimy N (2007) Optimal linear combinations of triple frequency carrier phase data from future global navigation satellite systems. GPS Solut 11(1):11–19
Schönemann E, Becker M, Springer T (2011) A new approach for GNSS analysis in a multi-GNSS and multi-signal environment. J Geod Sci 1(3):204–214
Shu L, Wang W, Ding R, Wei H (2017) Performance analysis of optimal combinations for triple-frequency BDS. Navig J Inst Navig 64(4):447–461
Teunissen PJG (1985) Generalized inverses, adjustment, the datum problem and S-transformations. In: Grafarend EW, Sanso F (eds) Optimization and design of geodetic networks. Springer, Berlin
Teunissen PJG (1995a) The invertible GPS ambiguity transformations. Manuscripta Geodaetia 20:489–497
Teunissen PJG (1995b) The least-squares ambiguity decorrelation adjustment: a method for fast GPS integer ambiguity estimation. J Geod 70(1–2):65–82
Teunissen PJG (1997) A canonical theory for short GPS baselines. Part I: the baseline precision. J Geod 71(6):320–336
Teunissen PJG, Khodabandeh A (2015) Review and principles of PPP-RTK methods. J Geod 89(3):217–240
Teunissen PJG, Kleusberg A (1998) GPS for geodesy, 2nd edn. Springer, Berlin
Teunissen PJG, Montenbruck O (eds) (2017) Springer handbook of global navigation satellite systems. Springer, Berlin
Teunissen PJG, Odijk D, Zhang B (2010) PPP-RTK: results of CORS network-based PPP with integer ambiguity resolution. J Aeronaut Astronaut Aviat 42(4):223–229
Vein R, Dale P (1999) Determinants and their applications in mathematical physics. Springer, New York
Wilson RJ (1996) Introduction to graph theory, 4th edn. Pearson Education, India
Zhang B, Chen Y, Yuan Y (2018) PPP-RTK based on undifferenced and uncombined observations: theoretical and practical aspects. J Geod. https://doi.org/10.1007/s00190-018-1220-5
Acknowledgements
The second author is the recipient of an Australian Research Council (ARC) Federation Fellowship (Project Number FF0883188). This support is gratefully acknowledged.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Author contribution statement
Both the authors contributed to the main results and writing of the paper.
Data availability statement
The GNSS data used in the paper are freely accessible and can be downloaded via the website http://saegnss2.curtin.edu.au/ldc/.
Appendices
Connected graphs and their incidence structure
This appendix gives a brief review of the basic elements of graph incidence matrices, see, e.g. (Coxeter 1973; Wilson 1996). It is intended to form the necessary background of the material presented.
1.1 Spanning trees of a graph
Connected graphs An undirected graph can be represented by the pair \({\mathcal {G}}=({\mathcal {V}},{\mathcal {E}})\), where \({\mathcal {V}}=\{1,\ldots ,n_v\}\) and \({\mathcal {E}}\subset \{(r,s)~|~r,s\in {\mathcal {V}}\}\) are the ‘vertex set’ and the ‘edge set’, respectively. Each edge, as a link between two vertices r and s of graph \({\mathcal {G}}\), is denoted by the unordered pair \((r,s)\in {\mathcal {E}}\). As the edge set \({\mathcal {E}}\) is not necessarily equal to \(\{(r,s)~|~r,s\in {\mathcal {V}}\}\), edges between any two vertices of \({\mathcal {G}}\) can be absent. If there is no edge between two vertices r and s, these vertices could still be linked to each other through a set of edges (i.e. a path). The graph \({\mathcal {G}}\) is said to be connected if every vertex is linked to all other vertices at least through one path. If any two vertices of the connected graph \({\mathcal {G}}\) are connected exactly through one path, then G is called a tree. Thus, a tree with \(n_v\) vertices contains \(n_v-1\) edges. Figure 5 shows examples of connected graphs compared to the one which is not connected.
Spanning subgraphs and trees. Graph \({\mathcal {T}}=({\mathcal {V}}_T,{\mathcal {E}}_T)\) is said to be a subgraph of \({\mathcal {G}}=({\mathcal {V}},{\mathcal {E}})\) if \({\mathcal {V}}_T\subset {\mathcal {V}}\) and \({\mathcal {E}}_T\subset {\mathcal {E}}\). Thus, the subgraph \({\mathcal {T}}\) contains no vertices or edges which are not in \({\mathcal {G}}\). The subgraph \({\mathcal {T}}\) is called a spanning subgraph of \({\mathcal {G}}\) if it contains every vertex of G, i.e. if \({\mathcal {V}}_T={\mathcal {V}}\). If the spanning subgraph \({\mathcal {T}}\) is a tree, then it is called a spanning tree.
1.2 The incidence matrix of a graph
Oriented incidence matrices. Let the graph \({\mathcal {G}}\), with vertices j (\(j=1,\ldots ,n_v\)), contain \(n_e\) edges indexed with i (\(i=1,\ldots ,n_e\)). The (edge–vertex) incidence matrix of \({\mathcal {G}}\) is then defined as \(\bar{P}=[p_{ij}]\), where
Thus, \(\bar{P}\) is an \(n_e\times n_v\) matrix. Each row (column) corresponds to an edge (a vertex). Every row of \(\bar{P}\) contains only two nonzero entries; one entry is \(-1\), and another is \(+1\). Whether an edge originates or terminates at an incident vertex is conventional, that is, the orientation of the edges can be chosen arbitrary. For instance, in Sect. 3, the orientation has been chosen so that the edges originate at ‘satellites’ and terminate at ‘receivers’.
Rank of incidence matrices The incidence matrices have row-sums equal to zero, i.e. \(\sum _{j=1}^{n_v}p_{ij}=0\)\((i=1,\ldots ,n_e)\). Thus, the vector of ones \(e_{n_v}\) nullifies \(\bar{P}\), i.e. \(\bar{P}e_{n_v}=0\). This implies that
Assume that there is another nonzero vector \(x=[x_1,\ldots ,x_{n_v}]^\mathrm{{T}}\) which also nullifies \(\bar{P}\). As every row of \(\bar{P}\) contains exactly one entry equal to \(-1\) and another equal to \(+1\), we have \(x_{k}-x_{j}=0\) for every edge (j, k). As a result, if there exists a path between two vertices r and s, then we have \(x_{r}=x_{s}\). Thus, for a connected graph we have \(x_{r}=x_{s}\) for any two vertices r and s, showing that vector x is just a scaled version of \(e_{n_v}\), i.e. \(\mathrm{rank}(\bar{P})= n_v-1\). If the graph is not connected, then the graph can be partitioned into multiple, say \(\kappa \), connected subgraphs. In that case, we have \(\mathrm{rank}(\bar{P})= n_v-\kappa \). Thus,
Reduced incidence matrices The reduced incidence matrix P, of size \(n_{e}\times (n_{v}-1)\), is structured by eliminating an arbitrary column of \(\bar{P}\). The rank of P is equal to that of \(\bar{P}\). To see this, let S be an \(n_{v}\times (n_{v}-1)\) matrix that is formed by eliminating an arbitrary column of the identity matrix \(I_{n_v}\). With \(P= \bar{P}S\), we have
The third equality follows from the equality \(\bar{P}e_{n_v}=0\), while the fourth (last) equality follows from the non-singularity of the square matrix \([S,e_{n_v}]\). Thus, the reduced incidence matrix of a connected graph is of full-column rank.
1.3 Kirchhoff’s matrix-tree theorem
Unimodularity of reduced incidence matrices The determinant of any square submatrix of P is either 0 or \(\pm 1\). Matrices with such a property are said to be totally unimodular. The proof is as follows. Let Q be an arbitrary square submatrix of P. Matrix Q may have row-sums equal to zero, or it may have a zero row. In both cases, \(\mathrm{det}(Q)=0\). Otherwise, Q has a row with only one nonzero entry (which must be \(\pm 1\)). Expanding the determinant of Q along that row gives \(\mathrm{det}(Q)=\pm \mathrm{det}(Q^\prime )\), where \(Q^\prime \) is a lower-dimension square submatrix of P. Likewise, \(\mathrm{det}(Q^\prime )=0\), or it has a row with only one nonzero entry equal to \(\pm 1\). By a repeated application of the above determinant expansion, it follows that the determinant of Q is either 0 or \(\pm 1\).
The total number of spanning trees in a graph Let P be the reduced incidence matrix of graph \({\mathcal {G}}\) with \(n_v\) vertices. Any square submatrix of P, of size \((n_{v}-1)\times (n_{v}-1)\), is itself a reduced incidence matrix of a spanning subgraph of \({\mathcal {G}}\). The corresponding spanning subgraph, say \({\mathcal {T}}\), has \((n_{v}-1)\) edges. Thus, \({\mathcal {T}}\) is a spanning tree, if it is connected. In that case, the subgraph \({\mathcal {T}}\) corresponds to a nonsingular submatrix with a determinant equal to \(\pm 1\) (cf. 52 and 53). Otherwise, \({\mathcal {T}}\) is not connected, i.e. the corresponding submatrix has a determinant equal to zero. These submatrices do therefore enable one to compute the total number of spanning trees in graph \({\mathcal {G}}\). Let such submatrices be given by \(Q_i\) (\(i\in \mathcal {C}\)), where the set \(\mathcal {C}\) contains all \((n_{v}\!-\!1)\)-element subsets of \(\{1,\ldots ,n_e\}\). The total number of spanning trees in graph \({\mathcal {G}}\) can then be given by
The second equality follows from the identity \(\mathrm{det}(Q_i\mathrm{{T}})=\mathrm{det}(Q_i)\). The third (last) equality follows from a direct application of the Cauchy–Binet determinant identity, see, e.g. (Vein and Dale 1999). The result presented in (54) is known as the matrix-tree theorem.
Supplementary proofs
Proof of the Theorem
(\(\Rightarrow \)) If \(\tilde{D}^\mathrm{{T}}\mathcal {Z}=[0, I_{\tilde{q}}]\), with \(\mathcal {Z}, \mathcal {Z}^{-1} \in \mathbb {Z}^{q \times q}\), then for any integer \(\tilde{z}\) a corresponding integer solution \(u=\mathcal {Z}^{-1}z \in \mathbb {Z}^{q}\) of \(\tilde{z}=(\tilde{D}^\mathrm{{T}}\mathcal {Z})u\) exists and thus also of \(\tilde{z}=\tilde{D}^\mathrm{{T}}z\). (\(\Leftarrow \)) Let \(\tilde{D}^\mathrm{{T}}\mathcal {Z}=[0, H]\) be the Hermite normal form of \(\tilde{D}^\mathrm{{T}}\). Then \(H^{-1}\tilde{z}=[0,I_{\tilde{q}}]Z^{-1}z\), from which it follows that an integer solution z exists for every integer \(\tilde{z}\) only if \(H^{-1}\) is integer, which by virtue of the structure of the Hermite normal form implies that \(H=I_{\tilde{q}}\). \(\square \)
Proof of (36)
As \(\mathrm{det}([P,R])=\pm 1\), we have \(1= \mathrm{det}([P,R]^\mathrm{{T}}[P,R])\) and therefore with an application of the determinant factorization rule (Koch 1999)
where \(Q = R\mathrm{{T}}[I-P(P^\mathrm{{T}}P)^{-1}P^\mathrm{{T}}]R\). Using the projector identity \(D(D^\mathrm{{T}}D)^{-1}D^\mathrm{{T}}=I-P(P^\mathrm{{T}}\!P)^{-1}P^\mathrm{{T}}\) (Teunissen 1985) and the fact that \(D^\mathrm{{T}}[P,R]=[0,I]\), the result follows. \(\square \)
Proof of the identity\( \mathrm{det}(D_n^\mathrm{{T}}D_n)=n\)in (37). From (25), it follows that \(D_n^\mathrm{{T}}D_n=I_{n-1}+e_{n-1}e_{n-1}^\mathrm{{T}}\). An application of the determinant factorization rule (Koch 1999) gives
as \(e_{n-1}^\mathrm{{T}}e_{n-1}=n-1\). \(\square \)
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Khodabandeh, A., Teunissen, P.J.G. Integer estimability in GNSS networks. J Geod 93, 1805–1819 (2019). https://doi.org/10.1007/s00190-019-01282-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00190-019-01282-6