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.     

BTTB preconditioners for BTTB least squares problems

In this paper, we consider solving the least squares problem min_x‖b-Tx‖₂ by using preconditioned conjugate gradient (PCG) methods, where T is a large rectangular matrix which consists of several square block-Toeplitz-Toeplitz-block (BTTB) matrices and b is a column vector. We propose a BTTB preconditioner to speed up the PCG method and prove that the BTTB preconditioner is a good preconditioner. We then discuss the construction of the BTTB preconditioner. Numerical examples, including image restoration problems, are given to illustrate the efficiency of our BTTB preconditioner. Numerical results show that our BTTB preconditioner is more efficient than the well-known Level-1 and Level-2 circulant preconditioners.     

A generalized successive overrelaxation method for least squares problems

In this paper a new iterative method is given for solving large sparse least squares problems and computing the minimum norm solution to underdetermined consistent linear systems. The new scheme is called the generalized successive overrelaxation (GSOR) method and is shown to be convergent ifA is full column rank. The GSOR method involves a parameter ρ and an auxiliary matrixP. One can choose matrix P so that the GSOR method only involves matrix and vector operations; therefore the GSOR method is suitable for parallel computations. Besides, the GSOR method can be combined with preconditioning techniques, and therefore can be expected to be more effective. This author's work was supported by Natural Science Foundation of Liaoning Province, China.     

Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems

There exist many classes of block-projections algorithms for approximating solutions of linear least-squares problems. Generally, these methods generate sequences convergent to the minimal norm least-squares solution only for consistent problems. In the inconsistent case, which usually appears in practice because of some approximations or measurements, these sequences do no longer converge to a least-squares solution or they converge to the minimal norm solution of a “perturbed” problem. In the present paper, we overcome this difficulty by constructing extensions for almost all the above classes of block-projections methods. We prove that the sequences generated with these extensions always converge to a least-squares solution and, with a suitable initial approximation, to the minimal norm solution of the problem. Numerical experiments, described in the last section of the paper, confirm the theoretical results obtained.     

Accelerated Gauss-Newton algorithms for nonlinear least squares problems

Recent theoretical and practical investigations have shown that the Gauss-Newton algorithm is the method of choice for the numerical solution of nonlinear least squares parameter estimation problems. It is shown that when line searches are included, the Gauss-Newton algorithm behaves asymptotically like steepest descent, for a special choice of parameterization. Based on this a conjugate gradient acceleration is developed. It converges fast also for those large residual problems, where the original Gauss-Newton algorithm has a slow rate of convergence. Several numerical test examples are reported, verifying the applicability of the theory.     

A total least squares method for Toeplitz systems of equations

A Newton method to solve total least squares problems for Toeplitz systems of equations is considered. When coupled with a bisection scheme, which is based on an efficient algorithm for factoring Toeplitz matrices, global convergence can be guaranteed. Circulant and approximate factorization preconditioners are proposed to speed convergence when a conjugate gradient method is used to solve linear systems arising during the Newton iterations. The work of the second author was partially supported by a National Science Foundation Postdoctoral Research Fellowship.     

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     

Quadratically constrained least squares and quadratic problems

Summary We consider the following problem: Compute a vectorx such that Ax–b₂=min, subject to the constraint x₂=. A new approach to this problem based on Gauss quadrature is given. The method is especially well suited when the dimensions ofA are large and the matrix is sparse.It is also possible to extend this technique to a constrained quadratic form: For a symmetric matrixA we consider the minimization ofx ^T A x–2b ^T x subject to the constraint x₂=.Some numerical examples are given.This work was in part supported by the National Science Foundation under Grant DCR-8412314 and by the National Institute of Standards and Technology under Grant 60NANB9D0908.     

Constrained least squares methods for linear timevarying DAE systems

Summary This paper presents a family of methods for accurate solution of higher index linear variable DAE systems, . These methods use the DAE system and some of its first derivatives as constraints to a least squares problem that corresponds to a Taylor series ofy, or an approximative equality derived from a Pade' approximation of the exponential function. Accuracy results for systems transformable to standard canonical form are given. Advantages, disadvantages, stability properties and implementation of these methods are discussed and two numerical examples are given, where we compare our results with results from more traditional methods.     

On the weighting method for least squares problems with linear equality constraints

The weighting method for solving a least squares problem with linear equality constraints multiplies the constraints by a large number and appends them to the top of the least squares problem, which is then solved by standard techniques. In this paper we give a new analysis of the method, based on the QR decomposition, that exhibits many features of the algorithm. In particular it suggests a natural criterion for chosing the weighting factor. This work was supported in part by the National Science Foundation under grant CCR 95503126.     

Complexity reduction of least squares problems involving special vandermonde matrices

This paper presents a new QRD factorization of a rectangular Vandermonde matrix for a special point distribution, including the symmetric case, based on ak-dimensional block decomposition of the matrix and some properties of the Kronecker product. The computational reduction factor with respect to any QR method isk ², in the general case, and 4 in the symmetric one. By the resulting matrix factorization, new formulas are devised for the least squares system solution, whose implementation produces an algorithm of reduced computational cost and computer storage. Finally the perturbation bounds of this new factorization are devised.     

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     

