A preconditioner for constrained and weighted least squares problems with Toeplitz structure

We study methods for solving the constrained and weighted least squares problem min _x by the preconditioned conjugate gradient (PCG) method. HereW = diag (₁, , _m ) with _{1 m} 0, andA ^T = [T ₁ ^T , ,T _k ^T ] with Toeplitz blocksT _l R ^{n × n} ,l = 1, ,k. It is well-known that this problem can be solved by solving anaugmented linear 2 × 2 block linear systemM +Ax =b, A ^T = 0, whereM =W ^–1. We will use the PCG method with circulant-like preconditioner for solving the system. We show that the spectrum of the preconditioned matrix is clustered around one. When the PCG method is applied to solve the system, we can expect a fast convergence rate.Research supported by HKRGC grants no. CUHK 178/93E and CUHK 316/94E.     

A primal-dual interior-point algorithm for nonlinear least squares constrained problems

This paper extends prior work by the authors on solving nonlinear least squares unconstrained problems using a factorized quasi-Newton technique. With this aim we use a primal-dual interior-point algorithm for nonconvex nonlinear programming. The factorized quasi-Newton technique is now applied to the Hessian of the Lagrangian function for the transformed problem which is based on a logarithmic barrier formulation. We emphasize the importance of establishing and maintaining symmetric quasi-definiteness of the reduced KKT system. The algorithm then tries to choose a step size that reduces a merit function, and to select a penalty parameter that ensures descent directions along the iterative process. Computational results are included for a variety of least squares constrained problems and preliminary numerical testing indicates that the algorithm is robust and efficient in practice.     

On the perturbation of least squares problems with equality constraints

Some new perturbation results are presented for least squares problems with equality constraints, in which relative errors are obtained on perturbed solutions, least squares residuals, and vectors of Lagrange multipliers of the problem, based on the equivalence of the problem to a usual least squares problem and optimal perturbation results for orthogonal projections.     

Preconditioned conjugate gradient method for generalized least squares problems

A variant of the preconditioned conjugate gradient method to solve generalized least squares problems is presented. If the problem is min (Ax − b)^TW⁻¹(Ax − b) with A ∈ R^m×n and W ∈ R^m×m symmetric and positive definite, the method needs only a preconditioner A₁ ∈ R^n×n, but not the inverse of matrix W or of any of its submatrices. Freund's comparison result for regular least squares problems is extended to generalized least squares problems. An error bound is also given.     

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.     

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.     

On the condition number of linear least squares problems in a weighted Frobenius norm

LetA be anm × n, m n full rank real matrix andb a real vector of sizem. We give in this paper an explicit formula for the condition number of the linear least squares problem (LLSP) defined by min Ax–b₂,x ⁿ . Let and be two positive real numbers, we choose the weighted Frobenius norm [A, b] _F on the data and the usual Euclidean norm on the solution. A straightforward generalization of the backward error of [9] to this norm is also provided. This allows us to carry out a first order estimate of the forward error for the LLSP with this norm. This enables us to perform a complete backward error analysis in the chosen norms.Finally, some numerical results are presented in the last section on matrices from the collection of [5]. Three algorithms have been tested: the QR factorization, the Normal Equations (NE), the Semi-Normal Equations (SNE).     

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.     

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.     

A new linesearch algorithm for nonlinear least squares problems

A linesearch (steplength) algorithm for unconstrained nonlinear least squares problems is described. To estimate the steplength inside the linesearch algorithm a new method that interpolates the residual vector is used together with a standards method that interpolates the sums of squares. Numerical results are reported that point out the advantage with the new steplength estimation method.     

A stable method for solving certain constrained least squares problems

This paper presents a feasible descent algorithm for solving certain constrained least squares problems. These problems are specially structured quadratic programming problems with positive semidefinite Hessian matrices that are allowed to be singular. The algorithm generates a finite sequence of subproblems that are solved using the numerically stable technique of orthogonal factorization with reorthogonalization and Given's transformation updating.This material is based upon work supported by the National Science Foundation under Grant No. MCS 78-06716 and by the International Institute for Applied Systems Analysis.     

