Preconditioned GAOR methods for solving weighted linear least squares problems

In this paper, we present the preconditioned generalized accelerated overrelaxation (GAOR) method for solving linear systems based on a class of weighted linear least square problems. Two kinds of preconditioning are proposed, and each one contains three preconditioners. We compare the spectral radii of the iteration matrices of the preconditioned and the original methods. The comparison results show that the convergence rate of the preconditioned GAOR methods is indeed better than the rate of the original method, whenever the original method is convergent. Finally, a numerical example is presented in order to confirm these theoretical results.     

Local convergence of a secant type method for solving least squares problems

Local convergence of a secant type iterative method for approximating a solution of nonlinear least squares problems is investigated in this paper. The radius of convergence is determined as well as usable error estimates. Numerical examples are also provided.     

On the incomplete oblique projections method for solving box constrained least squares problems

The aim of this paper is to extend the applicability of the incomplete oblique projections method (IOP) previously introduced by the authors for solving inconsistent linear systems to the box constrained case. The new algorithm employs incomplete projections onto the set of solutions of the augmented system Ax ? r = b, together with the box constraints, based on a scheme similar to the one of IOP, adding the conditions for accepting an approximate solution in the box. The theoretical properties of the new algorithm are analyzed, and numerical experiences are presented comparing its performance with some well-known methods.     

A derivative free iterative method for solving least squares problems

A derivative free iterative method for approximating a solution of nonlinear least squares problems is studied first in Shakhno and Gnatyshyn (Appl Math Comput 161:253–264, 2005). The radius of convergence is determined as well as usable error estimates. We show that this method is faster than its Secant analogue examined in Shakhno and Gnatyshyn (Appl Math Comput 161:253–264, 2005). Numerical example is also provided in this paper.     

A continuation method for solving separable nonlinear least squares problems

Given the data (x_i, y_i), i=1, 2, …, n, the problem is to find the values of the linear and nonlinear parameters â and b? which minimize the nonlinear functional |F(b)a?y|₂² over $\text{a ?}\text{R}{}^{\mathrm{p}}\text{, b ?}\text{R}{}^{\mathrm{q}}\text{,}\text{where}\text{F ?}\text{R}{}^{\mathrm{n\times p}}$ is a variable matrix and assumed to be of full rank, and $\text{y ?}\text{R}{}^{\mathrm{n}}$ is a constant vector.In this paper, we present a method for solving this problem by imbedding it into a one-parameter family of problems and by following its solution path using a predictor-corrector algorithm. In the course of iterations, the original problem containing p+q+1 variables is transformed into a problem with q+1 nonlinear variables by taking the separable structure of the problem into account. By doing so, the method reduces to solving a series of equations of smaller size and a considerable saving in the storage is obtained.Results of numerical experiments are reported to demonstrate the effectiveness of the proposed 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.     

Secant variable projection method for solving nonnegative separable least squares problems

Numerical Algorithms - The variable projection method is a classical and efficient method for solving separable nonlinear least squares (SNLLS) problems. However, it is hard to handle the...     

A variable projection method for solving separable nonlinear least squares problems

Consider the separable nonlinear least squares problem of findinga εR ⁿ and α εR ^k which, for given data (y _i ,t _i ),i=1,2,...m, and functions ? _j (α,t),j=1,2,...,n(m>n), minimize the functional $$r(a,\alpha ) = \left\| {y - \Phi (\alpha )a} \right\|_2^2$$ where θ(α) _ij =? _j (α,t _i ). Golub and Pereyra have shown that this problem can be reduced to a nonlinear least squares problem involvingα only, and a linear least squares problem involvinga only. In this paper we propose a new method for determining the optimalα which computationally has proved more efficient than the Golub-Pereyra scheme.     

Tikhonov regularization for weighted total least squares problems

