On condition numbers of the total least squares problem with linear equality constraint
Tóm tắt
This paper is devoted to condition numbers of the total least squares problem with linear equality constraint (TLSE). With novel limit techniques, closed formulae for normwise, mixed and componentwise condition numbers of the TLSE problem are derived. Computable expressions and upper bounds for these condition numbers are also given to avoid the costly Kronecker product-based operations. The results unify the ones for the TLS problem. For TLSE problems with equilibratory input data, numerical experiments illustrate that normwise condition number-based estimate is sharp to evaluate the forward error of the solution, while for sparse and badly scaled matrices, mixed and componentwise condition number-based estimates are much tighter.
Tài liệu tham khảo
Baboulin, M., Gratton, S.: A contribution to the conditioning of the total least-squares problem. SIAM J. Matrix Anal. Appl. 32, 685–699 (2011)
Ben-Israel, A., Greville, T.N.E.: Generalized Inverses, Theory and Applications, 2nd edn. Spring, New York (2003)
Björck, Å., Heggerness, P., Mathstoms, P.: Methods for large scale total least squares problems. SIAM J. Matrix Anal. Appl. 22, 413–429 (2000)
Boyd, S., Vandenberghe, L.: Introduction to Applied Linear Algebra-Vectors, Matrices, and Least Squares. Cambridge University Press, Cambridge (2018)
Cucker, F., Diao, H., Wei, Y.: On mixed and componentwise condition numbers for Moore-Penrose inverse and linear least squares problems. Math. Comput. 76, 947–963 (2007)
Diao, H.: On condition numbers for least squares with quadric inequality constraint. Comput. Math. Appl. 73, 616–627 (2017)
Diao, H.: Condition numbers for a linear function of the solution of the linear least squares problem with equality constraints. J. Comput. Appl. Math. 344, 640–656 (2018)
Diao, H., Sun, Y.: Mixed and componentwise condition numbers for a linear function of the solution of the total least squares problem. Linear AlgebraAppl. 544(1), 1–29 (2018)
Diao, H., Wei, Y., Xie, P.: Small sample statistical condition estimation for the total least squares problem. Numer. Algorithms 75(2), 1–21 (2017)
Dowling, E.M., Degroat, R.D., Linebarger, D.A.: Total least squares with linear constraints. IEEE International Conference on Acoustics, Speech, and Signal Processing 5, 341–344 (1992)
Fasino, D., Fazzi, A.: A Gauss-Newton iteration for total least squares problems. BIT 58, 281–299 (2018)
Geurts, A.J.: A contribution to the theory of condition. Numer Math. 39, 85–96 (1982)
Gohberg, I., Koltracht, I.: Mixed, componentwise, and structured condition numbers. SIAM J. Matrix Anal. Appl. 14, 688–704 (1993)
Golub, G.H., Van Loan, C.F.: An analysis of total least squares problem. SIAM J. Matrix Anal. Appl. 17(6), 883–893 (1980)
Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. Johns Hopkins University Press, Baltimore (2013)
Graham, A.: Kronecker Products and Matrix Calculus with Application. Ellis Horwood and John Wiley & Sons, New York (1981)
Gratton, S.: On the condition number of linear least squares problems in a weighted Frobenius norm. BIT 36, 523–530 (1996)
Halko, N., Martinsson, P.G., Tropp, J.A.: Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53, 217–288 (2011)
Hermus, K., Verhelst, W., Lemmerling, P., Wambacq, P., Van Huffel, S.: Perceptual audio modeling with exponentially damped sinusoids. Signal Process. 85, 163–176 (2005)
Jia, Z., Li, B.: On the condition number of the total least squares problem. Numer. Math. 125, 61–87 (2013)
Langville, A.N., Stewart, W.J.: The Kronecker product and stochastic automata networks. J. Comput. Appl. Math. 167, 429–447 (2004)
Lemmerling, P., De Moor, B.: Misfit versus latency. Automatica 37, 2057–2067 (2001)
Lemmerling, P., Mastronardi, N., Van Huffel, S.: Efficient implementation of a structured total least squares based speech compression method. Linear Algebra Appl. 366, 295–315 (2003)
Li, B., Jia, Z.: Some results on condition numbers of the scaled total least squares problem. Linear Algebra Appl. 435, 674–686 (2011)
Liu, Q., Chen, C., Zhang, Q.: Perturbation analysis for total least squares problems with linear equality constraint. Appl. Numer. Math. 161, 69–81 (2021)
Liu, Q., Jia, Z., Wei, Y.: A contribution tocondition numbers of the multidimensional total least squares problem with linear equality constraint. SIAM J. Matrix Anal. Appl. 43, 124–150 (2022)
Liu, Q., Jin, S., Yao, L., Shen, D.: The revisited total least squares problems with linear equality constraint. Appl. Numer. Math. 152, 275–284 (2020)
Liu, Q., Wei, M.: On direct elimination methods for solving the equality constrained least squares problem. Linear & Multilinear Algebra 58, 173–184 (2010)
Liu, Q., Zhang, Q., Shen, D.: Condition numbers of the mixed least squares-total least squares problem revisited. To appear in Linear and Multilinear Algebra (2022)
Markovsky, I., Van Huffel, S.: Overview of total least squares methods. Signal Process. 87, 2283–2302 (2007)
Meng, L., Zheng, B., Wei, Y.: Condition numbers of the multidimensional total least squares problems having more than one solution. Numerical Algorithms 84, 887–908 (2020)
Ng, M., Bose, N., Koo, J.: Constrained total least squares for color image reconstruction. Total Least Squares and Errors-in-Variables Modelling III: Analysis, Algorithms and Applications, 365–374. Kluer Academic Publishers (2002)
Ng, M., Plemmons, R., Pimentel, F.: A new approach to constrained total least squares image restoration. Linear Algebra Appl. 316, 237–258 (2000)
Pearson, K.: On lines and planes of closest fit to systems of points in space. Phil. Mag. 2, 559–572 (1901)
De Pierro, A.R., Wei, M.: Some new properties of the equality constrained and weighted least squares problem. Linear Algebra Appl. 320, 145–165 (2000)
Rice, J.R.: A theory of condition. SIAM J. Numer. Anal. 3, 287–310 (1966)
Schaffrin, B.: A note on constrained total least squares estimation. Linear Algebra Appl. 417, 245–258 (2006)
Shen, Y., Li, B., Chen, Y.: An iterative solution of weighted total least-squares adjustment. J. Geod. 85, 229–238 (2011)
Stewart, G.W.: On the asymptotic behavior of scaled singular value and QR decompositions. Math. Comput. 43(168), 483–489 (1984)
Van Huffel, S.: Partial singular value decomposition algorithm. J. Comput. Appl. Math. 33, 105–112 (1990)
Van Huffel, S., Lemmerling, P. (eds.): Total Least Squares and Errors-in-Variables Modeling: Analysis, Algorithms and Applications. Kluwer, Dordrecht, Boston, London (2002)
Van Huffel, S., Vandevalle, J.: The Total Least Squares Problems: Computational Aspects and Analysis. 9 of Frontiers in Applied Mathematics. SIAM, Philadelphia (1991)
Wei, Y., Diao, H., Qiao, S.: Condition number for weighted linear least squares problem. J. Comput. Math. 25, 561–572 (2007)
Wei, M.: The analysis for the total least squares problem with more than one solution. SIAM J. Matrix Anal. Appl. 13, 746–763 (1992)
Wei, M.: Algebraic relations between the total least squares and least squares problems with more than one solution. Numer. Math. 62, 123–148 (1992)
Wei, M.: Perturbation theory for the rank-deficient equality constrained least squares problem. SIAM J. Numer. Anal. 29, 1462–1481 (1992)
Wei, M., De Pierro, A.R.: Upper perturbation bounds of weighted projections, weighted and constrained least squares problems. SIAM J. Matrix Anal. Appl. 21, 931–951 (2000)
Xie, P., Xiang, H., Wei, Y.: A contribution to perturbation analysis for total least squares problems. Numer. Algorithms 75, 381–395 (2017)
Xie, P., Xiang, H., Wei, Y.: Randomized algorithms for total least squares problems. Numer. Linear Algebra Appl. 26, e2219 (2018)
Yang, H., Wang, S.: A fexible condition number for weighted linear least squares problem and its statistical estimation. J. Comput. Appl. Math. 292, 320–328 (2016)
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)
Zheng, B., Meng, L., Wei, Y.: Condition numbers of the multidimensional total least squares problem. SIAM J. Matrix Anal. Appl. 38, 924–948 (2017)
Zheng, B., Yang, Z.: Perturbation analysis for mixed least squares-total least squares problems. Numer Linear Algebra Appl. 26, e2239 (2019)