On the condition number of the total least squares problem

This paper concerns singular value decomposition (SVD)-based computable formulas and bounds for the condition number of the total least squares (TLS) problem. For the TLS problem with the coefficient matrix $A$ and the right-hand side $b$ , a new closed formula is presented for the condition number. Unlike an important result in the literature that uses the SVDs of both $A$ and $[A,\ b]$ , our formula only requires the SVD of $[A,\ b]$ . Based on the closed formula, both lower and upper bounds for the condition number are derived. It is proved that they are always sharp and estimate the condition number accurately. A few lower and upper bounds are further established that involve at most the smallest two singular values of $A$ and of $[A,\ b]$ . Tightness of these bounds is discussed, and numerical experiments are presented to confirm our theory and to demonstrate the improvement of our upper bounds over the two upper bounds due to Golub and Van Loan as well as Baboulin and Gratton. Such lower and upper bounds are particularly useful for large scale TLS problems since they require the computation of only a few singular values of $A$ and $[A, \ b]$ other than all the singular values of them.     

Some results on condition numbers of the scaled total least squares problem

Under the Golub-Van Loan condition for the existence and uniqueness of the scaled total least squares (STLS) solution, a first order perturbation estimate for the STLS solution and upper bounds for condition numbers of a STLS problem have been derived by Zhou et al. recently. In this paper, a different perturbation analysis approach for the STLS solution is presented. The analyticity of the solution to the perturbed STLS problem is explored and a new expression for the first order perturbation estimate is derived. Based on this perturbation estimate, for some STLS problems with linear structure we further study the structured condition numbers and derive estimates for them. Numerical experiments show that the structured condition numbers can be markedly less than their unstructured counterparts.     

On nonlinear weighted total least squares parameter estimation problem for the three-parameter Weibull density

The three-parameter Weibull density function is widely employed as a model in reliability and lifetime studies. Estimation of its parameters has been approached in the literature by various techniques, because a standard maximum likelihood estimate does not exist. In this paper we consider the nonlinear weighted total least squares fitting approach. As a main result, a theorem on the existence of the total least squares estimate is obtained, as well as its generalization in the total _lq$l_q$ norm (q?1$q?1$). Some numerical simulations to support the theoretical work are given.     

Bounds for the least squares distance using scaled total least squares

Summary. The standard approaches to solving overdetermined linear systems construct minimal corrections to the data to make the corrected system compatible. In ordinary least squares (LS) the correction is restricted to the right hand side c, while in scaled total least squares (STLS) [14,12] corrections to both c and B are allowed, and their relative sizes are determined by a real positive parameter . As , the STLS solution approaches the LS solution. Our paper [12] analyzed fundamentals of the STLS problem. This paper presents a theoretical analysis of the relationship between the sizes of the LS and STLS corrections (called the LS and STLS distances) in terms of . We give new upper and lower bounds on the LS distance in terms of the STLS distance, compare these to existing bounds, and examine the tightness of the new bounds. This work can be applied to the analysis of iterative methods which minimize the residual norm, and the generalized minimum residual method (GMRES) [15] is used here to illustrate our theory. Received July 20, 2000 / Revised version received February 28, 2001 / Published online July 25, 2001     

Perturbation theory for the Eckart-Young-Mirsky theorem and the constrained total least squares problem

Golub et al. (Linear Algebra Appl. 88/89 (1987) 317–327), J.Demmel (SIAM J. Numer. Anal. 24 (1987) 199–206), generalized the Eckart-Young-Mirsky (EYM) theorem, which solves the problem of approximating a matrix by one of lower rank with only a specific rectangular subset of the matrix allowed to be changed. Based on their results, this paper presents perturbation analysis for the EYM theorem and the constrained total least squares problem (CTLS).     

About existence and uniqueness of the restricted total least squares estimation

Summary Total Least Squares (TLS) is an estimation method for the solutiona of the linear system when both data sets and are subject to error. The TLS-method minimizes the functional with weighting parameter . In this paper the TLS-functional is analyzed by the technique of Lagrangian multipliers. The main part of the work deals with the case when the estimatea is restricted by an inequality of the formD a–b0, D a diagonal matrix. It is shown that there exists a unique estimatea if the weighting parameter is chosen sufficiently large.     

Algebraic connections between the least squares and total least squares problems

Summary In this paper the closeness of the total least squares (TLS) and the classical least squares (LS) problem is studied algebraically. Interesting algebraic connections between their solutions, their residuals, their corrections applied to data fitting and their approximate subspaces are proven.All these relationships point out the parameters which mainly determine the equivalences and differences between the two techniques. These parameters also lead to a better understanding of the differences in sensitivity between both approaches with respect to perturbations of the data.In particular, it is shown how the differences between both approaches increase when the equationsAXB become less compatible, when the length ofB orX is growing or whenA tends to be rank-deficient. They are maximal whenB is parallel with the singular vector ofA associated with its smallest singular value. Furthermore, it is shown how TLS leads to a weighted LS problem, and assumptions about the underlying perturbation model of both techniques are deduced. It is shown that many perturbation models correspond with the same TLS solution.Senior Research Assistant of the Belgian N.F.W.O. (National Fund of Scientific Research)     

