Perturbation theory for generalized and constrained linear least squares

The perturbation analysis of weighted and constrained rank‐deficient linear least squares is difficult without the use of the augmented system of equations. In this paper a general form of the augmented system is used to get simple perturbation identities and perturbation bounds for the general linear least squares problem both for the full‐rank and rank‐deficient problem. Perturbation identities for the rank‐deficient weighted and constrained case are found as a special case. Interesting perturbation bounds and condition numbers are derived that may be useful when considering the stability of a solution of the rank‐deficient general least squares problem. Copyright © 2000 John Wiley & Sons, Ltd.     

Perturbation Identities for Regularized Tikhonov Inverses and Weighted Pseudoinverses

We consider the perturbation analysis of two important problems for solving ill-conditioned or rank-deficient linear least squares problems. The Tikhonov regularized problem is a linear least squares problem with a regularization term balancing the size of the residual against the size of the weighted solution. The weight matrix can be a non-square matrix (usually with fewer rows than columns). The minimum-norm problem is the minimization of the size of the weighted solutions given by the set of solutions to the, possibly rank-deficient, linear least squares problem.It is well known that the solution of the Tikhonov problem tends to the minimum-norm solution as the regularization parameter of the Tikhonov problem tends to zero. Using this fact and the generalized singular value decomposition enable us to make a perturbation analysis of the minimum-norm problem with perturbation results for the Tikhonov problem. From the analysis we attain perturbation identities for Tikhonov inverses and weighted pseudoinverses.     

Properties and least‐squares problems for row extended matrices

In this paper, we discuss basic properties, a least‐squares problem for row extended matrices and the associated approximation problem. First, we obtain their basic properties by applying their particular structure. Then we derive a general representation of the solutions to the least‐squares problem, and we obtain an expression for the solution to the associated approximation problem. Finally, we provide a perturbation analysis and a perturbation bound for the best approximate solution. The results are illustrated by numerical examples. Copyright © 2009 John Wiley & Sons, Ltd.     

Perturbation analysis for mixed least squares–total least squares problems

In many linear parameter estimation problems, one can use the mixed least squares–total least squares (MTLS) approach to solve them. This paper is devoted to the perturbation analysis of the MTLS problem. Firstly, we present the normwise, mixed, and componentwise condition numbers of the MTLS problem, and find that the normwise, mixed, and componentwise condition numbers of the TLS problem and the LS problem are unified in the ones of the MTLS problem. In the analysis of the first‐order perturbation, we first provide an upper bound based on the normwise condition number. In order to overcome the problems encountered in calculating the normwise condition number, we give an upper bound for computing more effectively for the MTLS problem. As two estimation techniques for solving the linear parameter estimation problems, interesting connections between their solutions, their residuals for the MTLS problem, and the LS problem are compared. Finally, some numerical experiments are performed to illustrate our results.     

关于广义线性最小二乘问题的扰动分析

1问题 在应用统计中，常用的参数估计方法之一是广义线性最小二乘min(Cx-y)~TW~+(Cx-y).(1.1)其中C为m×n矩阵，W为m×m对称半正定矩阵，上标+代表Moore-Penrose广义逆Paige~[1]注意到：从统计观点看，W一般未必可逆，且通常具有对称满秩分解W=BB~T，因而，把问题改述为下述形式更合适     

THE NESTED TOTAL LEAST SQUARES PROBLEM:FORMULATION,SOLUTIONS AND PERTURBATION ANALYSIS

In this paper, we propose the nested totoal least squatres problem (NTLS), which is an extension of the equality constrained least squares problem (LSE). The formulation of the NTLS problem is given and the solution set of the NTLS problem is obtained. The least squares residuals and the minimal norm correction matrices of the NTLS solution are provided and a perturbation analysis of the NTLS solutions is given.     

Backward perturbation analysis for scaled total least‐squares problems

The scaled total least‐squares (STLS) method unifies the ordinary least‐squares (OLS), the total least‐squares (TLS), and the data least‐squares (DLS) methods. In this paper we perform a backward perturbation analysis of the STLS problem. This also unifies the backward perturbation analyses of the OLS, TLS and DLS problems. We derive an expression for an extended minimal backward error of the STLS problem. This is an asymptotically tight lower bound on the true minimal backward error. If the given approximate solution is close enough to the true STLS solution (as is the goal in practice), then the extended minimal backward error is in fact the minimal backward error. Since the extended minimal backward error is expensive to compute directly, we present a lower bound on it as well as an asymptotic estimate for it, both of which can be computed or estimated more efficiently. Our numerical examples suggest that the lower bound gives good order of magnitude approximations, while the asymptotic estimate is an excellent estimate. We show how to use our results to easily obtain the corresponding results for the OLS and DLS problems in the literature. Copyright © 2009 John Wiley & Sons, Ltd.     

Perturbation bounds for the linear least squares problem subject to linear inequality constraints

We study the effect on the solution to a linear least squares problem with linear inequality and equality constraints when the data defining the problem are perturbed. The existence and uniqueness of a solution are investigated. If the matrices involved have full rank, then a detailed bound is obtained by the duality theory for quadratic programming. Sufficient conditions are derived for an estimate of the perturbation in the solution to hold in terms of the largest perturbation in the data.     

