An algorithm for linear least squares problems with equality and nonnegativity constraints

We present a new algorithm for solving a linear least squares problem with linear constraints. These are equality constraint equations and nonnegativity constraints on selected variables. This problem, while appearing to be quite special, is the core problem arising in the solution of the general linearly constrained linear least squares problem. The reduction process of the general problem to the core problem can be done in many ways. We discuss three such techniques.The method employed for solving the core problem is based on combining the equality constraints with differentially weighted least squares equations to form an augmented least squares system. This weighted least squares system, which is equivalent to a penalty function method, is solved with nonnegativity constraints on selected variables.Three types of examples are presented that illustrate applications of the algorithm. The first is rank deficient, constrained least squares curve fitting. The second is concerned with solving linear systems of algebraic equations with Hilbert matrices and bounds on the variables. The third illustrates a constrained curve fitting problem with inconsistent inequality constraints.     

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.     

等式约束加权线性最小二乘问题的解法

1 引言 在实际应用中常会提出解等式约束加权线性最小二乘问题 min||b-Ax||_M,(1.1) x∈C~n s.t.Bx=d, 其中B∈C~(p×n),A∈C~(q×n),d∈C~p,b∈C~q,M∈C~(q×q)为Hermite正定阵. 对于问题(1.1),目前已有多种解法,见文[1—3).本文将利用广义逆矩阵的知识,给出(1.1)的通解及迭代解法.本文中关于矩阵广义逆与投影算子(矩阵)的记号基本上与文[4]的相同.例如,A~+表示A的MP逆,P_L表示到子空间L上的正交投影算子,λ_(max)(MAY)表示矩阵M~(1/2)AY的最大特征值.我们还要用到广义BD逆的概念: 设A∈C~(n×n),L为C~n的子空间,则称A_(L)~(+)=P_L(AP_L+P_L⊥)~+为A关于L的广义BD逆.     

Error estimation for a weighted minimum-norm least squares solution with positive definite weights

The weighted least squares problem is considered. Given a generally inconsistent system of linear algebraic equations, error estimates are obtained for its weighted minimum-norm least squares solution under perturbations of the matrix and the right-hand side, including the case of rank modifications of the perturbed matrix.     

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.     

Condition numbers and perturbation analysis for the Tikhonov regularization of discrete ill‐posed problems

One of the most successful methods for solving the least‐squares problem min_x∥Ax?b∥₂ with a highly ill‐conditioned or rank deficient coefficient matrix A is the method of Tikhonov regularization. In this paper, we derive the normwise, mixed and componentwise condition numbers and componentwise perturbation bounds for the Tikhonov regularization. Our results are sharper than the known results. Some numerical examples are given to illustrate our results. Copyright © 2010 John Wiley & Sons, Ltd.     

加权总体最小二乘问题的解集和性质

本文讨论了加权总体最小二乘问题的等价解集，分析了加权总体最小二乘解与加权最小二乘问题的解之间的关系。推广了Ｇｏｌｕｂ和Ｖａｎ Ｌｏａｎ，Ｖａｎ Ｈｕｆｆｅｌ和Ｖａｎｄｅｗａｌｌｅ，及Ｗｅｉ的相应结果。     

Relationship Between the Stiffly Weighted Pseudoinverse and Multi-Level Constrained Rseudoinverse

