Consider the overdetermined linear system , where and , and the total least squares (TLS) problem can be formulated as (see  )
However, in many linear parameter estimation problems, the error of data matrix A on the left side of the approximate system may be scaled. In order to maximize the accuracy of the estimated parameters x, the case where the scaling factor is used to weight some columns of error matrix in data matrix A is naturally considered when estimating parameters x using the TLS approach. From the point of view, Liu, Wei and Chen  proposed the concept of the matrix-scaled total least squares (MSTLS) problem with single right-hand side in 2019. Inspired by , Liu, Wei and Chen  transformed the MSTLS problem with single right-hand side into the weighted TLS (WTLS) problem.
As a continuation of their work, we extend the MSTLS problem with single right-hand side to multiple right-hand sides as follows.
where , , , and .
When , our model (2) degenerates to the single right-hand case.
The condition number is a measure of the sensitivity of the solution to input data perturbation. Therefore, condition numbers play an important role in numerical analysis. Many scholars have studied the TLS problem with multiple right-hand sides:      studied the sufficient conditions or/and necessary conditions for its solvability. When the TLS problem is solvable, Huang, Yan and Yu discussed the solution set and minimal norm solution of the TLS problem, see  . Recently, based on singular value decomposition (SVD) of augmented matrix, many scholars have discussed the solution set and minimal norm solution of the TLS problem. In , Hnětynková et al. proposed the TLS problem with multiple right-hand sides, and gave the conditions for the existence and expression of the solutions. In , Hnětynková et al. extended the concept of the core problem of the TLS problem with single right-hand side proposed by Paige and Strakoš in  to the TLS problem with multiple right-hand sides. The perturbation analysis of the solution of the TLS problem with multiple right-hand sides can be found in references     . Zheng, Meng and Wei gave the exact expressions and their upper bounds of normwise, mixed and componentwise condition numbers of TLS problem with multiple right-hand sides in  . These results extend the condition number theory of TLS problem with single right-hand side. In addition, by making use of the perturbation results in the above references, Liu et al.   derived closed formulae for condition numbers of the total least squares problem with linear equality constraint problem.
As far as we know, the perturbation analysis of the MSTLS problem has not been systematically performed in literature. In this paper, we consider the perturbation analysis of the MSTLS problem (2). The relative normwise condition number, the mixed condition number and the componentwise condition number are derived. Our analysis can be seen as a unified treatment of the mentioned approaches in  and .
Throughout this paper, for given positive integers m and n, we denote by the space of all real matrices, and stands for the identity matrix of order n. , and denote the 2-norm, ∞-norm, and Frobenius norm of their arguments, respectively. Given a matrix , , , and denote the “max” norm given by , the transpose, the Moore-Penrose inverse and the i-th largest singular value of X, respectively. is the absolute value of the matrix X, whose entries are . Moreover, for , , is an entry-wise division; that is, , or Y./Z in Matlab notation. Here, ξ/0 is interpreted as zero if and otherwise. For matrices , and denotes the Kronecker product of A and any matrix B. Let , where has an entry 1 in position and all other entries are zeros.
The organization of this paper is as follows. In Section 2, we present some necessary preliminaries, including the explicit expression for minimum -norm MSTLS solution under some mild conditions and some important lemmas. In Section 3, we derive the normwise, mixed and componentwise condition numbers and their computable upper bounds of the MSTLS solution. All these results can reduce to those of the TLS problem which were given in . Two numerical examples are tested in Section 4 to demonstrate the tightness of the derived upper bounds. Some concluding remarks are given in Section 5. In the appendix, we present a power method for calculating the normwise condition number of the MSTLS solution similar to the one in .
In this section, we give an explicit expression for the minimum -norm solution of the MSTLS problem with multiple right-hand sides (2) under some mild conditions.
Along the similar lines as in  , we can see that (2) is equivalent to the following WTLS model:
where . Let
and the SVD of be
where , , , , and .
The following theorem gives the minimum -norm solution of (2).
Theorem 2.1 Let the SVD of be given as in (4). If
thenthe MSTLS problem with multiple right-hand sides (2) has the minimum -norm solution:
wherethe weighted -norm is defined by .
Proof. By ( , (2.3)), we can get the minimum F-norm solution to (3) under the condition (5):
which leads to the minimum -norm solution of (2)
Therefore, we complete the proof.
In this paper, all discussions are based on the solvability conditions (5). Next we give some lemmas which will be used in the next analysis.
Lemma 2.1 ( , Chapt. 2) Let , , . Then
If an orthogonal matrix of size n is partitioned into a block form, some interesting connections and properties among these four submatrix blocks are provided in the lemma below.
Lemma 2.2 ( , Lemma 2.1) Let be an n-by-n orthogonal matrix with a 2-by-2 partitioning. Then
1) has full column (row)rank if and only if has full row (column) rank;
2) , , .
Since the MSTLS solution is closely related to the matrix V of right singular vectors of augmented matrix, the first-order perturbation analysis of V will play an important role in next discussions. The next lemma gives the first-order perturbation analysis of V.
Lemma 2.3 ( , Lemma 2.2) Let have the SVD in (4) with and be sufficiently small. Define
Then the matrix of right singular vectors of satisfies
where is given by
Moreover, if has full row (column)rank,then has full row (column) rank.
3. Condition Numbers of XMSTLS
Let and , where and are the perturbations of the input data A and B, respectively.
Consider the perturbed MSTLS problem with multiple right-hand sides
Similarly, (7) is also treated as a perturbed WTLS problem. Let , and the SVD of be
where , and are partitioned as in U, and V in (4), respectively.
When the norm of the perturbations is sufficiently small, then perturbation analysis of singular values can ensure that the perturbed MSTLS problem with multiple right-hand sides (7) has the minimum -norm solution:
Let . Now we introduce definitions of the normwise, mixed and componentwise condition numbers for as follows.
Definition 3.1 The absolute normwise condition number for is defined by
therelative normwise condition number for is defined by
themixed condition number for is defined by
andthe componentwise condition number for is defined by
Definition 3.1 only provides general descriptions of the various condition numbers. It is usually hard to give their exact computable formulae. However, if is a differentiable function with respect to the data, the condition numbers defined in Definition 3.1 can be exactly expressed in derivatives. We start from the differentiability of .
Let the SVD of the matrices be given as in (4). To derive the exact formulae of the condition numbers of , we define the mapping by
where . It follows from Lemma 2.3 that is continuous in a neighborhood of c. Using the definitions of the condition numbers of the mapping at a fixed point c   , and following   , if is Fréchet differentiable in a neighborhood of c, we have
where denotes the Fréchet derivative of at point c.
Before deriving the explicit expression for condition numbers, we give a useful lemma which proves that is Fréchet differentiable in a neighborhood of and gives the explicit expression for .
Lemma 3.1 Under conditions (5), the mapping defined above is continuous and Fréchet differentiable at . Moreover, its Fréchet derivative has the expression
inwhich R and S are defined as in Lemma 2.3,and
Proof. We only prove the second statement since the first part is trivial. According to Lemma 2.3, it follows that there exists a proper matrix P such that
Since has full row rank by Lemma 2.3, we have
Using Lemma 2.2 and only retaining the first-order terms give
which together with Lemma 2.1 and Lemma 2.3 leads to
Consequently, the Fréchet derivative of at is given by
which gives the desired result.
3.1. Normwise Condition Numbers
Next, we present the absolute and relative normwise condition numbers of .
Theorem 3.1 Let R be defined as in Lemma 2.3, and be defined as in Lemma 3.1. Under conditions (5), we have
Proof. By (14), (15), Lemma 3.1 and the fact that , the desired results are easily obtained.
Remark 3.1 Taking , our results in (19) and (20) reduce to those of the solution to TLS problem with multiple right-hand sides in ( , Theorem 3.3), respectively.
Computing and reduces to computing the spectral norm of matrix . It should be noted that the Kronecker product enlarges the size of the matrix when m and n are large, so it impossible to explicitly form and store the high dimensions matrix. Along the similar lines as in ( , Algorithm 1), we also adopt the iterative technique based on the power method ( , p. 289) to eliminate the influence of the Kronecker product. We include it as an appendix.
In many applications, an upper bound would be sufficient to estimate the normwise condition number of the MSTLS solution. We next present the upper bounds for and , which only involve the singular values and of . Such bounds are particularly appealing for large-scale MSTLS problem.
Theorem 3.2 Using the notation above, we have the upper bounds for the absolute and relative normwise condition numbers of as follows:
where and are singular values of .
Proof. According to Lemma 2.1 and Theorem 3.1, we use the CS decomposition ( , Theorem 2.6.3) and the property of 2-norm to follow a path similar to the proof in ( , Theorem 3.6), the corresponding results can be proved.
Remark 3.2 Taking , our result (21) reduces to that of the TLS problem with multiple right-hand sides in ( , Theorem 3.6).
Note that and when , and we can get the following corollary about the normwise condition numbers and their upper bounds for the MSTLS problem with single right-hand side by Theorems 3.1 and 3.2.
Corollary 3.1 Consider the MSTLS problem with single-hand side, if and , we have
wherex is the minimum -norm solution of the MSTLS problem with single right-hand side.
Remark 3.3 Taking , our results in (23) reduce to those of the TLS problem with single right-hand side in ( , Corollaries 3.4 and 3.8).
3.2. Mixed and Componentwise Condition Numbers
When the data are badly scaled and sparse, normwise condition numbers allow large relative perturbations on small entries and may give overestimated bounds. Instead of measuring perturbations by norms, a componentwise condition number is more suitable because it measures perturbation errors for each component of the input data . Therefore, the mixed, componentwise condition numbers for the MSTLS problem are worth studying. In the following theorem, we present the mixed and componentwise condition numbers of the MSTLS problem.
Theorem 3.3 Using the notation above, we have the mixed and componentwise condition numbers of the MSTLS solution as follows:
Proof. The proof can easily be obtained by (16), (17) and Lemma 3.1, so we omit it here.
Remark 3.4 Taking , our results in Theorem 3.3 reduce to those of the TLS problem with multiple right-hand sides in ( , Theorem 3.11).
The expressions of the condition numbers in Theorem 3.3 involve permutation matrix (or ) and extensive computation of Kronecker products, so it is not easy to use these expressions to calculate the condition number directly, which is impractical for large-scale problem. Similarly, we also give upper bounds for the mixed and componentwise condition numbers of the MSTLS problem, respectively.
Theorem 3.4 Using the notation above, we have the upper bounds for the mixed and componentwise condition numbers of the MSTLS solution as follows:
where has the i-th column
Proof. According to Theorem 3.3 and Lemma 2.1, we have
which together with (25), (26) leads to (27) and (28), respectively.
Remark 3.5 Taking , our results in Theorem 3.4 reduce to those of the TLS problem with multiple right-hand sides in ( , Theorem 3.12).
4. Numerical Experiments
In this section, we present three numerical experiments to illustrate that the tightness of the upper bound estimates on the absolute normwise, mixed and componentwise condition numbers of the MSTLS solution and the operability of Algorithm 1, respectively. All of the following numerical experiments are performed via MATLAB R2014b in a laptop with AMD A10-7300 Radeon R6, 10 Compute Cores 4C + 6G by using double precision. Each figure in the following tables is the average of 500 experiments.
Example 4.1 Let
and be given by its SVD decomposition
where and U is an arbitrary 4-by-4 orthogonal matrix. This example is inspired by ( , Example 3.7).
We partition the unitary matrix V:
We know and . Hence the approximate linear system (2) has the MSTLS solutions and the normwise condition number of its minimum -norm solution satisfies Table 1, which means that the upper bound can be reached and therefore is optimal.
Example 4.2 Let
with and being arbitrary orthogonal matrices and . We choose such that and , where , , E, and F have entries from the standard normal distribution such that and with .
This example is a modification from  and Zheng et al. ( , Example 5.2) used the similar example to compare the mixed and componentwise condition numbers with their corresponding upper bounds of the TLS problem with multiple right-hand sides. Next, we will show the exact condition numbers of and its upper bounds when , respectively.
As shown in Table 2 and Table 3, we can see that the upper bounds are at most two orders of magnitude larger than the corresponding exact condition number. That is, the upper bounds in Theorem 3.4 can estimate their corresponding condition numbers well.
Example 4.3 Let be given as in Example 4.1. Take , and , , , respectively.
The quantity measures the distance of our problem to nongenericity, and we have in exact arithmetic . Then by varying , we can generate different MSTLS problems, and by considering values of , it is possible to study the behavior of the MSTLS condition number in the context of close-to-nongeneric problems. Firstly, we compare in Table 4 the exact condition number given in Theorem 3.1, the upper bound given in Theorem 3.2. We also report the condition number computed by Algorithm 1, denoted by , and the corresponding number of power iterations (the algorithm terminates when the difference between two successive values is lower than 10−12).
Table 1. Comparison of condition number and its upper bound with different .
Table 2. Comparison of condition number and its upper bound with different .
Table 3. Comparison of condition number and its upper bound with different .
Table 4. MSTLS conditioning for several values of .
From Table 4, we observe that the upper bounds of the condition numbers are sharp although there may be a factor between the exact absolute normwise condition number and its upper bound sometimes. is always equal or very close to .
In this paper, we are concerned with the matrix-scaled total least squares (MSTLS) problem with multiple right-hand sides. To our best knowledge, the condition numbers of the MSTLS problem have so far not been considered systematically. Based on this view, we focus on the normwise, mixed and componentwise condition numbers of the MSTLS problem under some mild conditions, respectively. Then the tight and computable upper bound estimates are provided. Numerical examples are given to illustrate the tightness of these bounds. In addition, large-scale problems are more interesting, we can make efforts on computational issues associated with these problems, possibly with additional structures (like sparseness) for the defining matrices. This will be a good research direction in the future.
The authors are grateful to the anonymous referees and the Editor for their detailed and helpful comments that led to a substantial improvement to the paper.
Longyan Li is supported by the Research and Training Program for College Students (No. A2020-17).
Denote . This algorithm involves, however, the computation of the products of H by a vector and by a vector . We describe now how to perform the two operations.
Let with , , and . It follows from Lemma 2.2 that
which together with Lemma 2.1 and the fact that gives
where with the i-th column
Similarly, let and . Then we have
where with the i-th column
Using (29) and (30), we can now write in Algorithm 1 the iteration of the power method ( , p. 289) to compute the absolute and relative normwise condition numbers and of . In this algorithm we assume and the SVD of are available.
 Liu, Q., Wei, M. and Chen, C. (2020) A Note on the Matrix-Scaled Total Least Squares Problems with Multiple Solutions. Applied Mathematics Letters, 103, Article ID: 106181.
 Van Huffel, S. and Vandewalle, J. (1988) Analysis and Solution of the Nongeneric Total Least Squares Problem. SIAM Journal on Matrix Analysis and Applications, 9, 360-372.
 Van Huffel, S. and Vandewalle, J. (1991) The Total Least Squares Problem: Computational Aspects and Analysis. Society for Industrial and Applied Mathematics, Philadelphia.
 Yan, S. and Huang, K. (2000) The Original TLS Solution Sets of the Multidimensional TLS Problem. International Journal of Computer Mathematics, 73, 349-359.
 Hnětynková, I., Plešinger, M., Maria Sima, D., Strakoš, Z. and Van Huffel, S. (2011) The Total Least Squares Problem in AX ≈ B: A New Classification with the Relationship to the Classical Works. SIAM Journal on Matrix Analysis and Applications, 32, 748-770.
 Hnětynková, I., Plešinger, M. and Strakoš, Z. (2013) The Core Problem within a Linear Approximation Problem AX ≈ B with Multiple Right-Hand Sides. SIAM Journal on Matrix Analysis and Applications, 34, 917-931.
 Fierro, R.D. and Bunch, J.R. (1996) Perturbation Theory for Orthogonal Projection Methods with Applications to Least Squares and Total Least Squares. Linear Algebra and Its Applications, 234, 71-96.
 Zheng, B., Meng, L. and Wei, Y. (2017) Condition Numbers of the Multidimensional Total Least Squares Problem. SIAM Journal on Matrix Analysis and Applications, 38, 924-948.
 Meng, L., Zheng, B. and Wei, Y. (2020) Condition Numbers of the Multidimensional Total Least Squares Problems Having More Than One Solution. Numer. Algorithms, 84, 887-908.
 Gratton, S., Titley-Peloquin, D. and Ilunga, J.T. (2013) Sensitivity and Conditioning of the Truncated Total Least Squares Solution. SIAM Journal on Matrix Analysis and Applications, 34, 1257-1276.
 Xie, Z.J., Li, W. and Jin, X.Q. (2013) On Condition Numbers for the Canonical Generalized Polar Decompostion of Real Matrices. The Electronic Journal of Linear Algebra, 26, 842-857.
 Baboulin, M. and Gratton, S. (2011) A Contribution to the Conditioning of the Total Least-Squares Problem. SIAM Journal on Matrix Analysis and Applications, 32, 685-699.