The Equality Constrained Indefinite Least Squares Problem: Theory and Algorithms

We present theory and algorithms for the equality constrained indefinite least squares problem, which requires minimization of an indefinite quadratic form subject to a linear equality constraint. A generalized hyperbolic QR factorization is introduced and used in the derivation of perturbation bounds and to construct a numerical method. An alternative method is obtained by employing a generalized QR factorization in combination with a Cholesky factorization. Rounding error analysis is given to show that both methods have satisfactory numerical stability properties and numerical experiments are given for illustration. This work builds on recent work on the unconstrained indefinite least squares problem by Chandrasekaran, Gu, and Sayed and by the present authors.     

Some new properties of the equality constrained and weighted least squares problem

In this paper, some new properties of the equality constrained and weighted least squares problem (WLSE) min W^1/2(Kx−g)₂ subject to Lx=h are obtained. We derive a perturbation bound based on an unconstrained least squares problem and deduce some equivalent formulae for the projectors of this unconstrained LS problem. We also present a new way to compute the minimum norm solution x_WLSE of the WLSE problem by using the QR decomposition of the corresponding matrices and propose an algorithm to compute x_WLSE using the QR factorizations. Some numerical examples are provided to compare different methods for solving the WLSE problem.     

Zur Kondition des linearen Ausgleichsproblems mit linearen Gleichungen als Nebenbedingungen

Summary F.L. Bauer has treated in several papers [1, 3, 4] the condition related to the solution of linear equations and to the algebraic eigenvalue problem. We study the condition for the linear least squares problem with linear equality constraints (problem LSE). A perturbation theory of problem LSE is presented and three condition numbers are defined. Problem LSE includes the linear least squares problem (problem LS). There are examples with identical solution of problem LSE and of problem LS. Sometimes the condition of problem LSE is better and sometimes the condition of problem LS is better. Several numerical tests illustrate the theory.

Herrn Prof. Dr. Dr. F.L. Bauer zum 60. Geburtstag gewidmet     

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.     

Accuracy and Stability of the Null Space Method for Solving the Equality Constrained Least Squares Problem

The null space method is a standard method for solving the linear least squares problem subject to equality constraints (the LSE problem). We show that three variants of the method, including one used in LAPACK that is based on the generalized QR factorization, are numerically stable. We derive two perturbation bounds for the LSE problem: one of standard form that is not attainable, and a bound that yields the condition number of the LSE problem to within a small constant factor. By combining the backward error analysis and perturbation bounds we derive an approximate forward error bound suitable for practical computation. Numerical experiments are given to illustrate the sharpness of this bound.     

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.     

Algebraic relations between the total least squares and least squares problems with more than one solution

Summary This paper completes our previous discussion on the total least squares (TLS) and the least squares (LS) problems for the linear systemAX=B which may contain more than one solution [12, 13], generalizes the work of Golub and Van Loan [1,2], Van Huffel [8], Van Huffel and Vandewalle [11]. The TLS problem is extended to the more general case. The sets of the solutions and the squared residuals for the TLS and LS problems are compared. The concept of the weighted squares residuals is extended and the difference between the TLS and the LS approaches is derived. The connection between the approximate subspaces and the perturbation theories are studied.It is proved that under moderate conditions, all the corresponding quantities for the solution sets of the TLS and the modified LS problems are close to each other, while the quantities for the solution set of the LS problem are close to the corresponding ones of a subset of that of the TLS problem.This work was financially supported by the Education Committee, People's Republic of China     

关于TLS和LS解的扰动分析

1．引言本文采用卜］的记号．最小二乘（LS）和总体最小二乘（TLS）是科学计算中的两种重要方法．尤是TLS，近来已有多篇论文讨论［1－6，8－16］．奇异值分解（SVD）和CS分解是研究TLS和LS的重要工具．令ACm，BCm,C=(A,B)，A和C的SVD分别为（1．1）（1．2）其中P51为某个正整数，U，U，V，V均为西矩阵，UI，UI，VI，VI为上述矩阵的前P列，z1一山。g（。1，…，内），】2＝di。g（内十l，…，。小】1＝dl。g（61；…，站，】2二diag（4＋1；…，dk），。l三··2。120和dl三…三d。20分别为C和A的奇异值，Z＝mhfm．n十以…     

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.     

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).     

关于TLS的可解性及扰动分析

尽管有关总体最小二乘问题的研究工作是大量的，然而ＴＬＳ可解的充分必要条件一直没有得到。本文首先给出完整的可解性分析，然后建立了ＴＬＳ的扰动上界。     

Perturbation Analysis of Structured Least Squares Problems and Its Application in Calibration of Interest Rate Term Structure

A structured perturbation analysis of the least squares problem is considered in this paper.The new error bound proves to be sharper than that for general perturbations. We apply the new error bound to study sensitivity of changing the knots for curve fitting of interest rate term structure by cubic spline.Numerical experiments are given to illustrate the sharpness of this bound.