It is known that for a given matrix A of rank r, and a set D of positive diagonal matrices, supw∈D‖（W^1/2A) W^1/2‖ = (miniσ (A^(i))^-1, in which (A^(i) is a submatrix of A formed with r = (rank(A)) rows of A, such that (A^(i) has full row rank r. In many practical applications this value is too large to be used. In this paper we consider the case that both A and W(∈D) are fixed with W severely stiff. We show that in this case the weighted pseudoinverse (W^1/2‖A) W^1/2‖ is close to a multilevel constrained weighted pseudoinverse therefore ‖(W^1/2A) W^1/‖2 is uniformly bounded.We also prove that in this case the solution set the stiffly weighted least squares problem is close to that of corresponding multi-level constrained least squares problem.     

Implicit Scaling of Linear Least Squares Problems

We consider the solution of weighted linear least squares problems by Householder transformations with implicit scaling, that is, with the weights stored separately. By holding inverse weights, the constrained case can be accommodated. The error analysis of the weighted and unconstrained case is readily extended and we show that iterative refinement may be applied.     

Imposing symmetry in augmented linear systems

This paper discusses the methods of imposing symmetry in the augmented system formulation (ASF) for least‐squares (LS) problems. A particular emphasis is on upper Hessenberg problems, where the challenge lies in leaving all zero‐by‐definition elements of the LS matrix unperturbed. Analytical solutions for optimal perturbation matrices are given, including upper Hessenberg matrices. Finally, the upper Hessenberg LS problems represented by unsymmetric ASF that indicate a normwise backward stability of the problem (which is not the case in general) are identified. It is observed that such problems normally arise from Arnoldi factorization (for example, in the generalized minimal residual (GMRES) algorithm). The problem is illustrated with a number of practical (arising in the GMRES algorithm) and some ‘purpose‐built’ examples. Copyright © 2014 John Wiley & Sons, Ltd.     

On the modified Gram-Schmidt algorithm for weighted and constrained linear least squares problems

A framework and an algorithm for using modified Gram-Schmidt for constrained and weighted linear least squares problems is presented. It is shown that a direct implementation of a weighted modified Gram-Schmidt algorithm is unstable for heavily weighted problems. It is shown that, in most cases it is possible to get a stable algorithm by a simple modification free from any extra computational costs. In particular, it is not necessary to perform reorthogonalization.Solving the weighted and constrained linear least squares problem with the presented weighted modified Gram-Schmidt algorithm is seen to be numerically equivalent to an algorithm based on a weighted Householder-likeQR factorization applied to a slightly larger problem. This equivalence is used to explain the instability of the weighted modified Gram-Schmidt algorithm. If orthogonality, with respect to a weighted inner product, of the columns inQ is important then reorthogonalization can be used. One way of performing such reorthogonalization is described.Computational tests are given to show the main features of the algorithm.     

On greedy randomized coordinate descent methods for solving large linear least‐squares problems

For solving large scale linear least‐squares problem by iteration methods, we introduce an effective probability criterion for selecting the working columns from the coefficient matrix and construct a greedy randomized coordinate descent method. It is proved that this method converges to the unique solution of the linear least‐squares problem when its coefficient matrix is of full rank, with the number of rows being no less than the number of columns. Numerical results show that the greedy randomized coordinate descent method is more efficient than the randomized coordinate descent method.     

ON THE ACCURACY OF THE LEAST SQUARES AND THE TOTAL LEAST SQUARES METHODS

Consider solving an overdetermined system of linear algebraic equations by both the least squares method (LS) and the total least squares method (TLS). Extensive published computational evidence shows that when the original system is consistent. one often obtains more accurate solutions by using the TLS method rather than the LS method. These numerical observations contrast with existing analytic perturbation theories for the LS and TLS methods which show that the upper bounds for the LS solution are always smaller than the corresponding upper bounds for the TLS solutions. In this paper we derive a new upper bound for the TLS solution and indicate when the TLS method can be more accurate than the LS method.Many applied problems in signal processing lead to overdetermined systems of linear equations where the matrix and right hand side are determined by the experimental observations (usually in the form of a lime series). It often happens that as the number of columns of the matrix becomes larger, the ra     

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     

Consistency adjustments for pairwise comparison matrices

This paper is concerned with the development of a ‘best’ rank one transitive approximation to a general paired comparison matrix in a least‐squares sense. A direct attack on the non‐linear problem is frequently replaced by a sub‐optimal linear problem and, here, the best procedure of this kind is obtained. The Newton–Kantorovich method for the solution of the non‐linear problem is also studied, including the role of the best linear approximation as a starting point for this method. Numerical examples are included. Copyright © 2002 John Wiley & Sons, Ltd.     

Convergence results for an accelerated nonlinear cimmino algorithm

Summary We present an accelerated version of Cimmino's algorithm for solving the convex feasibility problem in finite dimension. The algorithm is similar to that given by Censor and Elfving for linear inequalities. We show that the nonlinear version converges locally to a weighted least squares solution in the general case and globally to a feasible solution in the consistent case. Applications to the linear problem are suggested.     

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.     

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.     

The Core-EP,Weighted Core-EP Inverse of Matrices and Constrained Systems of Linear Equations

We study the constrained systemof linear equations Ax=b,x∈R(A^k)for A∈C^n×nand b∈Cn,k=Ind(A).When the system is consistent,it is well known that it has a unique A^Db.If the system is inconsistent,then we seek for the least squares solution of the problem and consider min_x∈R(A^k)||b?Ax||2,where||·||2 is the 2-norm.For the inconsistent system with a matrix A of index one,it was proved recently that the solution is A^■b using the core inverse A^■of A.For matrices of an arbitrary index and an arbitrary b,we show that the solution of the constrained system can be expressed as A^■b where A^■is the core-EP inverse of A.We establish two Cramer’s rules for the inconsistent constrained least squares solution and develop several explicit expressions for the core-EP inverse of matrices of an arbitrary index.Using these expressions,two Cramer’s rules and one Gaussian elimination method for computing the core-EP inverse of matrices of an arbitrary index are proposed in this paper.We also consider the W-weighted core-EP inverse of a rectangular matrix and apply the weighted core-EP inverse to a more general constrained system of linear equations.     

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.