Backward error and condition number analysis for the indefinite linear least squares problem

References

• J.O. Aasen, On the reduction of a symmetric matrix to tridiagonal form, BIT 11 (1971), pp. 233–242. doi: 10.1007/BF01931804
   Google Scholar
• M. Arioli, M. Baboulin, and S. Gratton, A partial condition number for linear least squares problems, SIAM J. Matrix Anal. Appl. 29(2) (2007), pp. 413–433. doi: 10.1137/050643088
   Web of Science ®Google Scholar
• C. Ashcraft, R.G. Grimes, and J.G. Lewis, Accurate symmetric indefinite linear equation solvers, SIAM J. Matrix Anal. Appl. 20(2) (1999), pp. 513–561. doi: 10.1137/S0895479896296921
   Web of Science ®Google Scholar
• M. Baboulin and S. Gratton, Using dual techniques to derive componentwise and mixed condition numbers for a linear function of a linear least squares solution, BIT Numer. Math. 49(1) (2009), pp. 3–19. doi: 10.1007/s10543-009-0213-4
   Web of Science ®Google Scholar
• M. Baboulin and S. Gratton, A contribution to the conditioning of the total least-squares problem, SIAM J. Matrix Anal. Appl. 32(3) (2011), pp. 685–699. doi: 10.1137/090777608
   Web of Science ®Google Scholar
• A. Bojanczyk, N.J. Higham, and H. Patel, The equality constrained indefinite least squares problem: Theory and algorithms, BIT Numer. Math. 43(3) (2003), pp. 505–517. doi: 10.1023/B:BITN.0000007020.58972.07
   Web of Science ®Google Scholar
• A. Bojanczyk, N.J. Higham, and H. Patel, Solving the indefinite least squares problem by hyperbolic QR factorization, SIAM J. Matrix Anal. Appl. 24(4) (2003), pp. 914–931 (electronic). doi: 10.1137/S0895479802401497
   Web of Science ®Google Scholar
• J.R. Bunch and L. Kaufman, Some stable methods for calculating inertia and solving symmetric linear systems, Math. Comp. 31(137) (1977), pp. 163–179. doi: 10.1090/S0025-5718-1977-0428694-0
   Web of Science ®Google Scholar
• J.R. Bunch and B.N. Parlett, Direct methods for solving symmetric indefinite systems of linear equations, SIAM J. Numer. Anal. 8 (1971), pp. 639–655. doi: 10.1137/0708060
   Web of Science ®Google Scholar
• S. Chandrasekaran, M. Gu, and A.H. Sayed, A stable and efficient algorithm for the indefinite linear least-squares problem, SIAM J. Matrix Anal. Appl. 20(2) (1999), pp. 354–362. doi: 10.1137/S0895479896302229
   Web of Science ®Google Scholar
• X.-W. Chang and D. Titley-Peloquin, Backward perturbation analysis for scaled total least-squares problems, Numer. Linear Algebra Appl. 16(8) (2009), pp. 627–648. doi: 10.1002/nla.640
   Web of Science ®Google Scholar
• A.J. Cox and N.J. Higham, Backward error bounds for constrained least squares problems, BIT Numer. Math. 39(2) (1999), pp. 210–227. doi: 10.1023/A:1022385611904
   Web of Science ®Google Scholar
• F. Cucker and H. Diao, Mixed and componentwise condition numbers for rectangular structured matrices, Calcolo 44(2) (2007), pp. 89–115. doi: 10.1007/s10092-007-0130-3
   Web of Science ®Google Scholar
• F. Cucker, H. Diao, and Y. Wei, On mixed and componentwise condition numbers for Moore–Penrose inverse and linear least squares problems, Math. Comp. 76(258) (2007), pp. 947–964. doi: 10.1090/S0025-5718-06-01913-2
   Web of Science ®Google Scholar
• J.W. Demmel, On condition numbers and the distance to the nearest ill-posed problem, Numer. Math. 51(3) (1987), pp. 251–289. doi: 10.1007/BF01400115
   Web of Science ®Google Scholar
• H. Diao and Y. Wei, On Frobenius normwise condition numbers for Moore–Penrose inverse and linear least-squares problems, Numer. Linear Algebra Appl. 14(8) (2007), pp. 603–610. doi: 10.1002/nla.540
   Web of Science ®Google Scholar
