×

A new error in variables model for solving positive definite linear system using orthogonal matrix decompositions. (English) Zbl 1355.65046

The paper deals with the estimation of a positive definite solution to an overdetermined linear system with multiple right hand sides vectors. It considers that an error in the measured data and target matrices appears. The presented approach is based on a newly defined error function. The necessary and sufficient optimality conditions are derived and the direct algorithm to compute the solution is proposed. Two comparisons are presented: with respect to the interior point method and the method based on the quadratic programming. It is shown that the presented method leads to smaller standard deviation of error entries and smaller effective rank as desired by control problems.
More precisely, the following problem is discussed: \[ \min_{X\succ 0} \text{tr} ((DX-T)^T(D-TX^{-1})), \] where \(D,T\in \mathbb R^{{m\times n}}\), \(m\geq n\), are given and a positive definite matrix \(X\in \mathbb R^{n\times n}\) is to be computed. \(\text{tr}\) stands for trace of a matrix. The simplified form of the problem is the following: \[ DX\cong T. \] It is called the EVI problem.
Algorithm 1 is based on the orthogonal decomposition and the spectral decomposition. Algorithm 2 uses only the spectral decomposition. The most sophisticated Algorithm 3 is based on the spectral decomposition, rank determination, linear system solving, and the Cholesky decompositon. The complexity of computations is analysed and numerical experiments conclude the paper (with observations mentioned above).
The paper is well written, instructive and easily understandable.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65K05 Numerical mathematical programming methods
90C20 Quadratic programming
90C51 Interior-point methods

Software:

mftoolbox; VanHuffel
PDFBibTeX XMLCite
Full Text: DOI arXiv

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. 8, 746-768 (1998) · Zbl 0911.65047
[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 60(6), 3004-3021 (2012) · Zbl 1393.94166
[3] Cheng, C.L., Kukush, A., Mastronardi, N., Paige, C., Van Huffel, S.: Total least squares and errors-in-variables modeling. Comput. Stat. Data Anal. 52, 1076-1079 (2007) · Zbl 1452.00028
[4] 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) · Zbl 0847.65024
[5] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201-213 (2012) · Zbl 1049.90004
[6] Golub, G.H., Van Loan, C.F.: An analysis of the total least squares problem. SIAM J. Numer. Anal. 17, 883-893 (1980) · Zbl 0468.65011
[7] Hayami, K., Yin, J.F., Ito, T.: GMRES method for least squares problems. SIAM J. Matrix Anal. Appl. 31(5), 2400-2430 (2010) · Zbl 1215.65071
[8] Hnetynková, I., Plesinger, M., Sima, D.M., Strakos, Z., Van Huffel, S.: The total least squares problem in AX˜B, A new classification with the relationship to the classical works. SIAM J. Matrix Anal. Appl. 32(3), 748-770 (2011) · Zbl 1235.15016
[9] Hu, H., Olkin, I.: A numerical procedure for finding the positive definite matrix closest to a patterned matrix. Stat. Probabil. Lett. 12, 511-515 (1991) · Zbl 0850.62486
[10] Hu, H.: Positive definite constrained least-squares estimation of matrices. Linear Algebra Appl. 229, 167-174 (1995) · Zbl 0847.65024
[11] Van Huffel, S., Vandewalle, J.: Algebraic connections between the least squares and total least squares problems. Numer. Math. 55, 431-449 (1989) · Zbl 0663.65038
[12] 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 (2011) · Zbl 1171.65031
[13] Larson, H.J.: Least squares estimation of the components of a symmetric matrix. Technometrics 8(2), 360-362 (1966) · Zbl 0135.19503
[14] McInroy, J., Hamann, J.C.: Design and control of flexure jointed hexapods. IEEE Trans. Robot. Autom. 16(4), 372-381 (2000)
[15] Moré, J.J., Wild, S.M.: Benchmarking derivative-free optimization algorithms. SIAM J. Optim. 20, 172-191 (2009) · Zbl 1187.90319
[16] Paige, C. C., Strakos, Z.: Scaled total least squares fundamentals. Numer. Math. 91, 117-146 (2000) · Zbl 0998.65046
[17] 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, pp 3622-3627 (2000) · Zbl 1393.94166
[18] Woodgate, K.G.: Least-squares solution of F=PG over positive semidefinite symmetric P. Linear Algebra Appl. 245, 171-190 (1996) · Zbl 0856.90106
[19] Zhou, L., Lin, L., Wei, Y., Qiao, S.: Perturbation analysis and condition numbers of scaled total least squares problems. Numer. Algorithms 51, 381-399 (2009) · Zbl 1171.65031
[20] Banerjee, S., Roy, A.: Quadratic Forms, Linear Algebra and Matrix Analysis for Statistics. Chapman & Hall/CRC Texts in Statistical Sciences, pp 441-442 (2014) · Zbl 0850.62486
[21] Carlen, E.: Trace inequalities and quantum entropy: an introductory course. Contemporary Math. AMS 529, 73-140 (2009) · Zbl 1218.81023
[22] Gill, P.E., Murray, W., Wright, M.H.: Numerical Linear Algebra and Optimization. Addison Wesley (1991) · Zbl 0714.65063
[23] Higham, N.J.: Functions of Matrices: Theory and Computation. SIAM, Philadelphia (2008) · Zbl 1167.15001
[24] Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press (1991) · Zbl 0729.15001
[25] Van Huffel, S., Vandewalle, J.: The Total Least Squares Problem: Computational Aspects and Analysis. SIAM, Philadelphia (1991) · Zbl 0789.62054
[26] Krislock, N.G.: Numerical Solution of Semidefinite Constrained Least Squares Problems, M. Sc. Thesis, University of British Colombia (2003)
[27] Demmel, J.W.: Applied Numerical Linear Algebra, 3rd edn. SIAM, Philadelphia (1996) · Zbl 0879.65017
[28] Golub, G.H., Van Loan, C.F.: Matrix Computation, 4th edn. JHU Press (2012)
[29] Lancaster, P., Rodman, L.: Algebraic Riccati Equations. Clarendon Press (1995) · Zbl 0836.15005
[30] Magnus, J.R., Neudecker, H.: Matrix Differential Calculus with Applications in Statistics and Econometrics, 2nd edn. Wiley (1999) · Zbl 0912.15003
[31] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (1999) · Zbl 0930.65067
[32] 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
[33] Petersen, K.B., Pedersen, M.S. The matrix cookbook. http://orion.uwaterloo.ca/hwolkowi/matrixcookbook.pdf (2008). Accessed 11 January 2013 · Zbl 0468.65011
[34] Vershynin, R. Introduction to the non-asymptotic analysis of random matrices. http://arxiv.org/pdf/1011.3027v7.pdf (2011). Accessed 01 February 2013 · Zbl 1235.60009
[35] American Mathematical Society, Eigenvalues and sums of Hermitian matrices. http://www.ams.org/bookstore/pspdf/gsm-132-prev.pdf (2009). Accessed 18 March 2013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.