Implicitly-weighted total least squares

In a total least squares (TLS) problem, we estimate an optimal set of model parameters X, so that (A-ΔA)X=B-ΔB, where A is the model matrix, B is the observed data, and ΔA and ΔB are corresponding corrections. When B is a single vector, Rao (1997) and Paige and Strakoš (2002) suggested formulating standard least squares problems, for which ΔA=0, and data least squares problems, for which ΔB=0, as weighted and scaled TLS problems. In this work we define an implicitly-weighted TLS formulation (ITLS) that reparameterizes these formulations to make computation easier. We derive asymptotic properties of the estimates as the number of rows in the problem approaches infinity, handling the rank-deficient case as well. We discuss the role of the ratio between the variances of errors in A and B in choosing an appropriate parameter in ITLS. We also propose methods for computing the family of solutions efficiently and for choosing the appropriate solution if the ratio of variances is unknown. We provide experimental results on the usefulness of the ITLS family of solutions.     

Incomplete total least squares

Fitting data points with some model function such that the sum of squared orthogonal distances is minimized is well-known as TLS, i.e. as total least squares, see Van Huffel (1997). We consider situations where the model is such that there might be no perpendiculars from certain data points onto the model function and where one has to replace certain orthogonal distances by shortest ones, e.g. to corner or border line points. We introduce this considering the (now incomplete) TLS fit by a finite piece of a straight line. Then we study general model functions with linear parameters and modify a well-known descent algorithm (see Seufer (1996), Seufer/Sp?th (1997), Sp?th (1996), Sp?th (1997a) and Sp?th (1997b)) for fitting with them. As applications (to be used in computational metrology) we discuss incomplete TLS fitting with a segment of a circle, the area of a circle in space, with a cylinder, and with a rectangle (see also Gander/Hrebicek (1993)). Numerical examples are given for each case. Received August 27, 1997 / Revised version received February 23, 1998     

Effective condition numbers and small sample statistical condition estimation for the generalized Sylvester equation

In this paper,we investigate the effective condition numbers for the generalized Sylvester equation(AX-YB,DX-YE)=(C,F),where A,D∈R m×m,B,E∈R n×n and C,F ∈ R m×n.We apply the small sample statistical method for the fast condition estimation of the generalized Sylvester equation,which requires O(m2n+mn2) flops,comparing with O(m3+n3) flops for the generalized Schur and generalized HessenbergSchur methods for solving the generalized Sylvester equation.Numerical examples illustrate the sharpness of our perturbation bounds.     

Perturbation analysis and condition numbers of scaled total least squares problems

The standard approaches to solving an overdetermined linear system Ax ≈ b find minimal corrections to the vector b and/or the matrix A such that the corrected system is consistent, such as the least squares (LS), the data least squares (DLS) and the total least squares (TLS). The scaled total least squares (STLS) method unifies the LS, DLS and TLS methods. The classical normwise condition numbers for the LS problem have been widely studied. However, there are no such similar results for the TLS and the STLS problems. In this paper, we first present a perturbation analysis of the STLS problem, which is a generalization of the TLS problem, and give a normwise condition number for the STLS problem. Different from normwise condition numbers, which measure the sizes of both input perturbations and output errors using some norms, componentwise condition numbers take into account the relation of each data component, and possible data sparsity. Then in this paper we give explicit expressions for the estimates of the mixed and componentwise condition numbers for the STLS problem. Since the TLS problem is a special case of the STLS problem, the condition numbers for the TLS problem follow immediately from our STLS results. All the discussions in this paper are under the Golub-Van Loan condition for the existence and uniqueness of the STLS solution. Yimin Wei is supported by the National Natural Science Foundation of China under grant 10871051, Shanghai Science & Technology Committee under grant 08DZ2271900 and Shanghai Education Committee under grant 08SG01. Sanzheng Qiao is partially supported by Shanghai Key Laboratory of Contemporary Applied Mathematics of Fudan University during his visiting.     

The condition numbers for weighted Moore-Penrose inverse and weighted linear least squares problem

Condition numbers play an important role in numerical analysis. Classical normise condition numbers are used to measure the size of both input perturbations and output errors. In this paper, we study the weighted normwise relative condition numbers for the weighted Moore-Penrose inverse and the weighted linear least-squares (WLS) problems in the case of the full-column rank matrix. The bounds or formulas for the weighted condition numbers are presented. The obtained results can be viewed as extensions of the earlier works studied by others.     

