A computational complexity analysis of Tienstra’s solution to equality-constrained adjustment
Tóm tắt
Tienstra’s method was developed to solve parameter adjustment with linear equality constraints, which has been otherwise often carried out by directly applying the conventional (or standard) method of Lagrange multipliers to quadratic optimization problems with a positive definite matrix. We analyze the computational complexity of the celebrated Tienstra’s method and compare it with that of the method of Lagrange multipliers. We show that Tienstra’s method is not only statistically elegant but also interestingly of significant computational advantage over the method of Lagrange multipliers to solve weighted least squares adjustment with linear equality constraints, with the saving of computational cost by a minimum of about 38% to a maximum of 100%. Tienstra’s method can be very important for large scale problems of adjustment and inversion with linear equality constraints.
Tài liệu tham khảo
Baarda W., 1957. Some remarks on the computation and adjustment of large systems of geodetic triangulation. Bull. Geod., 43, 20–49.
Baarda W., 1967. Statistical Concepts in Geodesy. Publications on Geodesy, Vol. 2, Nr. 4. Netherlands Geodetic Commission, Delft, The Netherlands.
Baarda W., 1968. A Testing Procedure for Use in Geodetic Networks. Publications on Geodesy, Vol. 2, Nr. 5. Netherlands Geodetic Commission, Delft, The Netherlands.
Baarda W., 1973. S-Transformations and Criterion Matrices. Technical Report. Publ. Geodesy, New Series, 5(1). Netherlands Geodetic Commission, Delft, The Netherlands (http://www.ncgeo.nl/phocadownload/18Baarda.pdf).
Baarda W. and Alberta J.E., 1962. The connection of geodetic adjustment procedures with methods of mathematical statistics. Bull. Geod., 66, 325–345.
Blaha G., 1984. Tensor structure applied to the least-squares method, revisited. Bull. Geod., 58, 1–30.
Cui X.Z., Yu Z.C., Tao B.Z. and Liu D.J., 1982. Generalized adjustment of Observations. Publishing House of Surveying and Mapping, Beijing, China (in Chinese).
Gaposchkin E.M. and Lambeck K., 1971. Earth’s gravity field to the sixteenth degree and station coordinates from satellite and terrestrial data. J. Geophys. Res., 76, 4855–4883.
Golub G.H. and van Loan C.F., 1996. Matrix Computations. 3rd Edition. Johns Hopkins University Press, Baltimore, MD.
Lugoe F.N., 1990. Rigorous mathematical models for the denslfication and integration of geodetic networks. Bull. Geod., 64, 219–229.
Koch K.R., 1990. Bayesian Inference with Geodetic Applications. Springer-Verlag, Berlin, Germany.
Koch K.R., 1999. Parameter Estimation and Hypothesis Testing in Linear Models. 2nd Edition. Springer-Verlag, Berlin, Germany.
Lakshmikantham V. and Sen S.K., 2005. Computational Error and Complexity in Science and Engineering. Elsevier, London, U.K.
Moritz H., 1966. An explanation of the “systematic” effect of accidental errors in aerial triangulation. Photogrametria, 17, 18–22.
Morton K.W. and Mayers D.F., 1994. Numerical Solution of Partial Differential Equations. Cambridge University Press, Cambridge, U.K.
Porta J.M. and Thomas F., 2009. Concise proof of Tienstra’s formula. J. Surv. Eng., 135, 170–172.
Teunissen P.J.G., 1985. The Concept of Geodetic Inverse Linear Mapping and Non-Linear Adjustment. Publ. Geodesy, New Series, 8(1). Netherlands Geodetic Commission, Delft, The Netherlands.
Teunissen P.J.G., 1994. Least-squares estimation of the integer GPS ambiguities. LGR Series Publications of the Delft Geodetic Computing Centre, No. 6, Delft University Press, Delft University of Technology, Delft, The Netherlands, 59–74 (http://www.citg.tudelft.nl/fileadmin/Faculteit/CiTG/Over_de_faculteit/Afdelingen/Afdeling_Geoscience_and_Remote_ Sensing/pubs/PT_BEIJING93.PDF).
Teunissen P.J.G., 2000. Adjustment Theory: an Introduction. VSSD Publisher, Delft, The Netherlands.
Teunissen P.J.G. and Khodabandeh A., 2013. BLUE, BLUP and the Kalman filter: some new results. J. Geodesy, 87, 461–473.
Tienstra J.M., 1933. Nets of triangles consisting of points with circular error-curves. Proc. Koninklijke Akad Wetenschappen Amsterdam, 36, 656–665.
Tienstra J.M., 1947. An extension of the technique of the methods of least squares to correlated observations. Bull. Geod., 51, 301–335.
Tienstra J.M., 1948. The foundation of the calculus of observations and the method of least squares. Bull. Geod., 52, 289–306.
Tienstra J.M., 1956. Theory of the Adjustment of Normally Distributed Observations. Uitgeverij Argus, Amsterdam, The Netherlands.
Vandenberghe L., 2016. Constarined Least Squares. Lecture Notes. http://www.seas.ucla.edu/~vandenbe/133A/lectures/cls.pdf.
Velsink H., 2016. Time series analysis of 3D coordinates using nonstochastic observations. J. Appl. Geod., 10, 5–16.
Wu J.C. and Liu D.J., 1985. Adjustment of the Control Network. Publishing House of Surveying and Mapping, Beijing, China (in Chinese).
Xu P.L., 1993. Multi-objective second order optimization and criterion matrix design. Boll. Geod. Sci. Affini, 52, 305–323.
Xu P.L., 1995. Testing the hypotheses of non-estimable functions in free net adjustment models. Manuscr. Geod., 20, 73–81.
Xu P.L., 1997. A general solution in nonlinear rank-defect geodetic models. Boll. Geod. Sci. Affini, 56, 1–25.
Xu P.L., 2005. Sign-constrained robust least squares, subjective breakdown point and the effect of weights of observations on robustness. J. Geodesy, 79, 146–159.
Xu P.L., Cannon E. and Lachapelle G., 1995. Mixed Integer Programming for the Resolution of GPS Carrier Phase Ambiguities. presented at IUGG Assembly, Boulder, July 2-14, 1995 (https://pdfs.semanticscholar.org/89f3/9bdf71e8dc57308bf1793db5b0de679b49dc.pdf).
Xu P.L., Shi Y., Peng J.H., Liu J.N. and Shi C., 2013. Adjustment of geodetic measurements with mixed multiplicative and additive random errors. J. Geodesy, 87, 629–643.
Yang Y.X., Gao W. and Zhang X., 2010. Robust Kalman filtering with constraints: a case study for integrated navigation. J. Geodesy, 84, 373–381.