A class of Uzawa-SOR methods for saddle point problems

In this paper, we consider a class of Uzawa-SOR methods for saddle point problems, and prove the convergence of the proposed methods. We solve a lower triangular system per iteration in the proposed methods, instead of solving a linear equation Az=b. Actually, the new methods can be considered as an inexact iteration method with the Uzawa as the outer iteration and the SOR as the inner iteration. Although the proposed methods cannot achieve the same convergence rate as the GSOR methods proposed by Bai et al. [Z.-Z. Bai, B.N. Parlett, Z.-Q. Wang, On generalized successive overrelaxation methods for augmented linear systems, Numer. Math. 102 (2005) 1-38], but our proposed methods have less workloads per iteration step. Experimental results show that our proposed methods are feasible and effective.     

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)     

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.     

Incomplete block-matrix factorization iterative methods for convection-diffusion problems

Standard Galerkin finite element methods or finite difference methods for singular perturbation problems lead to strongly unsymmetric matrices, which furthermore are in general notM-matrices. Accordingly, preconditioned iterative methods such as preconditioned (generalized) conjugate gradient methods, which have turned out to be very successful for symmetric and positive definite problems, can fail to converge or require an excessive number of iterations for singular perturbation problems.This is not so much due to the asymmetry, as it is to the fact that the spectrum can have both eigenvalues with positive and negative real parts, or eigenvalues with arbitrary small positive real parts and nonnegligible imaginary parts. This will be the case for a standard Galerkin method, unless the meshparameterh is chosen excessively small. There exist other discretization methods, however, for which the corresponding bilinear form is coercive, whence its finite element matrix has only eigenvalues with positive real parts; in fact, the real parts are positive uniformly in the singular perturbation parameter.In the present paper we examine the streamline diffusion finite element method in this respect. It is found that incomplete block-matrix factorization methods, both on classical form and on an inverse-free (vectorizable) form, coupled with a general least squares conjugate gradient method, can work exceptionally well on this type of problem. The number of iterations is sometimes significantly smaller than for the corresponding almost symmetric problem where the velocity field is close to zero or the singular perturbation parameter =1.The 2 ^nd author's research was sponsored by Control Data Corporation through its PACER fellowship program.The 3 ^rd author's research was supported by the Netherlands organization for scientific research (NWO).On leave from the Institute of Mathematics, Academy of Science, 1090 Sofia, P.O. Box 373, Bulgaria.     

Approximating minimum norm solutions of rank-deficient least squares problems

In this paper we consider the solution of linear least squares problems min_x∥Ax - b∥²₂ where the matrix A ∈ R ^{m × n} is rank deficient. Put p = min{m, n}, let σ_i, i = 1, 2,…, p, denote the singular values of A, and let u_i and v_i denote the corresponding left and right singular vectors. Then the minimum norm solution of the least squares problem has the form x* = ∫^r_{i = 1}(u^T_ib/σ_i)v_i, where r ≤ p is the rank of A. The Riley–Golub iteration, x_{k + 1} = arg min_x{∥Ax - b∥²₂ + λ∥x − x_k∥²₂} converges to the minimum norm solution if x₀ is chosen equal to zero. The iteration is implemented so that it takes advantage of a bidiagonal decomposition of A. Thus modified, the iteration requires only O(p) flops (floating point operations). A further gain of using the bidiagonalization of A is that both the singular values σ_i and the scalar products u^T_ib can be computed at marginal extra cost. Moreover, we determine the regularization parameter, λ, and the number of iterations, k, in a way that minimizes the difference x* − x_k with respect to a certain norm. Explicit rules are derived for calculating these parameters. One advantage of our approach is that the numerical rank can be easily determined by using the singular values. Furthermore, by the iterative procedure, x* is approximated without computing the singular vectors of A. This gives a fast and reliable method for approximating minimum norm solutions of well-conditioned rank-deficient least squares problems. Numerical experiments illustrate the viability of our ideas, and demonstrate that the new method gives more accurate approximations than an approach based on a QR decomposition with column pivoting. © 1998 John Wiley & Sons, Ltd.     

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     

Galerkin-wavelet methods for two-point boundary value problems

Summary Anti-derivatives of wavelets are used for the numerical solution of differential equations. Optimal error estimates are obtained in the applications to two-point boundary value problems of second order. The orthogonal property of the wavelets is used to construct efficient iterative methods for the solution of the resultant linear algebraic systems. Numerical examples are given.This work was supported by National Science Foundation     

Multilevel iterative methods for mixed finite element discretizations of elliptic problems

Summary For solving second order elliptic problems discretized on a sequence of nested mixed finite element spaces nearly optimal iterative methods are proposed. The methods are within the general framework of the product (multiplicative) scheme for operators in a Hilbert space, proposed recently by Bramble, Pasciak, Wang, and Xu [5,6,26,27] and make use of certain multilevel decomposition of the corresponding spaces for the flux variable.