Symmetric block-SOR methods for rank-deficient least squares problems

In this article, we develop symmetric block successive overrelaxation (S-block-SOR) methods for finding the solution of the rank-deficient least squares problems. We propose an S2-block-SOR and an S3-block-SOR method for solving such problems and the convergence of these two methods is studied. The comparisons between the S2-block and the S3-block methods are presented with some numerical examples.     

Extrapolated Gauss-Seidel I and SOR methods for least-squares problems

Summary Recently, special attention has been given in the literature, to the problems of accurately computing the least-squares solution of very largescale over-determined systems of linear equations which occur in geodetic applications. In particular, it has been suggested that one can solve such problems iteratively by applying the block SOR (Successive Overrelaxation) and EGS1 (Extrapolated Gauss Seidel 1) plus semi-iterative methods to a linear system with coefficient matrix 2-cyclic or 3-cyclic. The comparison of 2-block SOR and 3-block SOR was made in [1] and showed that the 2-block SOR is better. In [6], the authors also proved that 3-block EGS1-SI is better than 3-block SOR. Here, we first show that the 2-block DJ (Double Jacobi)-SI, GS-SI and EGS1-SI methods are equivalent and all of them are equivalent to the 3-block EGS1-SI method; then, we prove that the composite methods and 2-block SOR have the same asymptotic rate of convergence, but the former has a better average rate of convergence; finally, numerical experiments are reported, and confirm that the 3-block EGS1-SI is better than the 2-block SOR.     

Convergence of a direct-iterative method for large-scale least-squares problems

In 1975 Chen and Gentleman suggested a 3-block SOR method for solving least-squares problems, based on a partitioning scheme for the observation matrix A into

$\text{A=}\text{A}{}_1\text{A}{}_2$

where A₁ is square and nonsingular. In many cases A₁ is obvious from the nature of the problem. This combined direct-iterative method was discussed further and applied to angle adjustment problems in geodesy, where A₁ is easily formed and is large and sparse, by Plemmons in 1979. Recently, Niethammer, de Pillis, and Varga have rekindled interest in this method by correcting and extending the SOR convergence interval. The purpose of our paper is to discuss an alternative formulation of the problem leading to a 2-block SOR method. For this formulation it is shown that the resulting direct-iterative method always converges for sufficiently small SOR parameter, in contrast to the 3-block formulation. Formulas for the optimum SOR parameter and the resulting asymptotic convergence factor, based upon 6A₂A^-1₁6₂, are given. Furthermore, it is shown that this 2-cyclic block SOR method always gives better convergence results than the 3-cyclic one for the same amount of work per iteration. The direct part of the algorithm requires only a sparse-matrix factorization of A₁. Our purpose here is to establish theoretical convergence results, in line with the purpose of the recent paper by Niethammer, de Pillis, and Varga. Practical considerations of choosing A₁ in certain applications and of estimating the resulting 6A₂A^-1₁6₂ will be addressed elsewhere.     

A stationary iterative pseudoinverse algorithm

Iterative methods applied to the normal equationsA ^T Ax=A ^T b are sometimes used for solving large sparse linear least squares problems. However, when the matrix is rank-deficient many methods, although convergent, fail to produce the unique solution of minimal Euclidean norm. Examples of such methods are the Jacobi and SOR methods as well as the preconditioned conjugate gradient algorithm. We analyze here an iterative scheme that overcomes this difficulty for the case of stationary iterative methods. The scheme combines two stationary iterative methods. The first method produces any least squares solution whereas the second produces the minimum norm solution to a consistent system. This work was supported by the Swedish Research Council for Engineering Sciences, TFR.     

Preconditioned sor methods for generalized least-squares problems