• H.-A. Diao, Condition numbers for a linear function of the solution of the linear least squares problem with equality constraints, Technical Report, Northeast Normal University, 2016.
   Google Scholar
• H.-A. Diao, On condition numbers for least squares with quadric inequality constraint, Comput. Math. Appl. 73(4) (2017), pp. 616–627. doi: 10.1016/j.camwa.2016.12.033
   Web of Science ®Google Scholar
• H.-A. Diao and Y. Sun, Mixed and componentwise condition numbers for a linear function of the solution of the total least squares problem, Linear Algebra Appl. 544 (2018), pp. 1–29. doi: 10.1016/j.laa.2018.01.008
   Web of Science ®Google Scholar
• H.-A. Diao, L. Liang, and S. Qiao, A condition analysis of the weighted linear least squares problem using dual norms, Linear Multilinear Algebra 66(6) (2018), pp. 1085–1103. doi: 10.1080/03081087.2017.1337059
   Web of Science ®Google Scholar
• I. Gohberg and I. Koltracht, Mixed, componentwise, and structured condition numbers, SIAM J. Matrix Anal. Appl. 14(3) (1993), pp. 688–704. doi: 10.1137/0614049
   Web of Science ®Google Scholar
• A. Graham, Kronecker Products and Matrix Calculus: With Applications, Hasted, New York, 1981.
   Google Scholar
• S. Gratton, On the condition number of linear least squares problems in a weighted frobenius norm, BIT Numer. Math. 36(3) (1996), pp. 523–530. doi: 10.1007/BF01731931
   Web of Science ®Google Scholar
• J.F. Grcar, Optimal sensitivity analysis of linear least squares, Technical report, 2003.
   Google Scholar
• J.F. Grcar, M.A. Saunders, and Z. Su, Estimates of optimal backward perturbations for linear least squares problems, 2007. Available at http://www-leland.stanford.edu/group/SOL/reports/SOL-2007-1.pdf.
   Google Scholar
• B. Hassibi, A.H. Sayed, and T. Kailath, Linear estimation in Krein spaces – Part I: Theory, IEEE Trans. Autmat. Control 3(2) (1996), pp. 18–33. doi: 10.1109/9.481605
   Web of Science ®Google Scholar
• N.J. Higham, Computing error bounds for regression problems, in Statistical Analysis of Measurement Error Models and Applications (Arcata, CA, 1989), Contemp. Math. Vol. 112, Amer. Math. Soc., Providence, RI, 1990, pp. 195–208.
   Google Scholar
• N.J. Higham, A survey of componentwise perturbation theory in numerical linear algebra, in Mathematics of Computation 1943–1993: A Half-century of Computational Mathematics (Vancouver, BC, 1993), Proc. Sympos. Appl. Math., Vol. 48, Amer. Math. Soc., Providence, RI, 1994, pp. 49–77.
   Google Scholar
• N.J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, Philadelphia, PA, 2002.
   Google Scholar
• D.J. Higham and N.J. Higham, Backward error and condition of structured linear systems, SIAM J. Matrix Anal. Appl. 13(1) (1992), pp. 162–175. doi: 10.1137/0613014
   Web of Science ®Google Scholar
• R. Karlson and B. Waldén, Estimation of optimal backward perturbation bounds for the linear least squares problem, BIT Numer. Math. 37(4) (1997), pp. 862–869. doi: 10.1007/BF02510356
   Web of Science ®Google Scholar
• H. Li and S. Wang, Partial condition number for the equality constrained linear least squares problem, Calcolo 54 (2017), pp. 1121–1146. doi: 10.1007/s10092-017-0221-8
   Web of Science ®Google Scholar
• H. Li and S. Wang, On the partial condition numbers for the indefinite least squares problem, Appl. Numer. Math. 123 (2018), pp. 200–220. doi: 10.1016/j.apnum.2017.09.006
   Web of Science ®Google Scholar
• H. Li, S. Wang, and H. Yang, On mixed and componentwise condition numbers for indefinite least squares problem, Linear Algebra Appl. 448 (2014), pp. 104–129. doi: 10.1016/j.laa.2014.01.030
   Web of Science ®Google Scholar
