{'fraction_non_alphanumeric': 0.060596432299940994, 'fraction_numerical': 0.024057010576006538, 'mean_word_length': 3.98236092265943, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Condition numbers of the mixed least squares-total least squares problem: revisited

A new closed formula for the first order perturbation estimate of the mixed least squares-total least squares (MTLS) solution is presented. It is mathematically equivalent to the one by Zheng and Yang(Numer. Linear Algebra Appl. 2019; 26(4):e2239). With this formula, general and structured normwise, mixed and componentwise condition numbers of the MTLS problem are derived. Perturbation bounds based on the normwise condition number, and compact forms for the upper bounds of mixed and componentwise condition numbers are also given in order for economic storage and efficient computation. It is shown that the condition numbers and perturbation bound of the TLS problem are unified in the ones of the MTLS problem.


Introduction
Consider the overdetermined linear system where A ∈ R m×n , b ∈ R m , m ≥ n, and the matrix A has full column-rank. In some engineering applications, the matrix A and the observation b are contaminated by some noise, and the total least squares (TLS) model [2,10] is often used to find best approximations to them in Frobenius norm such that The vector x = x TLS satisfying (1.1) is called the TLS solution. If some of rows of [A, b] are free of error and some rows in [E, f ] are set zero, the corresponding problem reduces to the total least squares problem with equality constraint [17,18]. If some columns of A are known exactly, and some columns in E, say, the first n 1 columns of E are set to be zero, then the corresponding problem (1.1) is known as the mixed least-squares and total least squares (MTLS) problem [19,21,29]. It arises in the regression analysis [8], system identification [23] and signal processing [25], etc. The solution to the MTLS problem is denoted by x M . Usually we assume that Ax = b is not consistent, otherwise the best minimizer for [E, f ] in (1.1) is taken to be a zero matrix. For TLS problems with small or medium size, a classical direct solver is based on the singular value decomposition (SVD) [2,10,11,24,28], where the solution is obtained from the right singular vector corresponding to the smallest singular value of [A, b]. For the MTLS problem, QR combined with SVD can be adopted, see e.g., [24]. Recently Liu and Wang [19] proposed the method of weighting to interpret the MTLS solution as a limit of the solution to an unconstrained weighted TLS (WTLS) problem, as the positive parameter in the weight matrix tends to zero. For the solution of problem WTLS, it is convenient to apply all known TLS theories and algorithms on it. Based on this observation, a QR factorization-based inverse iteration and a Rayleigh quotient iteration method were presented in [19]. The superiority of these methods over the standard QR-SVD algorithm was demonstrated by numerical experiments.
The condition number is fundamental since it measures the worst-case sensitivity of its solution to small perturbations in the input data. The condition numbers of TLS and its extension the scaled TLS (STLS) problem, by minimizing [E, λf ] F instead in (1.1), have been studied widely, e.g. by Zhou et al. [33], Baboulin and Gratton [1], Li and Jia [16,14], Wang et al. [26], based on which the explicit expression of the normwise condition number are given. In [27], Xie et al. provided the perturbation bound for the TLS problem and they also proved that the explicit expression for the absolute normwise condition number in [33,1,16] are equivalent since they have the same value of the 2-norm. Mixed and componentwise condition numbers for a linear function of the solution of the TLS problem were further studied in [5]. In [31,20], Zheng et al. and Meng et al. studied the condition numbers of multidimensional TLS problems.
Based on the weighting method for problem MTLS [19] and the technique [1] for the conditioning of the standard TLS problem, Zheng and Yang [32] studied the closed formula for the first order perturbation estimate of the MTLS solution and gave the explicit expressions for the condition number of the MTLS problem. In this paper, we revisit the condition numbers of the MTLS problem. We derive another different closed formula for the first order perturbation estimate of the MTLS solution, and reveal that the formula is equivalent to that in [32], which also implies the equivalence of the first order perturbation estimates for the TLS problem in [1,16]. General and structured normwise, mixed and componentwise condition numbers and structured condition numbers are investigated. We also present the perturbation bound and compact form for the condition numbers to be computable more efficiently with less storage. Numerical tests are given to illustrate our theoretical results.
Before our discussion, some notations are required. R m and R m×n denote the spaces of m × 1 and m × n real matrices, respectively. I n denotes the n × n identity matrix. O m×n and O n denote m × n and n × n zero matrix, respectively. If subscripts are ignored, the sizes of identity and zero matrices are suitable with context. · 2 , · ∞ and · F denote 2-norm, ∞-norm and Frobenius norm of their arguments, respectively. For a matrix A, |A| is a matrix by taking the absolute value of a ij as elements, A T is the transpose of A, a j is a Matlab notation that denotes the jth column of A and σ i (A) is the i-th largest singular value of A; vec(A) is an operator, which stacks the columns of A one underneath the other. For matrices A and B, the Kronecker product [15] of A and B is defined by A ⊗ B = [a ij B] and its property is listed as follows [15,12]: Let x = φ(a) be a continuous and Fréchet differentiable mapping from R p to R q . For small perturbations δa, denote δx = φ(a + δa) − φ(a). According to [7,9,22], the general normwise condition number κ(φ, a), mixed condition number m(φ, a) and componentwise condition number c(φ, a) are defined and formulated as follows: where φ(a) = 0, φ′(a) denotes the Fréchet derivative [7,22] of φ at the point a and b/a is the entry-wise division. Note that ξ/0 is interpreted as zero if ξ = 0 and infinity otherwise. We assume that a and φ(a) have no zero entries throughout this paper.

A new perturbation estimate of the MTLS solution
For the MTLS problem [24], we assume that the first n 1 columns of A are known exactly.
T be conformal with the context. Then the MTLS problem can be formulated as min To solve MTLS , a standard way is to factorize [A, b] into the QR form first: then solve the reduced TLS problem R 22 x 2 ≈ R 2b to obtain x 2 . The vector x 1 is then solved from R 11 x 1 = R 1b − R 12 x 2 by backward substitution. According to Golub-Van Loan's theory for standard TLS [10], if the genericity condition holds, the reduced TLS problem and therefore the MTLS problem have a unique solution. Lemma 1 [19]For the MTLS problem (2.1), letÃ = [A, b], W = diag(O n 1 , I n 2 ), andW = diag(W, 1). Then the MTLS solution x M satisfies the generalized eigenvalue system then the MTLS problem (2.1) has a unique solution determined by x M = (A T A−σ 2 n 2 +1 W ) −1 A T b, and it is equivalent to solving the following optimization problem Consider the mapping ϕ : where A and b are input data of the MTLS problem. Let a := vec([A b]), then we have the vector representation According to the definitions and formulae of three condition numbers, it is vital to compute the Fréchet derivative of φ(a) for representing the condition numbers of the MTLS problem. To this end, letÂ = A + ∆A,b = b + ∆b, where ∆A and ∆b denote the perturbations to A and b respectively. Consider the perturbed MTLS problem In [32], Zheng and Yang proved that where x is the exact MTLS solution, P = (A T A − σ 2 n 2 +1 W ), D = P −1 (A T − 2 W xr T γ ) with r = Ax − b,γ = 1 + x T W x and Π m,n is a vec-permutation matrix such that vec(C T ) = Π m,n vec(C) where C is an arbitrary m × n matrix. Based on this, they proved that We will adopt a different technique from that in [32] to derive a new closed formula of the perturbation estimate. It is clear that when [∆A, ∆b] F is sufficiently small, the perturbed MTLS problem has a unique solutionx such thatx is a real analytic function of vec([∆A, ∆b]) in some neighborhood of the origin. The following theorem presents a closed formula for the solution of the perturbed problem (2.6), by a similar technique to the one in [16].
and [∆A, ∆b] F is sufficiently small, then the perturbed problem (2.6) has a unique MTLS solutionx. Moreover, Proof. For convenience, let ε = vec([∆A, ∆b]), and x(ε) be the MTLS solution of the perturbed problem (2.6). Similar to (2.5), we can get It is clear that x(0) = x * , and for sufficiently small ε, x(ε) is real analytic in some neighborhood of the origin. Thus, the Taylor series of x(ε) with center the origin converges when ε is small enough. So, to prove (2.9) it suffices to prove ∇ ε x(0), the Jacobian of x(ε) at the origin, equals K. To this end, define the two-variable function The necessary condition for it to obtain the minimum at x(ε) is Differentiating (2.11) by ε with the chain rule gives On the other hand, we note that forr =Âx −b, (2.14) and the fact that Combining this with (2.13) and (2.5), we get where r = Ax * − b. Substituting ε = 0, x = x * and (2.15) into (2.14), we obtain Then ∂G ∂x iŝ =â i , i = 1, · · · , n, and We obtain The proof of the theorem is then completed.
Theorem 2 For the first order perturbation estimate of the MTLS solution x, the formulae in (2.7) and (2.10) are equivalent.
Proof. We note that for any n × m matrix M 1 , where the matrix (P −1 A T H 0 ) is exactly the matrix D in (2.7) by the relation (2.15).
Note that for any m × n matrix Y , and the assertion in the theorem then follows.
Remark 1 When n 1 = 0, the MTLS problem (2.1) reduces to the standard TLS problem (1.1) and the first order perturbation estimates in (2.7) and (2.9) become the results in [1] and [16], respectively, which reveals the equivalence of the first order perturbation estimates in [1] and [16]. For n 2 = 0, the MTLS reduces to the LS problem, and the estimate in (2.7) is exactly the result from [4]. Therefore Theorem 1 unifies the results for the TLS problem and LS problem.

Condition numbers for the MTLS problem
In this section, we first consider condition numbers of the MTLS problem for general matrix A and b. Based on the first order estimate in Theorem 1, we also consider the structured condition numbers for some MTLS problems with linear structure.

Compact condition numbers and perturbation analysis
According to Theorem 1 and the concept of normwise condition number, we obtain φ′(a) = K and the 2-norm relative condition number of the MTLS problem is given by where K is defined in (2.10). Note that the expression of K involves Kronecker product, which might lead to expensive storage and computational cost. In order to simplify the normwise condition number of the MTLS problem, we present the following theorems.
Theorem 3 For the MTLS problem (2.1), under the genericity condition (2.3) or (2.4), the absolute condition number κ = K 2 of the solution x of the MTLS problem has the following equivalent forms Since P is symmetric, by (2.10) and withḠ = G(x), Γ = [I n , 0 n×1 ] ⊗ r T , we observē GḠ T = 1 + x 2 2 = γ, ΓΓ T = r 2 2 I n ,ḠΓ T = rx T , and the Householder matrix H 0 satisfies H 0 r = −r, we then get The relations (3.2) and (3.3) then follow from (2.15). Furthermore, where with P 0 = I m − 1 for i = 1, 2 and D 1 = diag([I m , x 2 P 0 ], r 2 I n ), Therefore with Z i = [A T , I n ]UD i , By applying the fact in (2.15), we obtain the estimates for P −1 Z 1 2 in (3.4) and P −1 Z 2 2 in (3.5). Proof Combined with the equality in (2.15) for n 1 = 0, the above estimate is just a special case of (3.4).
For the perturbation bound of the MTLS problem, the result in (3.8) is equivalent to Zheng and Yang's result in [32,Theorem 5], and it also includes the bound for the standard TLS problem as a special case, see [27,   vec(xy T D + P −1 yr T ) 2 2 + D T y 2 2 = max where D = P −1 A T H 0 by the relation (2.15) and 2 is equivalent to the estimate (3.3) for K 2 2 . We will provide numerical tests to compare our estimate with that in [32] to illustrate our results.
Remark 4 In (2.10), the matrix K is of size n × m(n + 1), while the associated matrices in (3.3)-(3.5) are of size n × n, n × (2m + n), n × (m + n) respectively, which is more economic in storage. From the aspect of computation efficiency, the advantages of (3.3) over (3.2) and (3.5) over (3.4) are obvious since they require less matrix-product operations. However, as pointed out in [1,13], the explicit formulation of matrix cross product A T A and P −1 in (3.3) is not expected. The formula in (3.5) is preferred in avoiding the matrix cross prodcut, where in terms of (2.2), its calculation can be implemented by making use of the intermediate results from solving the MTLS problem. For example, the inverse of P can be written as , say in the small or medium MTLS, the SVD of [R 22 , R 2b ] is available and S −1 can be computed cheaply based on SVD and the result in [6, Lemma 2]; and for solving large MTLS problems when Rayleigh quotient and preconditioned conjugate gradient (RQI-PCG) [3] method is used, an approximation of σ n+1 is available and the linear system (R T 22 R 22 −σ 2 n 2 +1 I)w = f can be efficiently solved based on preconditioned conjugate gradient method via two triangular linear systems in its each iteration step. The computation of P −1 based on triangular linear systems can therefore be efficiently computed and preserves better numerical stability [13, ch. 8].
According to the definition of the mixed and componentwise condition numbers, they can be formulated as where the calculation of m(A, b), c(A, b) involves the Kronecker-product which makes the storage and computation costly. In practical computations, the upper bounds below are alternations to improve the computation efficiency. The proof is straightforward. Theorem 5 Under the notation in Theorem 1, the mixed and componentwise condition numbers of the MTLS problem are bounded as (3.11)

Structured condition numbers
If the matrix A lies in a linear subspace S which consists of a class of structured matrices, then any matrices in S can be represented by a linear combination of a linearly independent , · · · , vec(S q )] and α = [α 1 , α 2 , · · · , α q ] T and by the statement in [16,Theorem 4.1], Φ struct A is column orthogonal and has full column rank, with at most one nonzero entry in each row.
Note that Based on (2.9), the first order perturbation result becomes ∆x = KΦ struct A,b ǫ+O( ǫ 2 2 ). According to the concept of condition numbers, the relative norwise, mixed and componentwise condition numbers for structured MTLS take following forms which is Kronecker product-free and can be computable more efficiently with less storage.

