Abstract
An Optimal Method for Estimating GPS Ambiguities (OMEGA) that enables very high performance and computational efficiency has been developed and demonstrated. This method employs two search space reduction processes -a scaling and a screening process -that are related to the search space transformation and the ambiguity candidate filtering in multi-search levels. To obtain the highest efficiency, an optimization procedure, which determines the parameters to minimize the number of candidates under given conditions, is implemented in closed-form before the search-verification step. The method is essentially based on the least-squares-approach originally proposed by Hatch but uses a modified and more efficient process. Two improved algorithms are introduced in this paper. First, an alternative algorithm for the spectral decomposition, which reduces the dimension of the residuals vector to its degrees of freedom, is given in closed form. This algorithm is implemented in the computational step of the quadratic form of the residuals in order to increase computational efficiency. Second, an efficient error model for the threshold of the filter equation that is used to derive the search space scaling process is given. This error model shows two advantages: 1) it bounds noise signals of the filter equation; 2) it gives efficient thresholds so that the scaling effects for the search space can be increased.
Introduction
In navigation and surveying systems using GPS carrier phase data, the performance of ambiguity resolution and computational efficiency are of great concern. These capabilities are often traded off in designing the system. One possible way to overcome the trade-off loss is to reduce the number of ambiguity candidates before or at the searchverification step. The search space transformation (Abidin, 1993; Teunissen, 1994; Martin-Neira et al., 1995) and ambiguity candidate filtering in multi-search levels (Chen and Lachapelle, 1995; Teunissen, 1997) are effective techniques for that purpose.
When we use a process similar to the least-squares-approach of Hatch (1990) at the search-verification step, it is possible to implement optimization procedures reducing the number of candidates before implementing the step. We showed that this could be achieved using the design matrix of the linearized double-difference observables in Kim and Langley (1999) . These optimization procedures include two search-space reduction processes (i.e., a scaling and a screening process) and two-step optimization processes -a global optimization to find a matrix S minimizing the total search space volume and a local optimization to find a reordered matrix S minimizing the total search space volume out of all possible combinations of S, where the matrix S is computed using the design matrix.
To increase computational efficiency, further attention has been given to the quadratic form of the residuals and to error models for the thresholds of the filter equation. The quadratic form of the residuals is generally used for the ambiguity acceptance test and is the practical computational part in the ambiguity search-verification step. Therefore, we need to decrease computational burden using a more efficient computational algorithm. A significant reason for needing a more efficient error model for the filter thresholds is that the filter thresholds are related to a magnification factor of the scaling process. The more efficient the error model, the greater the scaling effect.
The GPS Observables
To simplify discussions, we will assume that the float estimates of the ambiguities and their error models are given. For the double-difference observables recorded on short baselines, the satellite and the receiver clock biases are removed, and the residual atmospheric effects are negligible. Ignoring multipath, we have
where l is the nx1 initial misclosure vector of the difference between the double-difference observations and their estimates; n is the number of the double-difference observations; x is the 3x1 vector of the unknown remote (rover) station position components; A is the design matrix for the unknown position; N is the nx1 vector of ambiguity parameters; e is the nx1 vector of the double-difference observation noise; [] E g and [] Cov g represent the mathematical expectation and the variance-covariance operators, respectively.
The Modified Least-Squares Approach
Using the same terminology as Hatch (1990) , we outline the modified process for the least-squares approach in Table 1 . In the computational equations, the subscripts "p" and "s" represent the primary and the secondary group of satellites; and [] round g is the rounding-to-the-nearest-integer operator. When compared with the original least-squares approach, the modified approach gives exactly the same residuals. To prove the equivalence of both approaches, we will define:
Then, we have following equality:
Subtracting the residuals for both approaches and applying Eq. (3) gives
where subscripts "o" and "m" represent the original and modified approaches. When we compute the residuals using the modified approach in Table 1 , the only variable parameter is the secondary innovations vector. In accord with the least-squares principle, the optimal estimator for the secondary innovations vector is given as:
We can recognize that the optimal estimator is independent of the search-verification step, since it is derived from the design matrix and the initial misclosure vector for the primary group. These parameters are constant in a snapshot (i.e., single epoch) approach, such as the least-squares approach. One natural idea to utilize the optimal estimator is to define a filter equation as: 
Using the filter equation and a certain threshold vector τ τ, we can define a filter as:
where
The dimension of n-3 for the filter equation and threshold vector comes from the dimension difference between the (ndimensional) double-difference observations and the (3-dimensional) unknown remote station position components.
Quadratic Form of the Residuals
For the ambiguity acceptance test, we have to compute the quadratic form of the residuals for all ambiguity candidates in the ambiguity search-verification step. Two approaches can be considered for decreasing computational burden -search space (or ambiguity candidates) reduction and computational algorithm improvement. We will focus on the computational algorithm for the quadratic form of the residuals in this paper. Using the computational equation for the residuals in Table 1 , the quadratic form of the residuals is given as:
where
Spectral decomposition for a singular symmetric matrix Σ Σ is expressed as (Basilevsky, 1983) :
where the nx(n-3) matrix E contains the nx1 latent vectors (eigenvectors) 12n-3 E,E,,E L and the (n-3)x(n-3) diagonal matrix Λ Λ possesses n-3 nonzero latent roots (eigenvalues)
where
We can find an example of this algorithm in Martin-Neira et al. (1995) . An alternative algorithm for the spectral decomposition approach can be derived using the following relational equations. From Eq. (4), rewriting the residuals gives ( ) .
Therefore, using the partitioned matrices of =− * GIAA , we have two relational equations from Eq. (14) (15) and (16) into (17) gives
where
Furthermore, the following equality can be proved:
where Vss Q is a partitioned matrix of the variance-covariance of v, v Q . To compare the computational efficiency of different algorithms, we outline three algorithms for the computation of the quadratic form of the residuals in Table 2 . The computational algorithms A1 and A2 represent a normal and a spectral decomposition approach. The computational algorithm A3 is an alternative approach for the computational algorithm A2. The computational steps are separated into three parts for clarity -common, external, and internal. The external part is computed before the ambiguity search-verification step. On the other hand, the internal part is computed in the search loop. Therefore, the computational efficiency of the internal part is usually of great concern. 
Error Model for the Filter Threshold
In general, the threshold vector τ τ in Eq. (7) can be derived from the quadratic form of the filter equation as:
where w Q is the variance-covariance matrix of w and c is a positive constant which can be selected based on the probability distribution of w. Therefore, we can determine confidence intervals bounding a confidence ellipsoid which is formed by choosing c at a certain confidence level. Then, one simple way to set the thresholds is ,1,2,,
where wi σ is the square root of the i th diagonal element in w Q . It should be noted that the confidence level of the thresholds is different from that of the confidence ellipsoid.
(When we mention a confidence level in this paper, it refers to the confidence ellipsoid.) However, we can recognize in Eq. (6) that it is not easy to establish correctly the variancecovariance matrix w Q and the probability distribution of w. For this reason, we have used an alternative approach for the quadratic form of the filter equation. In general, the ellipsoidal region in 3 n − ¡ centered on the estimator x of a certain vector x can be expressed as (Giri, 1977) :
where x Q is the variance-covariance matrix of x . The family of ellipsoids obtained by varying c (c>0) has the same center x , their shapes and orientation are determined by x Q , and their sizes are determined by c. It should be noted that the positive constant c does not have probabilistic sense unless the probability distribution of x is known. From Eq. (23), the thresholds are given as:
where xi σ is the square root of the i th diagonal element in x Q . One condition required in this approach is that the estimator x should be the unbiased estimator of x; then, we can get different thresholds according to the weighting scheme of x Q . Three cases from (a) to (c) in Table 3 show the unbiased estimators of x and their error models. Because both x and x are probabilistic variables, the condition of unbiasedness becomes
For each case, the condition of unbiasedness can be proved if the following equality holds (more details in Teunissen (1998) 
where
Three error models for the filter thresholds (i.e., the error models from (a) to (c)) were tested and discussed in Kim and Langley (1999) . A rigorous error model, which is related to deciding the value of the positive constant c in a probabilistic sense, can be derived from Eqs. (18) and (21). From these two equations, we can express a correct error model of the filter equation w as:
Assuming that the double-difference observation noise e in Eq. (1) where α is the level of significance. Therefore, we can determine the positive constant c with a certain confidence level in accord with α. Table 3 shows the summary of the error models for the filter thresholds. In each error model, the variance-covariance matrices with subscripts are the submatrices partitioned from the variance-covariance matrix of the double-difference observations in Eq. (1). 
Results
To test the efficiency of the computational algorithms for the quadratic form of the residuals and the performance of the error models for the filter thresholds, we processed some of the test data recorded at one reference station in the Canadian Coast Guard (CCG) DGPS and OTF network and that recorded simultaneously on board a hydrographic sounding ship at Trois-Rivières, on the St. Lawrence River, 130 km upstream (southwest) of Québec City, on 30 September 1998 (Fig. 1) . The data set contains both L1 and L2 observations recorded at a one second sampling interval for two hours in kinematic mode. Baseline length between the reference station and hydrographic sounding ship was about 40 km.
The results of our analyses are presented in two parts: the floating point operation count (FLOPS) test of the computational algorithms for the quadratic form of the residuals; and the performance of the error models for the filter thresholds.
Computational Algorithm Efficiency
Using each computational algorithm for the quadratic form of the residuals in Table 2 , the FLOPS test was conducted to compare the efficiency of the algorithms. (Although this test cannot give us a realistic computation time, we can see the relative efficiencies of the algorithms.) Table 4 shows the test results. Test conditions were given as: 1) three-level search loops were built; 2) the search range for each search level was given as 2 m, therefore, twenty-one candidates were given for each search level; 3) seven satellites were used. The normal computational algorithm A1 gave the worst computational efficiency and the alternative algorithm A3 for the spectral decomposition approach gave the best results. Compared with the normal algorithm A1, the efficiency of the spectral decomposition algorithm A2 was improved by about 62%. In the case of the alternative algorithm A3, the efficiency was improved by about 64%. In both the external and internal computation parts, the alternative algorithm A3 was superior to the spectral decomposition algorithm A2. We have obtained consistent results under different test conditions. We can say therefore, that the alternative algorithm A3 is the most efficient algorithm of the three algorithms tested for computing the quadratic form of the residuals no matter which test conditions are given.
Error Model Performance
To compare the performance of the error models, the filter thresholds were computed using Eqs. (22) and (24) for each error model in Table 3 . The positive constant value c was determined from the chi-squared distribution at the 95% confidence level with n-3 degrees of freedom (i.e., we assumed that the double-difference observation noise follows the normal distribution). As was mentioned previously, however, this choice of c cannot guarantee the same confidence level to the error models from (a) to (c) in Table 3 , because these error models are not based on a rigorouslydefined probability distribution. Even though this limitation exists, we considered, as a matter of convenience, that the positive constant c has the same confidence level for all error models in our investigations. Fig. 2 shows the overall performance of the error models, i.e., how well the filter thresholds (solid lines) bound the values of the filter equation (dots). To investigate the performance of the error models in detail, we plotted the filter thresholds for each error model and for the double-difference time series of PRN 9 and 8 separately in Fig. 3 . We need in general an error model that protects all the values of the filter equation for true ambiguities in the given confidence level, which at the same time is also efficient. The third error model satisfies these criteria as shown by the examples in Fig. 3 . On the other hand, it is evident that the first error model does not satisfy these criteria. Furthermore, the first error model did not react well to the noise level of the filter equation. For the second and fourth error models, our investigations have shown that both of these error models have similar characteristics (sometimes, almost identical). In fact, the equation for the fourth error model can be developed in a similar form to that of the second error model in Table 3 . According to the partitioned design matrices, both error models would be almost identical. The performance of these error models is not much different from that of the third error model as shown by the examples in Fig. 3 .
Conclusions
The work reported in this paper has been a follow-on study stemming from our previous work as reported in Kim and Langley (1999) . Two aspects -error models for the filter thresholds and computational algorithms in the searchverification step -have been investigated in detail. For the computational algorithms of the quadratic form of the residuals in Table 2 , we found that the alternative algorithm A3 for the spectral decomposition is the most efficient. Regarding the error models for the filter thresholds in Table 3 , we found that three of the four error models performed well, i.e., the filter thresholds bounded almost all the noise signals of the filter equation. Only the first of the four performed poorly. We also found that the second and fourth error models have similar behavior. However, because of the meaning of the positive constant c (i.e., for robustness, it should be determined not arbitrarily but in a probabilistic sense), we have considered the fourth error model as the most rigorous approach in our investigations.
Teunissen, P. J. G., A canonical theory for short GPS baselines. Part III: The geometry of the ambiguity search space, Journal of Geodesy, Vol. 71, No. 8, pp. 486-501, 1997 .
Teunissen, P. J. G., A class of unbiased integer GPS ambiguity estimators, Artificial Satellites, Vol. 33, No. 1, pp. 3-10, 1998 . Table 3 .

{'paper_id': '13395876', 'title': 'A search space optimization technique for improving ambiguity resolution and computational efficiency', 's2_url': 'https://api.semanticscholar.org/CorpusID:13395876', 'source': 'S2ORC'}