×

zbMATH — the first resource for mathematics

Estimating the backward error for the least-squares problem with multiple right-hand sides. (English) Zbl 1453.65079
Summary: Let \(A\) and \(B\) be \(m\times n\) and \(m\times d\) matrices, and let \(\widetilde{X}\) be an approximate solution to the problem \(\min_X \|AX-B\|_F\). In 1996, J.-G. Sun [IMA J. Numer. Anal. 16, No. 1, 1–11 (1996; Zbl 0845.15002)] found an explicit expression for the optimal backward error – the size of the smallest perturbation to \(A\) (and possibly \(B)\) such that \(\widetilde{X}\) is an exact solution to the perturbed problem. The expression requires finding the difference of two potentially close numbers, and so its numerical evaluation can be unstable. We offer an estimate of the backward error that can be evaluated stably and when \(d=1\) is identical to the Karlson-Waldén estimate of 1997 [R. Karlson and B. Waldén, BIT 37, No. 4, 862–869 (1997; Zbl 0905.65051)]. We prove that this estimate always approximates the optimal backward error to within a factor of \(\sqrt{2}\).
MSC:
65F20 Numerical solutions to overdetermined systems, pseudoinverses
15A06 Linear equations (linear algebraic aspects)
65F35 Numerical computation of matrix norms, conditioning, scaling
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Sun, J.-G., Optimal backward perturbation bounds for the linear least-squares problem with multiple right-hand sides, IMA J. Numer. Anal., 16, 1, 1-11 (1996) · Zbl 0845.15002
[2] Waldén, B.; Karlson, R.; Sun, J.-G., Optimal backward perturbation bounds for the linear least squares problem, Numer. Linear Algebra Appl., 2, 3, 271-286 (1995) · Zbl 0848.65025
[3] Higham, N. J., Accuracy and Stability of Numerical Algorithms (2002), SIAM: SIAM Philadelphia · Zbl 1011.65010
[4] Stewart, G. W., An inverse perturbation theorem for the linear least squares problem, SIGNUM Newsl., 10, 2-3, 39-40 (1975)
[5] Stewart, G. W., Research, development, and LINPACK, (Mathematical Software, III (1977)), 1-14 · Zbl 0407.68027
[6] Karlson, R.; Waldén, B., Estimation of backward perturbation bounds for the linear least squares problem, BIT Numer. Math., 37, 862-869 (1997) · Zbl 0905.65051
[7] Gratton, S.; Jiránek, P.; Titley-Peloquin, D., On the accuracy of the Karlson-Walden estimate of the backward error in linear least squares problems, SIAM J. Matrix Anal. Appl., 33, 822-836 (2012) · Zbl 1268.65055
[8] Su, Z., Computational Methods for Least Squares Problems and Clinical Trials (2005), Stanford University: Stanford University Stanford, CA, USA, Ph.D. thesis
[9] Rigal, J. L.; Gaches, J., On the compatibility of a given solution with the data of a linear system, J. ACM, 14, 543-548 (1967) · Zbl 0183.17704
[10] Paige, C. C.; Saunders, M. A., LSQR: an algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Softw., 8, 1, 43-71 (1982) · Zbl 0478.65016
[11] Fong, D.; Saunders, M. A., LSMR: an iterative algorithm for sparse least squares problems, SIAM J. Sci. Comput., 33, 5, 2950-2971 (2011) · Zbl 1232.65052
[12] Gratton, S.; Jiránek, P.; Titley-Peloquin, D., Simple backward error bounds for linear least-squares problems, Linear Algebra Appl., 439, 78-89 (2013) · Zbl 1281.65065
[13] Gu, M., Backward perturbation bounds for linear least squares problems, SIAM J. Matrix Anal. Appl., 20, 2, 363-372 (1998) · Zbl 0948.65040
[14] Grcar, J. F., Optimal sensitivity analysis of linear least squares (2003), Lawrence Berkeley National Laboratory: Lawrence Berkeley National Laboratory Berkeley, CA, Tech. Rep. LBNL-52434
[15] Grcar, J. F.; Saunders, M. A.; Su, Z., Estimates of optimal backward perturbations for linear least squares problems (2007), Department of Management Science and Engineering, Stanford University: Department of Management Science and Engineering, Stanford University Stanford, CA, Tech. Rep. SOL-2007-1
[16] Recht, B.; Fazel, M.; Parrilo, P. A., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 3, 471-501 (2010) · Zbl 1198.90321
[17] Ball, K.; Carlen, E. A.; Lieb, E. H., Sharp uniform convexity and smoothness inequalities for trace norms, Invent. Math., 115, 1, 463-482 (1994) · Zbl 0803.47037
[18] Van Huffel, S.; Vandewalle, J., The Total Least Squares Problem: Computational Aspects and Analysis (1991), SIAM: SIAM Philadelphia · Zbl 0789.62054
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.