1.IntroductionThegeneralizedleastsquaresproblem,definedasmin(Ax--b)"W--'(Ax--b),(1.1)xacwhereAERm",m>n,bERm,andWERm'misasymmetricandpositivedefinitematrix,isfrequentlyfoundwhensolvingproblemsinstatistics,engineeringandeconomics.Forexample,wegetgeneralizedleastsquaresproblemswhensolvingnonlinearregressionanalysisbyquasi-likelihoodestimation,imagereconstructionproblemsandeconomicmodelsobtainedbythemaximumlikelihoodmethod(of.[1,21).Paige[3,4]investigatestheproblemexplicitly.Hechangestheorig…     

A note on the sufficient initial condition ensuring the convergence of directly extended 3-block ADMM for special semidefinite programming

ABSTRACT

In this note, we consider three types of problems, H-weighted nearest correlation matrix problem and two types of important doubly non-negative semidefinite programming, derived from the binary integer quadratic programming and maximum cut problem. The dual of these three types of problems is a 3-block separable convex optimization problem with a coupling linear equation constraint. It is known that, the directly extended 3-block alternating direction method of multipliers (ADMM3d) is more efficient than many of its variants for solving these convex optimization, but its convergence is not guaranteed. By choosing initial points properly, we obtain the convergence of ADMM3d for solving the dual of these three types of problems. Furthermore, we simplify the iterative scheme of ADMM3d and show the equivalence of ADMM3d to the 2-block semi-proximal ADMM for solving the dual's reformulation, under these initial conditions.     

A generalization of the HSS-based sequential two-stage method for solving non-Hermitian saddle point problems

For non-Hermitian saddle point problems with non-Hermitian positive definite (1,1)-block, Zhu et al. studied the HSS-based sequential two-stage method (see Zhu et al. Appl. Math. Comput. 242, 907–916 19). However, this approach may not work when the (1,1)-block of the saddle point problems is weakly Hermitian or skew-Hermitian dominant. By introducing a new preconditioning matrix, a generalization of the HSS-based sequential two-stage method is proposed for solving non-Hermitian saddle-point problems with non-Hermitian positive definite and Hermitian or skew-Hermitian dominant (1,1)-block. Theoretical analysis shows that the proposed iterative method is convergent. Numerical experiments are provided to confirm the theoretical results, which demonstrate that the generalized method is effective and feasible for solving saddle point problems with non-Hermitian positive definite and Hermitian or skew-Hermitian dominant (1,1)-block.     

A matrix-splitting method for symmetric affine second-order cone complementarity problems

The affine second-order cone complementarity problem (SOCCP) is a wide class of problems that contains the linear complementarity problem (LCP) as a special case. The purpose of this paper is to propose an iterative method for the symmetric affine SOCCP that is based on the idea of matrix splitting. Matrix-splitting methods have originally been developed for the solution of the system of linear equations and have subsequently been extended to the LCP and the affine variational inequality problem. In this paper, we first give conditions under which the matrix-splitting method converges to a solution of the affine SOCCP. We then present, as a particular realization of the matrix-splitting method, the block successive overrelaxation (SOR) method for the affine SOCCP involving a positive definite matrix, and propose an efficient method for solving subproblems. Finally, we report some numerical results with the proposed algorithm, where promising results are obtained especially for problems with sparse matrices.     

求解大型稀疏最小二乘问题的2—块PSD型迭代法

１引言假设Ａ为大型稀疏的ｍ×ｎ实矩阵（ｍ＞ｎ）,ｒａｎｋ（Ａ）＝ｎ,在实际中,常常需要求解Ａｘ＝ｂ,（１．１）其中ｂ为给定的ｍ维向量．求（１．１）的欧氏范数最小二乘解等价于求解其中ｒ为ｍ维向量,不失一般性,可令其中Ａ;为ｎ×ｎ满秩方阵,且把ｂ和ｒ也相应地分块为其中ｒ１和ｂ１都是ｎ维向量,用（１．３）和（１．４）的符号,（１．２）可写成等价形式如下相应的块Ｊａｃｏｂｉ迭代矩阵Ｂ２和Ｂ３,定义为Ｃ相应于ＢＬ的分块形式是Ｌ循环阵或是ＧＣＯ（１,Ｌ—１）阵或Ｔ（１,ｌ—１）阵,ＢＬ是指标为Ｌ的弱循环阵（…     