Second-order nonlinear least squares estimation

The ordinary least squares estimation is based on minimization of the squared distance of the response variable to its conditional mean given the predictor variable. We extend this method by including in the criterion function the distance of the squared response variable to its second conditional moment. It is shown that this “second-order” least squares estimator is asymptotically more efficient than the ordinary least squares estimator if the third moment of the random error is nonzero, and both estimators have the same asymptotic covariance matrix if the error distribution is symmetric. Simulation studies show that the variance reduction of the new estimator can be as high as 50% for sample sizes lower than 100. As a by-product, the joint asymptotic covariance matrix of the ordinary least squares estimators for the regression parameter and for the random error variance is also derived, which is only available in the literature for very special cases, e.g. that random error has a normal distribution. The results apply to both linear and nonlinear regression models, where the random error distributions are not necessarily known.     

Randomized algorithms for total least squares problems

Motivated by the recently popular probabilistic methods for low‐rank approximations and randomized algorithms for the least squares problems, we develop randomized algorithms for the total least squares problem with a single right‐hand side. We present the Nyström method for the medium‐sized problems. For the large‐scale and ill‐conditioned cases, we introduce the randomized truncated total least squares with the known or estimated rank as the regularization parameter. We analyze the accuracy of the algorithm randomized truncated total least squares and perform numerical experiments to demonstrate the efficiency of our randomized algorithms. The randomized algorithms can greatly reduce the computational time and still maintain good accuracy with very high probability.     

Scaled total least squares fundamentals

Summary. The standard approaches to solving overdetermined linear systems construct minimal corrections to the vector c and/or the matrix B such that the corrected system is compatible. In ordinary least squares (LS) the correction is restricted to c, while in data least squares (DLS) it is restricted to B. In scaled total least squares (STLS) [22], corrections to both c and B are allowed, and their relative sizes depend on a real positive parameter . STLS unifies several formulations since it becomes total least squares (TLS) when , and in the limit corresponds to LS when , and DLS when . This paper analyzes a particularly useful formulation of the STLS problem. The analysis is based on a new assumption that guarantees existence and uniqueness of meaningful STLS solutions for all parameters . It makes the whole STLS theory consistent. Our theory reveals the necessary and sufficient condition for preserving the smallest singular value of a matrix while appending (or deleting) a column. This condition represents a basic matrix theory result for updating the singular value decomposition, as well as the rank-one modification of the Hermitian eigenproblem. The paper allows complex data, and the equivalences in the limit of STLS with DLS and LS are proven for such data. It is shown how any linear system can be reduced to a minimally dimensioned core system satisfying our assumption. Consequently, our theory and algorithms can be applied to fully general systems. The basics of practical algorithms for both the STLS and DLS problems are indicated for either dense or large sparse systems. Our assumption and its consequences are compared with earlier approaches. Received June 2, 1999 / Revised version received July 3, 2000 / Published online July 25, 2001     

Parallel variable distribution for total least squares

A novel parallel method for determining an approximate total least squares (TLS) solution is introduced. Based on domain decomposition, the global TLS problem is partitioned into several dependent TLS subproblems. A convergent algorithm using the parallel variable distribution technique (SIAM J. Optim. 1994; 4 :815–832) is presented. Numerical results support the development and analysis of the algorithms. Copyright © 2005 John Wiley & Sons, Ltd.     

A condition analysis of the weighted linear least squares problem using dual norms

In this paper, based on the theory of adjoint operators and dual norms, we define condition numbers for a linear solution function of the weighted linear least squares problem. The explicit expressions of the normwise and componentwise condition numbers derived in this paper can be computed at low cost when the dimension of the linear function is low due to dual operator theory. Moreover, we use the augmented system to perform a componentwise perturbation analysis of the solution and residual of the weighted linear least squares problems. We also propose two efficient condition number estimators. Our numerical experiments demonstrate that our condition numbers give accurate perturbation bounds and can reveal the conditioning of individual components of the solution. Our condition number estimators are accurate as well as efficient.     

Minimax estimation and the least squares method

This paper is devoted to the problem of minimax estimation of parameters in linear regression models with uncertain second order statistics. The solution to the problem is shown to be the least squares estimator corresponding to the least favourable matrix of the second moments. This allows us to construct a new algorithm for minimax estimation closely connected with the least squares method. As an example, we consider the problem of polynomial regression introduced by A. N. Kolmogorov     

On least squares estimation for long-memory lattice processes

A flexible class of anisotropic stationary lattice processes with long memory can be defined in terms of a two-way fractional ARIMA (FARIMA) representation. We consider parameter estimation based on minimizing an approximate residual sum of squares. The method can be applied to sampling areas that are not necessarily rectangular. A central limit theorem is derived under general conditions. The method is illustrated by an analysis of satellite data consisting of total column ozone amounts in Europe and the Atlantic respectively.