• Q. Liu and X. Li, Preconditioned conjugate gradient methods for the solution of indefinite least squares problems, Calcolo 48(3) (2011), pp. 261–271. doi: 10.1007/s10092-011-0039-8
   Web of Science ®Google Scholar
• Q. Liu and A. Liu, Block SOR methods for the solution of indefinite least squares problems, Calcolo 51(3) (2014), pp. 367–379. doi: 10.1007/s10092-013-0090-8
   Web of Science ®Google Scholar
• Q. Liu and F. Zhang, Incomplete hyperbolic Gram-Schmidt-based preconditioners for the solution of large indefinite least squares problems, J. Comput. Appl. Math. 250 (2013), pp. 210–216. doi: 10.1016/j.cam.2013.02.016
   Web of Science ®Google Scholar
• X.-G. Liu and N. Zhao, Linearization estimates of the backward errors for least squares problems, Numer. Linear Algebra Appl. 19(6) (2012), pp. 954–969. doi: 10.1002/nla.827
   Web of Science ®Google Scholar
• A.N. Malyshev, Optimal backward perturbation bounds for the LSS problem, BIT Numer. Math. 41(2) (2001), pp. 430–432. doi: 10.1023/A:1021954809777
   Web of Science ®Google Scholar
• A.N. Malyshev, A unified theory of conditioning for linear least squares and Tikhonov regularization solutions, SIAM J. Matrix Anal. Appl. 24(4) (2003), pp. 1186–1196 (electronic). doi: 10.1137/S0895479801389564
   Web of Science ®Google Scholar
• N. Mastronardi and P. Van Dooren, The antitriangular factorization of symmetric matrices, SIAM J. Matrix Anal. Appl. 34(1) (2013), pp. 173–196. doi: 10.1137/110858860
   Web of Science ®Google Scholar
• N. Mastronardi and P. Van Dooren, An algorithm for solving the indefinite least squares problem with equality constraints, BIT Numer. Math. 54(1) (2014), pp. 201–218. doi: 10.1007/s10543-013-0452-2
   Web of Science ®Google Scholar
• J.R. Rice, A theory of condition, SIAM J. Numer. Anal. 3 (1966), pp. 287–310. doi: 10.1137/0703023
   Google Scholar
• A.H. Sayed, B. Hassibi, and T. Kailath, Inertia properties of indefinite quadratic forms, IEEE Signal Process. Lett. 3(2) (1996), pp. 57–59. doi: 10.1109/97.484217
   Web of Science ®Google Scholar
• R.D. Skeel, Scaling for numerical stability in Gaussian elimination, J. ACM 26(3) (1979), pp. 494–526. doi: 10.1145/322139.322148
   Web of Science ®Google Scholar
• G.W. Stewart, Research, development, and LINPACK, in Mathematical Software, III (Proc. Sympos., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1977), Publ. Math. Res. Center, No. 39, Academic Press, New York, 1977, pp. 1–14.
   Google Scholar
• S. Van Huffel and J. Vandewalle, The Total Least Squares Problem, Frontiers in Applied Mathematics, Vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1991. Computational aspects and analysis, With a foreword by Gene H. Golub.
   Google Scholar
• B. Waldén, R. Karlson, and J.G. Sun, Optimal backward perturbation bounds for the linear least squares problem, Numer. Linear Algebra Appl. 2(3) (1995), pp. 271–286. doi: 10.1002/nla.1680020308
   Web of Science ®Google Scholar
• Q. Wang, Perturbation analysis for generalized indefinite least squares problems, J. East China Norm. Univ. Natur. Sci. Ed. 2009(4) (2009), pp. 47–53.
   Google Scholar
• H. Xu, A backward stable hyperbolic QR factorization method for solving indefinite least squares problem, J. Shanghai Univ. 8 (2004), pp. 391–396. doi: 10.1007/s11741-004-0049-8
   Google Scholar
• T.-Y. Zhou, On the condition number and backward error analysis for indefinite linear least squares problems, Master's thesis, Northeast Normal University, May 2015, in Chinese.
   Google Scholar