Semiconvergence of extrapolated iterative methods for singular linear systems

In this paper, we discuss convergence of the extrapolated iterative methods for solving singular linear systems. A general principle of extrapolation is presented. The semiconvergence of an extrapolated method induced by a regular splitting and a nonnegative splitting is proved whenever the coefficient matrix A is a singular M-matrix with ‘property c’ and an irreducible singular M-matrix, respectively. Since the (generalized, block) JOR and AOR methods are respectively the extrapolated methods of the (generalized, block) Jacobi and SOR methods, so the semiconvergence of the (generalized, block) JOR and AOR methods for solving general singular systems are proved. Furthermore, the semiconvergence of the extrapolated power method, the (block) JOR, AOR and SOR methods for solving Markov chains are discussed.     

A modified Gram–Schmidt algorithm with iterative orthogonalization and column pivoting

Iterative orthogonalization is aimed to ensure small deviation from orthogonality in the Gram–Schmidt process. Former applications of this technique are restricted to classical Gram–Schmidt (CGS) and column-oriented modified Gram–Schmidt (MGS). The major aim of this paper is to explain how iterative orthogonalization is incorporated into row-oriented MGS. The interest that we have in a row-oriented iterative MGS comes from the observation that this method is capable of performing column pivoting. The use of column pivoting delays the deteriorating effects of rounding errors and helps to handle rank-deficient least-squares problems.

A second modification proposed in this paper considers the use of Gram–Schmidt QR factorization for solving linear least-squares problems. The standard solution method is based on one orthogonalization of the r.h.s. vector b against the columns of Q. The outcome of this process is the residual vector, r^*, and the solution vector, x^*. The modified scheme is a natural extension of the standard solution method that allows it to apply iterative orthogonalization. This feature ensures accurate computation of small residuals and helps in cases when Q has some deviation from orthogonality.     

An iterative back substitution algorithm for the solution of tridiagonal matrix systems with fringes

For tridiagonal matrix systems, a simple direct algorithm giving the solution exists, but in the most general case of tridiagonal matrix with fringes, the direct solving algorithms are more complicated. For big systems, direct methods are not well fitted and iterative algorithms are preferable. In this paper a relaxation type iterative algorithm is presented. It is an extension of the backward substitution method used for simple tridiagonal matrix systems. The performances show that this algorithm is a good compromise between a direct method and other iterative methods as block SOR. Its nature suggests its use as inner solver in the solution of problems derived by application of a decomposition domain method. A special emphasis is done on the programming aspect. The solving Fortran subroutines implementing the algorithm have been generated automatically from their specification by using a computer algebra system technique.     

Splitting iterative methods for fuzzy system of linear equations

A class of splitting iterative methods is considered for solving fuzzy system of linear equations, which cover Jacobi, Gauss–Seidel, SOR, SSOR, and their block variants proposed by others before. We give a convergence theorem for a regular splitting, where the corresponding iterative methods converge to the strong fuzzy solution for any initial vector and fuzzy right-hand vector. Two schemes of splitting are given to illustrate the theorem. Numerical experiments further show the efficiency of the splitting iterative methods.     

关于“求解加权线性最小二乘问题的一类预处理GAOR方法”一文的注记

在"求解加权线性最小二乘问题的一类预处理GAOR方法"一文中,作者提出了求解加权线性最小二乘问题等价$2\times 2$块线性系统的一类预处理GAOR方法,并给出了几个比较定理来说明新提出预处理GAOR方法的优越性.本文我们将指出该文中几个比较定理的不完善之处和证明的错误之处,并给出正确的证明.     

A QMR-based interior-point algorithm for solving linear programs