Numerical experiments
In this part, we first present numerical experiments to verify the utility of our first order perturbation results, and then compare three types of condition numbers from tests. All experiments are coded by MATLAB R2012b with machine precision 2.22 × 10 −16 and done on a PC with Intel Core i5-5200U CPU @ 2.20GHz and the memory is 4 GB. Example 1 Consider the estimation of the parameters in a transfer function model [30], given in its errors-in-variables form where u 0 (t) and y 0 (t) are the unmeasurable noise-free inputs and outputs, u(t) and y(t) the noisy measured inputs and outputs, while ∆u(t) and ∆y(t) represent all stochastic disturbances to the inputs and outputs, respectively; A(q −1 ) and B(q −1 ) are polynomials taking the form B(q −1 ) = b 1 q −1 + · · · + b n 1 q −n 1 , C(q −1 ) = 1 + c 1 q −1 + · · · + c n 2 q −n 2 , and q −1 is a backward shift operator such that q −1 y(t) = y(t − 1). In order to estimate the parameters in transfer function, we need to solve the approximate system φ(t) T x ≈ y(t), for t = 1, 2, · · · , N and φ(t) = [u(t − 1), · · · , u(t − n 1 ), −y(t − 1), · · · , −y(t − n 2 )] T , x = [b 1 , · · · , b n 1 , c 1 , · · · , c n 2 ] T , in which the entries u(j), y(j) with j ≤ 0 are set to be zero. This leads to the set of linear equations Ax ≈ z for with k 0 +1(≥ 1) and m being the starting point and the number of chosen samples for parameter estimation. In [25], Van Huffel and Vandewalle proposed the TLS model to solve the linear equation when the inputs u(t) and outputs y(t) are affected by the noise. When the inputs u(t) are noise-free, i.e. ∆u(t) = 0, the MTLS model should be used to solve the linear equation.
In our test, we assume that the inputs u(t) are noise-free and the outputs y(t) are affected by white noise with zero mean and variance 0.01. Take m = 30, n = 20, n 1 = 10 and k 0 = max(n 1 , n 2 ) = 10 and generate entrywise perturbation [∆A, ∆b] = ǫ · rand(m, n + 1) where ⊙ denotes the entrywise multiplication. Denote where K 0 ZY , K 0 are computed from formulae (2.7) and (2.10) respectively. For different ǫ and random perturbations, in Table 1 we compare the first order perturbation estimates in (2.7), (2.10) of the MTLS solution and the estimates in (2.8),(3.3) and (3.5) for the absolute normwise condition number.
In Table 1, we observe that for different parameter ǫ and perturbations, η ZY ∆x , η new ∆x are all of the magnitude O(ǫ 2 ), indicating the first order perturbation estimates in (2.7) and (2.10) are both correct. Among five methods for evaluating the normwise condition number K 2 or K ZY 2 , we find that four methods give the same value while the estimate via (2.8) does not match the true value of K ZY 2 in (2.7), which illustrates our theoretical results.

