×

zbMATH — the first resource for mathematics

On the partial condition numbers for the indefinite least squares problem. (English) Zbl 1377.65049
Summary: The condition number of a linear function of the indefinite least squares solution is called the partial condition number for the indefinite least squares problem. In this paper, based on a new and very general condition number which can be called the unified condition number, we first present an expression of the partial unified condition number when the data space is measured by a general weighted product norm. Then, by setting the specific norms and weight parameters, we obtain the expressions of the partial normwise, mixed and componentwise condition numbers. Moreover, the corresponding structured partial condition numbers are also taken into consideration when the problem is structured. Considering the connections between the indefinite and total least squares problems, we derive the (structured) partial condition numbers for the latter, which generalize the ones in the literature. To estimate these condition numbers effectively and reliably, the probabilistic spectral norm estimator and the small-sample statistical condition estimation method are applied and three related algorithms are devised. Finally, the obtained results are illustrated by numerical experiments.

MSC:
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F35 Numerical computation of matrix norms, conditioning, scaling
Software:
mctoolbox; VanHuffel
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Arioli, M.; Baboulin, M.; Gratton, S., A partial condition number for linear least-squares problems, SIAM J. Matrix Anal. Appl., 29, 413-433, (2007) · Zbl 1141.65028
[2] Baboulin, M.; Gratton, S., Using dual techniques to derive componentwise and mixed condition numbers for a linear function of a linear least squares solution, BIT Numer. Math., 49, 3-19, (2009) · Zbl 1168.65022
[3] Baboulin, M.; Gratton, S., A contribution to the conditioning of the total least-squares problem, SIAM J. Matrix Anal. Appl., 32, 685-699, (2011) · Zbl 1242.65087
[4] Baboulin, M.; Gratton, S.; Lacroix, R.; Laub, A. J., Statistical estimates for the conditioning of linear least squares problems, Lecture Notes in Comput. Sci., 8384, 124-133, (2014)
[5] Bergou, E. H.; Gratton, S.; Tshimanga, J., The exact condition number of the truncated singular value solution of a linear ill-posed problem, SIAM J. Matrix Anal. Appl., 35, 1073-1085, (2014) · Zbl 1308.65059
[6] Bojanczyk, A. W.; Higham, N. J.; Patel, H., Solving the indefinite least squares problem by hyperbolic QR factorization, SIAM J. Matrix Anal. Appl., 24, 914-931, (2003) · Zbl 1036.65035
[7] Burgisser, P.; Cucker, F., Condition: the geometry of numerical algorithms, (2013), Springer Heidelberg · Zbl 1280.65041
[8] Cao, Y.; Petzold, L., A subspace error estimate for linear systems, SIAM J. Matrix Anal. Appl., 24, 787-801, (2003) · Zbl 1036.65042
[9] Chandrasekaran, S.; Gu, M.; Sayed, A. H., A stable and efficient algorithm for the indefinite linear least-squares problem, SIAM J. Matrix Anal. Appl., 20, 354-362, (1998) · Zbl 0920.65024
[10] Cucker, F.; Diao, H., Mixed and componentwise condition numbers for rectangular structured matrices, Calcolo, 44, 89-115, (2007) · Zbl 1168.15304
[11] 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) · Zbl 1115.15004
[12] Diao, H.-A.; Wei, Y.; Qiao, S., Structured condition numbers of structured Tikhonov regularization problem and their estimations, J. Comput. Appl. Math., 308, 276-300, (2016) · Zbl 1346.65015
[13] Diao, H.-A.; Wei, Y.; Xie, P., Small sample statistical condition estimation for the total least squares problem, Numer. Algorithms, (2016)
[14] Diao, H.; Xiang, H.; Wei, Y., Mixed, componentwise condition numbers and small sample statistical condition estimation of Sylvester equations, Numer. Linear Algebra Appl., 19, 639-654, (2012) · Zbl 1274.65120
[15] Diao, H.-A.; Zhou, T.-Y., Backward error and condition number analysis for the indefinite linear least squares problem, (2016)
[16] Geurts, A. J., A contribution to the theory of condition, Numer. Math., 39, 85-96, (1982) · Zbl 0465.65025
[17] Gohberg, I.; Koltracht, I., Mixed, componentwise, and structured condition numbers, SIAM J. Matrix Anal. Appl., 14, 688-704, (1993) · Zbl 0780.15004
[18] Golub, G. H.; Kahan, W., Calculating the singular values and pseudo-inverse of a matrix, J. Soc. Ind. Appl. Math., Ser. B Numer. Anal., 2, 205-224, (1965) · Zbl 0194.18201
[19] 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
[20] Golub, G. H.; Van Loan, C. F., Matrix computations, (2013), Johns Hopkins University Press Baltimore · Zbl 1268.65037
[21] Gratton, S., On the condition number of linear least squares problems in a weighted Frobenius norm, BIT Numer. Math., 36, 523-530, (1996) · Zbl 0878.65030
[22] Grcar, J. F., Unattainable of a perturbation bound for indefinite linear least squares problem, (2011)
[23] Gudmundsson, T.; Kenney, C. S.; Laub, A. J., Small-sample statistical estimates for matrix norms, SIAM J. Matrix Anal. Appl., 16, 776-792, (1995) · Zbl 0831.65051
[24] Hassibi, B.; Sayed, A. H.; Kailath, T., Linear estimation in Krein spaces—part I: theory, IEEE Trans. Autom. Control, 41, 18-33, (1996) · Zbl 0862.93055
[25] Higham, N. J., Accuracy and stability of numerical algorithms, (2002), SIAM Philadelphia · Zbl 1011.65010
[26] Higham, D. J.; Higham, N. J., Backward error and condition of structured linear systems, SIAM J. Matrix Anal. Appl., 13, 162-175, (1992) · Zbl 0747.65028
[27] Hochstenbach, M. E., Probabilistic upper bounds for the matrix two-norm, J. Sci. Comput., 57, 464-476, (2013) · Zbl 1292.65037
[28] Horn, R. A.; Johnson, C. R., Topics in matrix analysis, (1991), Cambridge University Press New York · Zbl 0729.15001
[29] Huffel, S. V.; Vandewalle, J., The total least squares problem: computational aspects and analysis, (1991), SIAM Philadelphia · Zbl 0789.62054
[30] Jia, Z.; Li, B., On the condition number of the total least squares problem, Numer. Math., 125, 61-87, (2013) · Zbl 1287.65034
[31] Kenney, C. S.; Laub, A. J., Small-sample statistical condition estimates for general matrix functions, SIAM J. Sci. Comput., 15, 36-61, (1994) · Zbl 0801.65042
[32] Kenney, C. S.; Laub, A. J.; Reese, M. S., Statistical condition estimation for linear systems, SIAM J. Sci. Comput., 19, 566-583, (1998) · Zbl 0915.15003
[33] Kenney, C. S.; Laub, A. J.; Reese, M. S., Statistical condition estimation for linear least squares, SIAM J. Matrix Anal. Appl., 19, 906-923, (1998) · Zbl 0913.65035
[34] Laub, A. J.; Xia, J., Applications of statistical condition estimation to the solution of linear systems, Numer. Linear Algebra Appl., 15, 489-513, (2008) · Zbl 1212.65130
[35] Li, B.; Jia, Z., Some results on condition numbers of the scaled total least squares problem, Linear Algebra Appl., 435, 674-686, (2011) · Zbl 1228.65058
[36] Li, H.; Wang, S.; Yang, H., On mixed and componentwise condition numbers for indefinite least squares problem, Linear Algebra Appl., 448, 104-129, (2014) · Zbl 1286.65051
[37] Liu, Q.; Li, X., Preconditioned conjugate gradient methods for the solution of indefinite least squares problems, Calcolo, 48, 261-271, (2011) · Zbl 1230.65052
[38] Liu, Q.; Liu, A., Block SOR methods for the solution of indefinite least squares problems, Calcolo, 51, 367-379, (2014) · Zbl 1314.65059
[39] Mastronardi, N.; Van Dooren, P., An algorithm for solving the indefinite least squares problem with equality constraints, BIT Numer. Math., 54, 201-218, (2014) · Zbl 1290.65033
[40] Rice, J. R., A theory of condition, SIAM J. Numer. Anal., 3, 287-310, (1966) · Zbl 0143.37101
[41] Rump, S. M., Structured perturbations. part I: normwise distances, SIAM J. Matrix Anal. Appl., 25, 1-30, (2003) · Zbl 1061.15004
[42] Rump, S. M., Structured perturbation. part II: componentwise distances, SIAM J. Matrix Anal. Appl., 25, 31-56, (2003) · Zbl 1061.15005
[43] Sayed, A. H.; Hassibi, B.; Kailath, T., Inertia properties of indefinite quadratic forms, IEEE Signal Process. Lett., 3, 57-59, (1996)
[44] Wang, Q., Perturbation analysis for generalized indefinite least squares problems, J. East China Norm. Univ. Natur. Sci. Ed., 4, 47-53, (2009) · Zbl 1212.65164
[45] Wei, Y.; Diao, H.; Qiao, S., Condition number for weighted linear least squares problem, J. Comput. Math., 25, 561-572, (2007) · Zbl 1140.65324
[46] Xie, Z.; Li, W.; Jin, X., On condition numbers for the canonical generalized polar decomposition of real matrices, Electron. J. Linear Algebra, 26, 842-857, (2013) · Zbl 1283.15024
[47] Xie, P.; Wei, Y.; Xiang, H., Perturbation analysis and randomized algorithms for large-scale total least squares problems, (2014)
[48] Xu, H., A backward stable hyperbolic QR factorization method for solving indefinite least squares problem, J. Shanghai Univ., 8, 391-396, (2004)
[49] Xu, W.; Wei, Y.; Qiao, S., Condition numbers for structured least squares problems, BIT Numer. Math., 46, 203-225, (2006) · Zbl 1093.65045
[50] Yang, H.; Wang, S., A flexible condition number for weighted linear least squares problem and its statistical estimation, J. Comput. Appl. Math., 292, 320-328, (2016) · Zbl 1327.65089
[51] 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
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.