A new approach for the implementation of interior-point methods for solving linear programs is proposed. Its main feature is the iterative solution of the symmetric, but highly indefinite 2×2-block systems of linear equations that arise within the interior-point algorithm. These linear systems are solved by a symmetric variant of the quasi-minimal residual (QMR) algorithm, which is an iterative solver for general linear systems. The symmetric QMR algorithm can be combined with indefinite preconditioners, which is crucial for the efficient solution of highly indefinite linear systems, yet it still fully exploits the symmetry of the linear systems to be solved. To support the use of the symmetric QMR iteration, a novel stable reduction of the original unsymmetric 3×3-block systems to symmetric 2×2-block systems is introduced, and a measure for a low relative accuracy for the solution of these linear systems within the interior-point algorithm is proposed. Some indefinite preconditioners are discussed. Finally, we report results of a few preliminary numerical experiments to illustrate the features of the new approach.     

DIRECT ITERATIVE METHODS FOR RANK DEFICIENT GENERALIZED LEAST SQUARES PROBLEMS

1. IntroductionThe generalized LS problemis frequently found in solving problems from statistics, engineering, economics, imageand signal processing. Here A e Rmxn with m 2 n, b E Re and W E Rmxm issymmetric positive definite. The large sparse rank deficient generalized LS problemsappeal in computational genetics when we consider mited linear model for tree oranimal genetics [2], [31, [5].Recentlyg Yuan [9] and [10], Yuan and lusem [11] considered direct iterative methodsfor the problem …     

On Two Iterative Least-Squares Finite Element Schemes for the Incompressible Navier–Stokes Problem

This paper is mainly devoted to a comparative study of two iterative least-squares finite element schemes for solving the stationary incompressible Navier–Stokes equations with velocity boundary condition. Introducing vorticity as an additional unknown variable, we recast the Navier–Stokes problem into a first-order quasilinear velocity–vorticity–pressure system. Two Picard-type iterative least-squares finite element schemes are proposed to approximate the solution to the nonlinear first-order problem. In each iteration, we adopt the usual L ² least-squares scheme or a weighted L ² least-squares scheme to solve the corresponding Oseen problem and provide error estimates. We concentrate on two-dimensional model problems using continuous piecewise polynomial finite elements on uniform meshes for both iterative least-squares schemes. Numerical evidences show that the iterative L ² least-squares scheme is somewhat suitable for low Reynolds number flow problems, whereas for flows with relatively higher Reynolds numbers the iterative weighted L ² least-squares scheme seems to be better than the iterative L ² least-squares scheme. Numerical simulations of the two-dimensional driven cavity flow are presented to demonstrate the effectiveness of the iterative least-squares finite element approach.     

Low-rank and sparse matrix recovery from noisy observations via 3-block ADMM algorithm

Recovering low-rank and sparse matrix from a given matrix arises in many applications, such as image processing, video background substraction, and so on. The 3-block alternating direction method of multipliers (ADMM) has been applied successfully to solve convex problems with 3-block variables. However, the existing sufficient conditions to guarantee the convergence of the 3-block ADMM usually require the penalty parameter $\gamma$ to satisfy a certain bound, which may affect the performance of solving the large scale problem in practice. In this paper, we propose the 3-block ADMM to recover low-rank and sparse matrix from noisy observations. In theory, we prove that the 3-block ADMM is convergent when the penalty parameters satisfy a certain condition and the objective function value sequences generated by 3-block ADMM converge to the optimal value. Numerical experiments verify that proposed method can achieve higher performance than existing methods in terms of both efficiency and accuracy.     

求解加权线性最小二乘问题的一类预处理GAOR方法

为了快速求解一类来自加权线性最小二乘问题的2×2块线性系统,本文提出一类新的预处理子用以加速GAOR方法,也就是新的预处理GAOR方法.得到了一些比较结果,这些结果表明当GAOR方法收敛时,新方法比原GAOR方法和之前的一些预处理GAOR方法有更好的收敛性.而且,数值算例也验证了新预处理子的有效性．