Enhancement of Computational Efficiency for Weighted Total Least Squares
Publication: Journal of Surveying Engineering
Volume 147, Issue 4
Abstract
Weighted total least-squares (WTLS) adjustment is a rigorous method used for estimating parameters in the errors-in-variables (EIV) model. However, its computational efficiency is limited due to the large number of matrix operations involved, which are extremely time-consuming, particularly when processing large data sets. Based on the structural characteristics of the EIV model, the design matrix is divided into a constant matrix and a random matrix. Then the EIV model is rewritten as a general structured model and reformulate it as an efficient WTLS algorithm, which only attaches a weight matrix to the random matrix to reduce the size of the matrices involved in the iterative process. In addition, the proposed algorithm does not reestimate the random matrix in each iteration. All of this helps to improve computational efficiency. Numerical results confirm that the proposed algorithm can obtain the same accuracy as other existing improved algorithms, but using the same hardware, which requires significantly less time and memory.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
The data and models generated or used during the study are available from Jianmin Wang by request. The code is available from Qiongyue Zhang or Wenshuai Yan by request.
Acknowledgments
This work is partially supported by the Opening Fund of the State Key Laboratory of Geohazard Prevention and Geoenvironmental Protection (Chengdu University of Technology), China (SKLGP2020K027), and the Natural Science Foundation of Shanxi Province, China (201901D111048). The authors also thank the anonymous reviewers for their constructive comments.
References
Adcock, R. 1877. “Note on the method of least squares.” Analyst 4 (6): 183–184.
Ahmad, T., R. B. Lyngdoh, A. S. Sahadevan, S. Raha, P. K. Gupta, and A. Misra. 2020. “Four-directional spatial regularization for sparse hyperspectral unmixing.” J. Appl. Remote Sensing 14 (4): 046511. https://doi.org/10.1117/1.JRS.14.046511.
Akyilmaz, O. 2007. “Total least squares solution of coordinate transformation.” Surv. Rev. 39 (303): 68–80. https://doi.org/10.1179/003962607X165005.
Amiri-Simkooei, A. R., F. Zangeneh-Nejad, J. Asgari, and S. Jazaeri. 2014. “Estimation of straight line parameters with fully correlated coordinates.” Measurement 48 (1): 378–386. https://doi.org/10.1016/j.measurement.2013.11.005.
Cadzow, J. A. 1988. “Signal enhancement—A composite property mapping algorithm.” IEEE Trans. Acoust. Speech Signal Process. 36 (1): 49–62. https://doi.org/10.1109/29.1488.
Carroll, R., D. Ruppert, L. Stefanski, and C. Crainiceanu. 2006. Measurement error in nonlinear models—A modern perspective. 2nd ed. New York: Chapman and Hall.
Chang, G. 2015. “On least-squares solution to 3D similarity transformation problem under Gauss–Helmert model.” J. Geod. 89 (6): 573–576. https://doi.org/10.1007/s00190-015-0799-z.
Dastgahian, M. S., M. N. Tehrani, and H. Khoshbin. 2018. “The off-grid frequency selective millimeter wave channel estimation.” Int. J. Commun. Syst. 31 (15): e3770. https://doi.org/10.1002/dac.3770.
Deming, W. E. 1931. “The application of least squares.” Philos. Mag. Ser. 11 (68): 146–158. https://doi.org/10.1080/14786443109461671.
Deming, W. E. 1934. “On the application of least squares—II.” Philos. Mag. Ser. 17 (114): 804–829. https://doi.org/10.1080/14786443409462437.
De Moor, B. 1993. “Structured total least squares and approximation problems.” Linear Algebr. Appl. 188–189 (Jul–Aug): 163–205. https://doi.org/10.1016/0024-3795(93)90468-4.
Fang, X. 2013. “Weighted total least squares: Necessary and sufficient conditions, fixed and random parameters.” J. Geod. 87 (8): 733–749. https://doi.org/10.1007/s00190-013-0643-2.
Fang, X. 2015. “Weighted total least-squares with constraints: A universal formula for geodetic symmetrical transformations.” J. Geod. 89 (5): 459–469. https://doi.org/10.1007/s00190-015-0790-8.
Felus, Y., and B. Schaffrin. 2005. “Performing similarity transformations using the errors-in-variables model.” In Proc., ASPRS Annual Conf. Baltimore: American Society for Photogrammetry and Remote Sensing.
Felus, Y. A. 2004. “Application of total least squares for spatial point process analysis.” J. Surv. Eng. 130 (3): 126–133. https://doi.org/10.1061/(ASCE)0733-9453(2004)130:3(126).
Felus, Y. A., and R. C. Burtch. 2009. “On symmetrical three-dimensional datum conversion.” GPS Solutions 13 (1): 65–74. https://doi.org/10.1007/s10291-008-0100-5.
Fuller, W. 1987. Measurement error models. New York: Wiley Interscience.
Golub, G. H., and C. F. van Loan. 1980. “An analysis of the total least squares problem.” SIAM J. Numer. Anal. 17 (6): 883–893. https://doi.org/10.1137/0717073.
Guan, Y., S. Liu, S. Zhou, and L. Zhang. 2011. “Robust plane fitting of point clouds based on TLS.” [In Chinese.] J. Geod. Geodyn. 31 (5): 80–83.
Han, J. 2010. “Noniterative approach for solving the indirect problems of linear reference frame transformations.” J. Surv. Eng. 136 (4): 150–156. https://doi.org/10.1061/(ASCE)SU.1943-5428.0000026.
Jazaeri, S., A. R. Amiri-Simkooei, and M. A. Sharifi. 2014. “Iterative algorithm for weighted total least squares adjustment.” Surv. Rev. 46 (334): 19–27. https://doi.org/10.1179/1752270613Y.0000000052.
Kummell, C. H. 1879. “Reduction of observation equations which contain more than one observed quantity.” Analyst 6 (4): 97–105. https://doi.org/10.2307/2635646.
Lei, Z., G. Tianqi, Z. Ji, J. Shijun, S. Qingzhou, and H. Ming. 2014. “An adaptive moving total least squares method for curve fitting.” Measurement 49 (Mar): 107–112. https://doi.org/10.1016/j.measurement.2013.11.050.
Li, J., W. Gao, J. Qian, Q. Guo, J. Xi, and C. H. Ritz. 2019. “Robust entangled-photon ghost imaging with compressive sensing.” Sensors (Switzerland) 19 (1): 1–11. https://doi.org/10.3390/s19010192.
Mahboub, V. 2012. “On weighted total least-squares for geodetic transformations.” J. Geod. 86 (5): 359–367. https://doi.org/10.1007/s00190-011-0524-5.
Mahboub, V., and M. A. Sharifi. 2013. “On weighted total least-squares with linear and quadratic constraints.” J. Geod. 87 (3): 279–286. https://doi.org/10.1007/s00190-012-0598-8.
Markovsky, I., and S. Van Huffel. 2005. “High-performance numerical algorithms and software for structured total least squares.” J. Comput. Appl. Math. 180 (2): 311–331. https://doi.org/10.1016/j.cam.2004.11.003.
Markovsky, I., and S. Van Huffel. 2007. “Overview of total least-squares methods.” Signal Process. 87 (10): 2283–2302. https://doi.org/10.1016/j.sigpro.2007.04.004.
Mastronardi, N., P. Lemmerling, and S. Van Huffel. 2000. “Fast structured total least squares algorithm for solving the basic deconvolution problem.” SIAM J. Matrix Anal. Appl. 22 (2): 533–553. https://doi.org/10.1137/S0895479898345813.
Menniti, S., E. Castagna, and T. Mazza. 2013. “Estimating the global density of graphs by a sparseness index.” Appl. Math. Comput. 224 (Nov): 346–357. https://doi.org/10.1016/j.amc.2013.08.040.
Neitzel, F. 2010. “Generalization of total least-squares on example of unweighted and weighted 2D similarity transformation.” J. Geod. 84 (12): 751–762. https://doi.org/10.1007/s00190-010-0408-0.
Neri, F., G. Saitta, and S. Chiofalo. 1989. “An accurate and straightforward approach to line regression analysis of error-affected experimental data.” J. Phys. E: Sci. Instrum. 22 (4): 215–217. https://doi.org/10.1088/0022-3735/22/4/002.
Pichel, J. C., F. F. Rivera, M. Fernández, and A. Rodríguez. 2012. “Optimization of sparse matrix–vector multiplication using reordering techniques on GPUs.” Microprocess. Microsyst. 36 (2): 65–77. https://doi.org/10.1016/j.micpro.2011.05.005.
Pissanetzky, S. 1984. Sparse matrix technology. London: Academic Press.
Rahman, T., and J. Valdman. 2013. “Fast MATLAB assembly of FEM matrices in 2D and 3D: Nodal elements.” Appl. Math. Comput. 219 (13): 7151–7158. https://doi.org/10.1016/j.amc.2011.08.043.
Rajkumar, D. G. 2017. “Linear cryptanalysis of substitution ciphers using particle swarm optimization.” Orient. Comput. Sci. Technol. 10 (3): 580–584. https://doi.org/10.13005/ojcst/10.03.04.
Ran, L., R. Xie, Z. Liu, L. Zhang, T. Li, and J. Wang. 2018. “Simultaneous range and cross-range variant phase error estimation and compensation for highly squinted SAR imaging.” IEEE Trans. Geosci. Remote Sens. 56 (8): 4448–4463. https://doi.org/10.1109/TGRS.2018.2820102.
Rodriguez, J. S., G. Hackebeil, J. Siirola, V. M. Zavala, and C. D. Laird. 1994. Large scale optimization, edited by W. W. Hager, D. W. Hearn, and P. M. Pardalos. Boston: Springer.
Rosen, J. B., H. Park, and J. Glick. 1996. “Total least norm formulation and solution for structured problems.” SIAM J. Matrix Anal. Appl. 17 (1): 110–126. https://doi.org/10.1137/S0895479893258802.
Schaffrin, B., F. Neitzel, S. Uzun, and V. Mahboub. 2012. “Modifying Cadzow’s algorithm to generate the optimal TLS-solution for the structured EIV-Model of a similarity transformation.” J. Geodetic Sci. 2 (2): 98–106. https://doi.org/10.2478/v10156-011-0028-5.
Schaffrin, B., and A. Wieser. 2008. “On weighted total least-squares adjustment for linear regression.” J. Geod. 82 (7): 415–421. https://doi.org/10.1007/s00190-007-0190-9.
Schaffrin, B., and A. Wieser. 2011. “Total least-squares adjustment of condition equations.” Stud. Geophys. Geod. 55 (3): 529–536. https://doi.org/10.1007/s11200-011-0032-3.
Shen, Y., B. Li, and Y. Chen. 2011. “An iterative solution of weighted total least-squares adjustment.” J. Geod. 85 (4): 229–238. https://doi.org/10.1007/s00190-010-0431-1.
Shi, Y., P. Xu, J. Liu, and C. Shi. 2015. “Alternative formulae for parameter estimation in partial errors-in-variables models.” J. Geod. 89 (1): 13–16. https://doi.org/10.1007/s00190-014-0756-2.
Tong, X., Y. Jin, and L. Li. 2011. “An improved weighted total least squares method with applications in linear fitting and coordinate transformation.” J. Surv. Eng. 137 (4): 120–128. https://doi.org/10.1061/(ASCE)SU.1943-5428.0000055.
Van Huffel, S., P. Haesun, and J. B. Rosen. 1996. “Formulation and solution of structured total least norm problems for parameter estimation.” IEEE Trans. Signal Process. 44 (10): 2464–2474. https://doi.org/10.1109/78.539031.
Van Huffel, S., and J. Vandewalle. 1991. The total least squares problem: Computational aspects and analysis. Philadelphia, PA: Society for Industrial and Applied Mathematics.
Wang, J., J. Zhao, Z. Liu, and Z. Kang. 2021. “Location and estimation of multiple outliers in weighted total least squares.” Measurement 181 (Aug): 109591. https://doi.org/10.1016/j.measurement.2021.109591.
Wang, L., G. Wen, and Y. Zhao. 2019. “Virtual observation method and precision estimation for Ill-posed partial EIV model.” J. Surv. Eng. 145 (4): 04019010. https://doi.org/10.1061/(ASCE)SU.1943-5428.0000282.
Wang, L., and G. Xu. 2016. “Variance component estimation for partial errors-in-variables models.” Stud. Geophys. Geod. 60 (1): 35–55. https://doi.org/10.1007/s11200-014-0975-2.
Wang, L., H. Yu, and X. Cheng. 2016. “An algorithm for partial EIV model.” [In Chinese.] Acta Geod. Cartographica Sin. 45 (1): 22–29.
Wang, Q., Y. Fang, W. Wang, M. Wu, R. Wang, and Y. Fang. 2013. “Research on automatic reading recognition of index instruments based on computer vision.” In Proc., 2013 3rd Int. Conf. on Computer Science and Network Technology, 10–13. New York: IEEE.
Xu, P. 2016. “The effect of errors-in-variables on variance component estimation.” J. Geod. 90 (8): 681–701. https://doi.org/10.1007/s00190-016-0902-0.
Xu, P. 2019. “Improving the weighted least squares estimation of parameters in errors-in-variables models.” J. Franklin Inst. 356 (15): 8785–8802. https://doi.org/10.1016/j.jfranklin.2019.06.016.
Xu, P., J. Liu, and C. Shi. 2012. “Total least squares adjustment in partial errors-in-variables models: Algorithm and statistical analysis.” J. Geod. 86 (8): 661–675. https://doi.org/10.1007/s00190-012-0552-9.
Xu, P., J. Liu, W. Zeng, and Y. Shen. 2014. “Effects of errors-in-variables on weighted least squares estimation.” J. Geod. 88 (7): 705–716. https://doi.org/10.1007/s00190-014-0716-x.
Yang, Y., M. K. Cheng, C. K. Shum, and B. D. Tapley. 1999. “Robust estimation of systematic errors of satellite laser range.” J. Geod. 73 (7): 345–349. https://doi.org/10.1007/s001900050252.
Zhang, S., K. Zhang, J. Han, and X. Tong. 2017. “Total least norm solution for linear structured EIV model.” Appl. Math. Comput. 304 (Jul): 58–64. https://doi.org/10.1016/j.amc.2017.01.006.
Zhao, J. 2017. “Efficient weighted total least-squares solution for partial errors-in-variables model.” Surv. Rev. 49 (356): 346–354. https://doi.org/10.1080/00396265.2016.1180753.
Zheng, Y., Y. Li, M. Thiruvengadam, H. Lan, and J. C. Tien. 2017. “DPM dispersion inside a single straight entry using dynamic mesh model.” Int. J. Coal Sci. Technol. 4 (3): 234–244. https://doi.org/10.1007/s40789-017-0179-9.
Zhou, Y., X. Kou, J. Li, and X. Fang. 2017. “Comparison of structured and weighted total least-squares adjustment methods for linearly structured errors-in-variables models.” J. Surv. Eng. 143 (1): 04016019. https://doi.org/10.1061/(ASCE)SU.1943-5428.0000190.
Information & Authors
Information
Published In
Journal of Surveying Engineering
Volume 147 • Issue 4 • November 2021
Copyright
© 2021 American Society of Civil Engineers.
History
Received: Feb 15, 2021
Accepted: Jun 4, 2021
Published online: Jul 30, 2021
Published in print: Nov 1, 2021
Discussion open until: Dec 30, 2021
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.
Cited by
- Jie Han, Songlin Zhang, Shimeng Dong, Qingyun Yan, Comparison of Posterior Precision Estimation Methods of Weighted Total Least-Squares Solution for Errors-in-Variables Model, Journal of Surveying Engineering, 10.1061/JSUED2.SUENG-1480, 150, 4, (2024).
- Saeid Gholinejad, Alireza Amiri-Simkooei, Multivariate Weighted Total Least Squares Based on the Standard Least-Squares Theory, Journal of Surveying Engineering, 10.1061/JSUED2.SUENG-1424, 149, 4, (2023).
- Xunqiang Gong, Hongyu Wang, Tieding Lu, Wei You, Rui Zhang, Combined Prediction Model for High-Speed Railway Bridge Pier Settlement Based on Robust Weighted Total Least-Squares Autoregression and Adaptive Dynamic Cubic Exponential Smoothing, Journal of Surveying Engineering, 10.1061/JSUED2.SUENG-1379, 149, 2, (2023).
- Zhijun Kang, A simple iterative algorithm based on weighted least-squares for errors-in-variables models: Examples of coordinate transformations, Journal of Applied Geodesy, 10.1515/jag-2021-0053, 16, 3, (203-215), (2022).