In this work, we study and analyze the regularized weighted total least squares (RWTLS) formulation. Our regularization of the weighted total least squares problem is based on the Tikhonov regularization. Numerical examples are presented to demonstrate the effectiveness of the RWTLS method.     

Numerical methods for solving linear least squares problems

A common problem in a Computer Laboratory is that of finding linear least squares solutions. These problems arise in a variety of areas and in a variety of contexts. Linear least squares problems are particularly difficult to solve because they frequently involve large quantities of data, and they are ill-conditioned by their very nature. In this paper, we shall consider stable numerical methods for handling these problems. Our basic tool is a matrix decomposition based on orthogonal Householder transformations.Reproduction in Whole or in Part is permitted for any Purpose of the United States government. This report was supported in part by Office of Naval Research Contract Nonr-225(37) (NR 044-11) at Stanford University.     

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.     

On iterative methods for solving nonlinear least squares problems over convex sets

Nonlinear least squares problems over convex sets inR ⁿ are treated here by iterative methods which extend the classical Newton, gradient and steepest descent methods and the methods studied recently by Pereyra and the author. Applications are given to nonlinear least squares problems under linear constraint, and to linear and nonlinear inequalities. Part of the research underlying this report was undertaken for the Office of Naval Research, Contract Nonr-1228(10), Project NR047-021, and for the U.S. Army Research Office — Durham, Contract No. DA-31-124-ARO-D-322 at Northwestern University. Reproduction of this paper in whole or in part is permitted for any purpose of the United States Government.     

A weighted pseudoinverse,generalized singular values,and constrained least squares problems

The weighted pseudoinverse providing the minimum semi-norm solution of the weighted linear least squares problem is studied. It is shown that it has properties analogous to those of the Moore-Penrose pseudoinverse. The relation between the weighted pseudoinverse and generalized singular values is explained. The weighted pseudoinverse theory is used to analyse least squares problems with linear and quadratic constraints. A numerical algorithm for the computation of the weighted pseudoinverse is briefly described.This work was supported in part by the Swedish Institute for Applied Mathematics.     

A weighted least squares method for scattered data fitting

In this paper, we present a weighted least squares method to fit scattered data with noise. Existence and uniqueness of a solution are proved and an error bound is derived. The numerical experiments illustrate that our weighted least squares method has better performance than the traditional least squares method in case of noisy data.     

On the weighting method for mixed least squares–total least squares problems

It is well known that the standard algorithm for the mixed least squares–total least squares (MTLS) problem uses the QR factorization to reduce the original problem into a standard total least squares problem with smaller size, which can be solved based on the singular value decomposition (SVD). In this paper, the MTLS problem is proven to be closely related to a weighted total least squares problem with its error‐free columns multiplied by a large weighting factor. A criterion for choosing the weighting factor is given; and for the sake of stability in solving the MTLS problem, the Cholesky factorization‐based inverse (Cho‐INV) iteration and Rayleigh quotient iteration are also considered. For large‐scale MTLS problems, numerical tests show that Cho‐INV is superior to the standard QR‐SVD method, especially for the case with big gap between the desired and undesired singular values and the case when the coefficient matrix has much more error‐contaminated columns. Rayleigh quotient iteration behaves more efficient than QR‐SVD for most cases and fails occasionally, and in some cases, it converges much faster than Cho‐INV but still less efficient due to its higher computation cost.     

On the equivalence of the weighted least squares and the generalised least squares estimators,with applications to kernel smoothing

This paper establishes the conditions under which the generalised least squares estimator of the regression parameters is equivalent to the weighted least squares estimator. The equivalence conditions have interesting applications in local polynomial regression and kernel smoothing. Specifically, they enable to derive the optimal kernel associated with a particular covariance structure of the measurement error, where optimality has to be intended in the Gauss-Markov sense. For local polynomial regression it is shown that there is a class of covariance structures, associated with non-invertible moving average processes of given orders which yield the Epanechnikov and the Henderson kernels as the optimal kernels.