jzs-10821

Competitive Algorithms for Large Scale Positive Definite Linear Systems of Equations Using an Error in Variables Optimization Model

Nezam Mahdavi-Amiri*1 and Negin Bagherpour1

1 Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran

*Corresponding author’s e-mail: nezamm@sharif.edu

Original: 29 may 2020        Revised: 21 August 2020        Accepted: 26 September 2020        Published online: 20 December 2020  

Doi Link:

Abstract

   We seek positive definite solutions of large scale overdetermined linear systems of equations with multiple right hand sides, where the coefficient and the right hand side matrices are respectively called data and target matrices. We recently proposed a new approach for solving such problems in small scales considering error in both the measured data and the target matrices and using a novel error formulation. We proposed four algorithms for solving small scale positive definite linear systems of equations with both full rank and rank deficient data matrices. Here, we extend our algorithms to solve large scale problems. The algorithms are implemented in Matlab and Fortran (using the ScaLAPACK library) respectively for small and large scale problems . ScaLAPACK is a parallel library written in Fortran to solve linear algebra problems such as computing matrix decompositions for large scale matrices. Block cyclic data distribution is used in ScaLAPACK to provide proper scalability, reliability, portability, flexibility and ease of use. Comparative numerical experiments with two available methods, the interior point method and a method based on quadratic programming, show that our approach produce a smaller standard deviation of the error entries and a smaller effective rank, as being desirable for control problems. Using the Dolan-More performance profiles we show that our proposed algorithms are more efficient and more accurate in computing proper solutions.

Key Words: large scale problems, Dolan-More, ScaLAPACK

References

[1]  Alizadeh F., Pierre J., Heaberly A., Overton M. L. "Primal-dual interior point methods for semidefinite programming: convergence rates, stability and numerical result". SIAM J. Optim. Vol. 8, pp. 746-768. (1998).

[2]  Aubry A., Maio A. D., Pallotta L., Farina A. "Maximum likelihood estimation of a structured covariance matrix with a condition number constraint". IEEE Trans. On Signal Processing. Vol. 60, No. 6, pp. 3004-3021. (2012).

[3]  Bagherpour N., Mahdavi-Amiri N. "A new error in variables model for solving positive definite linear system using orthogonal matrix decompositions". Numer. Alg. Vol. 72, No. 1, pp. 211-241. (2016).

[4]  Byrd R. H., Mary E., Nocedal J. "An Interior Point Algorithm for Large-Scale Nonlinear Programming". SIAM J. Optim. Vol. 9, No. 4, pp. 877-900. (1999).

[5]  Cheng C. L., Kukush A., Mastronardi N., Paige C., Van Huffel S. "Total Least Squares and Errors-in-variables Modeling". Comput. Stat. Data An. Vol. 52, pp. 1076-1079. (2007).

[6]  Deng Y., Boley D. "On the Optimal Approximation for the Symmetric Procrustes Problems of the Matrix Equation AXB = C". Proceedings of the International Conference on Computational and Mathematical Methods in Science and Engineering, Chicago. Pp. 159-168. (2007).

[7]  Dolan E. D, Moré J. J. "Benchmarking optimization software with performance profiles". Mathematical Programming. Vol. 91, pp. 201-213. (2012).

[8]  Golub G. H., Van Loan C. F. "An analysis of the total least squares problem". SIAM J. Numer. Anal. Vol. 17, pp. 883-893. (1980).

[9]  Hayami K., Yin J. F., Ito T. "GMRES method for least squares problems". SIAM. J. Matrix Anal. and Appl. Vol.  31, No. 5, pp. 2400-2430. (2010).

[10]  Hnětynková I., Plešinger M., Sima D. M., Strakoš Z., Van Huffel S. "The total least squares problem in , A new classification with the relationship to the classical works". SIAM J. Matrix Anal. Appl. Vol. 32, No. 3, pp. 748-770. (2011).

[11]  Hu H., Olkin I. "A numerical procedure for finding the positive definite matrix closest to a patterned matrix". Statistical and Probability Letters. Vol. 12, pp. 511-515. (1991).

[12]  Hu H. "Positive definite constrained least-squares estimation of matrices". Linear Algebra and its Applications. Vol. 229, pp. 167-174. (1995).

