×

Perturbation analysis and condition numbers of scaled total least squares problems. (English) Zbl 1171.65031

Scaled total least squares (STLS) is a generalization of total least squares (TLS). The problem is to approximate the solution \(x\) of the linear system \(Ax=b\) by \(y\), satisfying \((A+E)y=\lambda b-r\). Here \([r~E]\) is the minimal perturbation (minimal in Frobenius norm \(\|r~E\|_F\)), needed to make the latter system solvable. The scaling parameter \(\lambda\) is positive. TLS is a special case corresponding to \(\lambda=1\).
First properties of TLS are recalled and used to show when STLS has a unique solution. Then a sharp, but impractical, relative condition number (in 2-norm) for the STLS problem is derived. However, it implies that the gap \(\hat{\sigma}_n-\sigma_{n+1}\) (assumed positive) with \(\hat{\sigma}_n\) and \(\sigma_{n+1}\) the smallest singular values of \(A\) and \([A~\lambda b]\) respectively is the essential determining element. The larger the gap, the better the condition. Similarly relative condition numbers in \(\infty\)-norm, both mixed (ratio of norms) and componentwise (norm of componentwise ratios) are obtained.

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F22 Ill-posedness and regularization problems in numerical linear algebra

Software:

mctoolbox; VanHuffel
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ben-Israel, A., Greville, T.N.E.: Generalized Inverses: Theory and Applications, 2nd edn. Springer, New York (2003) · Zbl 1026.15004
[2] 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 · doi:10.1090/S0025-5718-06-01913-2
[3] Fierro, R.D., Bunch, J.R.: Perturbation theory for orthogonal projection methods with applications to least squares and total least squares. Linear Algebra Appl. 234, 71–96 (1996) · Zbl 0843.65027 · doi:10.1016/0024-3795(94)00209-6
[4] Gohberg, I., Koltracht, I.: Mixed, componentwise, and structured condition numbers. SIAM J. Matrix Anal. Appl. 14, 688–704 (1993) · Zbl 0780.15004 · doi:10.1137/0614049
[5] 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 · doi:10.1137/0717073
[6] Graham, A.: Kronecker Products and Matrix Calculus with Application. Wiley, New York (1981) · Zbl 0497.26005
[7] Higham, N.J.: Accuracy, Stability of Numerical Algorithms, 2nd edn. SIAM, Philadelphia (2002) · Zbl 1011.65010
[8] Higham, N.J.: A survey of componentwise perturbation theory in numerical linear algebra. Proc. Symp. Appl. Math. 48, 49–77 (1994) · Zbl 0815.65062
[9] Hnětynková, I., Strakoš, Z.: Lanczos tridiagonalization and core problems. Linear Algebra Appl. 421, 243–251 (2007) · Zbl 1111.65041 · doi:10.1016/j.laa.2006.05.006
[10] Kukush, A., Markovsky, I., Van Huffel, S.: Consistency of the structured total least squares estimator in a multivariate errors-in-variables model. J. Stat. Plan. Inference 133, 315–358 (2005) · Zbl 1213.62097 · doi:10.1016/j.jspi.2003.12.020
[11] Kukush, A., Van Huffel, S.: Consistency of elementwise-weighted total least squares estimator in a multivariate errors-in-variables model AX=B. Metrika 59, 75–97 (2004) · Zbl 1062.62100 · doi:10.1007/s001840300272
[12] Liu, X.: On the solvability and perturbation analysis for tatal least squares problem. Acta Math. Appl. Sin. 19, 254–262 (1996) (in Chinese) · Zbl 0858.65042
[13] Markovsky, I., Rastello, M.L., Premoli, A., Kukush, A., Van Huffel, S.: The element-wise weighted total least-squares problem. Comput. Stat. Data Anal. 50, 181–209 (2006) · Zbl 1429.62298 · doi:10.1016/j.csda.2004.07.014
[14] Markovsky, I., Van Huffel, S.: Overview of total least-squares methods. Signal Process. 87, 2283–2302 (2007) · Zbl 1186.94229 · doi:10.1016/j.sigpro.2007.04.004
[15] Paige, C.C., Strakoš, Z.: Bounds for the least squares distance using scaled total least squares. Numer. Math. 91, 93–115 (2002) · Zbl 0998.65045 · doi:10.1007/s002110100317
[16] Paige, C.C., Strakoš, Z.: Scaled total least squares fundamentals. Numer. Math. 91, 117–146 (2002) · Zbl 0998.65046 · doi:10.1007/s002110100314
[17] Paige, C.C., Strakoš, Z.: Core problems in linear algebraic systems. SIAM J. Matrix Anal. Appl. 27, 861–875 (2006) · Zbl 1097.15003 · doi:10.1137/040616991
[18] Rao, B.D.: Unified treatment of LS, TLS and truncated SVD methods using a weighted TLS framework. In: Van Huffel, S. (ed.) Recent Advances in Total Least Squares Techniques and Errors-in-Variables Modeling, pp. 11–20. SIAM, Philadelphia (1997) · Zbl 0892.62054
[19] Rohn, J.: New condition numbers for matrices and linear systems. Computing 41, 167–169 (1989) · Zbl 0665.65042 · doi:10.1007/BF02238741
[20] Skeel, R.D.: Scaling for numerical stability in Gaussian elimination. J. Assoc. Comput. Math. 26, 167–169 (1979) · Zbl 0435.65035
[21] Stewart, G.W.: A second order perturbation expansion for small singular values. Linear Algebra Appl. 56, 231–235 (1984) · Zbl 0532.15008 · doi:10.1016/0024-3795(84)90128-9
[22] Sun, J.-G.: A note on simple non-zero singular values. J. Comput. Math. 6, 258–266 (1988) · Zbl 0662.15008
[23] Van Huffel, S.: Analysis of the total least squares problem and its use in parameter estimation. Dissertation, ESAT Lab., Dept. Electr. Eng., K.U. Leuven (1987)
[24] Van Huffel, S.: On the significance of nongeneric total least squares problems. SIAM J. Matrix Anal. Appl. 13, 20–35 (1992) · Zbl 0763.65028 · doi:10.1137/0613004
[25] Van Huffel, S., Vandewalle, J.: Analysis and solution of the nongeneric total least squares problems. SIAM J. Matrix Anal. Appl. 9, 360–372 (1988) · Zbl 0664.65036 · doi:10.1137/0609030
[26] Van Huffel, S., Vandewalle, J.: Analysis and properties of the generalized total least squares problems AXB when some or all columns in A are subject to error. SIAM J. Matrix Anal. Appl. 10, 294–315 (1989) · Zbl 0681.65025 · doi:10.1137/0610023
[27] 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 · doi:10.1007/BF01396047
[28] Van Huffel, S., Vandewalle, J.: The Total Least Squares Problem: Computational Aspects and Analysis. SIAM, Philadelphia (1991) · Zbl 0789.62054
[29] Van Huffel, S., Zha, H.: The restricted total least squares problem: formulation, algorithm, and properties. SIAM J. Matrix Anal. Appl. 12, 292–309 (1991) · Zbl 0732.65041 · doi:10.1137/0612021
[30] Wang, G., Wei, Y., Qiao, S.: Generalized Inverses: Theory and Computations. Science, Beijing (2004) · Zbl 1395.15002
[31] Wei, M.: The analysis for the total least squares problem with more than one solution. SIAM J. Matrix Anal. Appl. 13, 746–763 (1992) · Zbl 0758.65039 · doi:10.1137/0613047
[32] Wei, M.: On the perturbation of the LS and TLS problems. Math. Numer. Sinica 20(3), 267–278 (1998) (in Chinese) · Zbl 0910.65021
[33] Wilkinson, J.H.: The Algebraic Eigenvalue Problem. Oxford University Press, London (1965) · Zbl 0258.65037
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.