Example 2
In this example, we compare the relative error of the MTLS solution with the estimated upper bounds based on the normwise condition number or the perturbation bound in (3.8) as well. Firstly, we construct the random MTLS problems as follows. The coefficient matrices A and b are generated according to the QR factorization (2.2), where Q is a random orthogonal matrix, and [R 11 , R 12 , R 1b ] = triu(qr(rand(n 1 , n + 1))).
In Table 2, we listed the upper bounds for the relative forward error of the MTLS solution, where the CPU time for seconds to compute corresponding upper bounds is deplayed. It is observed from Table 2 that the computation ofκ 0 is much less efficient due to the large size of K, and the bound in (3.8) and upper bounds based onκ 4 are very tight and efficient.
Example 3 Consider the intercept model arising in the "errors in variables" regression model [8]: α + x 1 c 1 + · · · + x n c n = b, where b and c i are observed m × 1 vectors, α ∈ R m is the intercept vector of the linear model. The model gives rise to the overdetermined set of equations for 1 m = [1, · · · , 1] T and C = [c 1 , c 2 , · · · , c n ] ∈ R m×n , in which the first column of the left-hand side matrix is known exactly, leading to the mixed LS-TLS problem.
In this example, we choose b as a random vector, while for the matrix C, we consider the following two cases: (a) Take m = 6, n = 4 and where δ is a tiny positive parameter. Set A = [1 m , C] and in the perturbed MTLS problem, the first column of A is not perturbed, and the matrix C is perturbed according to its structure, i.e., [∆C, ∆b] = 10 −10 · rand(m, n + 1) ⊙ [C, b].
In Table 3, we compare the relative perturbations ∆x 2 x 2 , ∆x ∞ x ∞ and ∆x x ∞ with the backward error multiplied by our normwise condition number, the upper bounds in (3.10)-(3.11) (denoted by m u , c u , resp.) of mixed and componentwise condition numbers (denoted by m, c, resp.). The tabulated results show that the normwise condition number multiplied by backward error is far from the true value of relative error of the solution when δ decreases, while the mixed and componentwise condition numbers based bounds can estimate the forward error much more tightly. Moreover, the upper bounds of mixed and componentwise condition numbers are very sharp but with less matrix operations.
(b) Take C = T to be a large m × (m − 2ω) Toeplitz matrix, whose first column is given by t i,1 = i for i = 1, 2, · · · , 2ω + 1, and zero otherwise. Entries in the first row are given by t 1,j = t 1,1 if j = 1, and zero otherwise.
The tabulated results in Table 4 show that for evaluating the forward error ∆x 2 x 2 of large MTLS problems, the estimates based on structured normwise condition numbers are tighter than those based on unstructured ones, but both become worse when the matrix [A, b] becomes badly scaled. The estimates based on general and structured mixed or componentwise condition number are sharp to evaluate ∆x ∞ x ∞ or ∆x x ∞ , they are only one or two orders of magnitude higher than corresponding relative forward errors, indicating that mixed and componentwise condition numbers are more robust and preferred for badly scaled problems.

Conclusion
In this paper, we present a new closed formula for the first order perturbation estimate of the MTLS solution, which is also illustrated to be equivalent to that in [32]. Normwise, mixed/componentwise condition numbers and corresponding structured condition numbers of the MTLS problem are also derived. These expressions all involve matrix Kronecker product operations, we propose different skills to simplify the expressions to improve the computational efficiency. For the normwise condition number, we show that it can be transformed into several compact forms, and the perturbation bound is also an alternation. From a number of numerical tests, we can see that the new forms and bounds for the normwise condition number have great computational efficiency and require less storage. For structured/sparse and badly-scaled MTLS problems, the sparse pattern and the magnitude of the entries are better utilized in (structured) mixed and componentwise condition numbers than normwise condition number, and it is more suitable to adopt mixed/componentwise condition numbers to measure the conditioning of badly scaled or structured MTLS problems.