Algebraic methods for equality constrained least squares problems in commutative quaternionic theory

This paper, by means of two matrix representations of a commutative quaternion matrix, studies the relationship between the solutions of commutative quaternion equality constrained least squares (LSE) problems and that of complex and real LSE problems and derives two algebraic methods for finding the solutions of equality constrained least squares problems in commutative quaternionic theory.     

Asymptotic distribution of the weighted least squares estimator

This paper derives the asymptotic distribution of the weighted least squares estimator (WLSE) in a heteroscedastic linear regression model. A consistent estimator of the asymptotic covariance matrix of the WLSE is also obtained. The results are obtained under weak conditions on the design matrix and some moment conditions on the error distributions. It is shown that most of the error distributions encountered in practice satisfy these moment conditions. Some examples of the asymptotic covariance matrices are also given.     

Accuracy of Gram–Schmidt orthogonalization and Householder transformation for the solution of linear least squares problems

Accuracy of a Gram–Schmidt algorithm for the solution of linear least squares equations is compared with accuracy of least squares subroutines in three highly respected mathematical packages that use Householder transformations. Results from the four programs for 13 test problems were evaluated at 16 digit precision on four different desktop computers using four different compilers. Singular values obtained from the different programs are compared and the effect of pivoting to improve the accuracy is discussed. Solution vectors from the program using the Gram–Schmidt algorithm were generally more accurate or comparable to solution vectors from the programs using the Householder transformations. © 1997 John Wiley & Sons, Ltd.     

Matrix stretching for sparse least squares problems

For linear least squares problems min _x ‖Ax − b‖₂, where A is sparse except for a few dense rows, a straightforward application of Cholesky or QR factorization will lead to catastrophic fill in the factor R. We consider handling such problems by a matrix stretching technique, where the dense rows are split into several more sparse rows. We develop both a recursive binary splitting algorithm and a more general splitting method. We show that for both schemes the stretched problem has the same set of solutions as the original least squares problem. Further, the condition number of the stretched problem differs from that of the original by only a modest factor, and hence the approach is numerically stable. Experimental results from applying the recursive binary scheme to a set of modified matrices from the Harwell‐Boeing collection are given. We conclude that when A has a small number of dense rows relative to its dimension, there is a significant gain in sparsity of the factor R. A crude estimate of the optimal number of splits is obtained by analysing a simple model problem. Copyright © 2000 John Wiley & Sons, Ltd.     

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.     

Preconditioner based on the Sherman-Morrison formula for regularized least squares problems

We propose a sparse approximate inverse preconditioner based on the Sherman-Morrison formula for Tikhonov regularized least square problems. Theoretical analysis shows that, the factorization method can take the advantage of the symmetric property of the coefficient matrix and be implemented cheaply. Combined with dropping rules, the incomplete factorization leads to a preconditioner for Krylov iterative methods to solve regularized least squares problems. Numerical experiments show that our preconditioner is competitive compared to existing methods, especially for ill-conditioned and rank deficient least squares problems.     

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.     

Iterative refinement for constrained and weighted linear least squares

We present an algorithm for mixed precision iterative refinement on the constrained and weighted linear least squares problem, the CWLSQ problem. The approximate solution is obtained by solving the CWLSQ problem with the weightedQR factorization [6]. With backward errors for the weightedQR decomposition together with perturbation bounds for the CWLSQ problem we analyze the convergence behaviour of the iterative refinement procedure.In the unweighted case the initial convergence rate of the error of the iteratively refined solution is determined essentially by the condition number. For the CWLSQ problem the initial convergence behaviour is more complicated. The analysis shows that the initial convergence is dependent both on the condition of the problem related to the solution,x, and the vector =Wr, whereW is the weight matrix andr is the residual.We test our algorithm on two examples where the solution is known and the condition number of the problem can be varied. The computational test confirms the theoretical results and verifies that mixed precision iterative refinement, using the system matrix and the weightedQR decomposition, is an effective way of improving an approximate solution to the CWLSQ problem.