[13]  Van Huffel S., Vandewalle J. "Algebraic connections between the least squares and total least squares problems". Numer. Math. Vol. 55, pp. 431-449. (1989).

[14]  Kang B., Jung S., Park P. "A new iterative method for solving total least squares problem". Proceeding of the 8th Asian Control Conference (ASCC), Kaohsiung, Taiwan, (2011).

[15]  Larson H. J. "Least squares estimation of the components of a symmetric matrix". Technometrics. Vol. 8, No. 2, pp. 360-362. (1966).

[16]  McInroy J., Hamann J. C. "Design and control of flexure jointed hexapods". IEEE Trans. Robotics and Automation. Vol. 16, No. 4, pp. 372-381. (2000).

[17]  Paige C. C., Strakoš Z. "Scaled total least squares fundamentals". Numer. Math. Vol. 91, pp. 117-146. (2000).

[18]  Poignet P., Gautier M. "Comparison of Weighted Least Squares and Extended Kalman Filtering Methods for Dynamic Identification of Robots". Proceedings of the IEEE Conference on Robotics and Automation, San Francisco, CA, USA, pp. 3622-3627. (2000).

[19]  Woodgate K. G. "Least-squares solution of  over positive semidefinite symmetric P". Linear Algebra Appl. Vol. 245, pp. 171-190. (1996).

[20]  Zhou L., Lin L., Wei Y., Qiao S. "Perturbation analysis and condition numbers of scaled total least squares problems". Numer. Algorithms. Vol. 51, pp. 381-399. (2009).

[21]  Banerjee S., Roy A. "Quadratic Forms, Linear Algebra and Matrix Analysis for Statistics". Chapman & Hall/CRC Texts in Statistical Sciences, pp. 441-442. (2014).

[22]  Carlen E. "Trace Inequalities and Quantum Entropy: An Introductory Course". Contemporary Mathematics, Vol. 529, AMS, pp. 73-140. (2009).

[23]  Gill P. E. , Murray W., Wright M. H. "Numerical Linear Algebra and Optimization". Addison Wesley (1991).

[24]  Blackford L. S., Choi J., Cleary A., et. al. "Software, Environments and Tools: ScaLAPACK User's Guide", SIAM, Philadelphia. (1997).

[25]  Higham N. J. "Functions of Matrices: Theory and Computation". SIAM, Philadelphia. (2008).

[26]  Horn R. A., Johnson C. R. "Topics in Matrix Analysis". Cambridge University Press. (1991).

[27]  Van Huffel S., Vandewalle J. "The Total Least Squares Problem: Computational Aspects and Analysis". SIAM, Philadelphia. (1991).

[28]  Krislock N. G. "Numerical Solution of Semidefinite Constrained Least Squares Problems". M. Sc. Thesis, University of British Colombia. (2003).

[29]  Demmel J. W. "Applied Numerical Linear Algebra". 3rd edition, SIAM, Philadelphia. (1996).

[30]  Golub G. H., Van Loan C. F. "Matrix Computation". 4th edition, JHU Press. (2012).

[31]  Lancaster P., Rodman L. "Algebraic Riccati Equations". Clarendon Press. (1995).

[32]  Magnus J. R., Neudecker H. "Matrix Differential Calculus with Applications in Statistics and Econometrics". 2nd edition, John Wiley & Sons. (1999).

[33]  Nocedal J., Wright S. J. "Numerical Optimization". Springer, New York. (1999).

[34]  Higham N. J. "Computing the nearest correlation matrix (A problem from nance)". MIMS EPrint: 2006.70, http://eprints.ma.man.ac.uk/, (2006). Accessed 26 June (2012).

[35]  Petersen K. B., Pedersen M. S.: The Matrix Cookbook, http://orion.uwaterloo.ca/ hwolkowi/matrixcookbook.pdf, (2008). Accessed 11 January (2013).

[36]  Vershynin R.: Introduction to the non-asymptotic analysis of random matrices, http://arxiv.org/pdf/1011.3027v7.pdf, (2011). Accessed 01 February (2013).

[37] American Mathematical Society, Eigenvalues and sums of Hermitian matrices, http://www.ams.org/bookstore/pspdf/gsm132prev.pdf, (2009). Accessed 18 March (2013).

View Full Article