Accuracy and Stability of the Null Space Method for Solving the Equality Constrained Least Squares Problem

The null space method is a standard method for solving the linear least squares problem subject to equality constraints (the LSE problem). We show that three variants of the method, including one used in LAPACK that is based on the generalized QR factorization, are numerically stable. We derive two perturbation bounds for the LSE problem: one of standard form that is not attainable, and a bound that yields the condition number of the LSE problem to within a small constant factor. By combining the backward error analysis and perturbation bounds we derive an approximate forward error bound suitable for practical computation. Numerical experiments are given to illustrate the sharpness of this bound.     

等式约束不定最小二乘问题的双曲MGS消去算法

众所周知,加权法是解等式约束不定最小二乘问题的方法之一.通过探讨极限意义下,双曲MGS算法解对应加权问题的本质,得到一类消去算法.实验表明,该算法以和文献中现有的GHQR算法达到一样的精度,但实际计算量只需要GHQR算法的一半.     

Indefinite QR Factorization

Let A be a Hermitian positive definite matrix given by its rectangular factor G such that A=G^*G. It is well known that the Cholesky factorization of A is equivalent to the QR factorization of G. In this paper, an analogue of the QR factorization for Hermitian indefinite matrices is constructed. This problem has been considered by many authors, but the problem of zero diagonal elements has not been solved so far. Here we show how to overcome this difficulty. AMS subject classification (2000) 65F25, 46C20, 65F15     

双曲矩阵分解修正问题的一些结果

This paper considers the updating problem of the hyperbolic matrix factorizations. The sufficient conditions for the existence of the updated hyperbolic matrix factorizations are first provided. Then, some differential inequalities and first order perturbation expansions for the updated hyperbolic factors are derived. These results generalize the corresponding ones for the updating problem of the classical QR factorization obtained by Jiguang SUN.     

ImplicitQR factorization of a product of three matrices

We present a numerical algorithm for computing the implicit QR factorization of a product of three matrices, and we illustrate the technique by applying it to the generalized total least squares and the restricted total least squares problems. We also demonstrate how to take advantage of the block structures of the underlying matrices in order to reduce the computational work.     

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.     

Sparse Linear Least Squares Problems in Optimization

Numerical and computational aspects of direct methods for largeand sparseleast squares problems are considered. After a brief survey of the most oftenused methods, we summarize the important conclusions made from anumerical comparison in matlab. Significantly improved algorithms haveduring the last 10-15 years made sparse QR factorization attractive, andcompetitive to previously recommended alternatives. Of particular importanceis the multifrontal approach, characterized by low fill-in, dense subproblemsand naturally implemented parallelism. We describe a Householder multifrontalscheme and its implementation on sequential and parallel computers. Availablesoftware has in practice a great influence on the choice of numericalalgorithms. Less appropriate algorithms are thus often used solely because ofexisting software packages. We briefly survey softwarepackages for the solution of sparse linear least squares problems. Finally,we focus on various applications from optimization, leading to the solution oflarge and sparse linear least squares problems. In particular, we concentrateon the important case where the coefficient matrix is a fixed general sparsematrix with a variable diagonal matrix below. Inner point methods forconstrained linear least squares problems give, for example, rise to suchsubproblems. Important gains can be made by taking advantage of structure.Closely related is also the choice of numerical method for these subproblems.We discuss why the less accurate normal equations tend to be sufficient inmany applications.     

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.     

关于酉对称矩阵的QR分解及其算法

为了简化大型行(列)酉对称矩阵的QR分解,研究了行(列)酉对称矩阵的性质,获得了一些新的结果,给出了行(列)酉对称矩阵的QR分解的公式和快速算法,它们可极大地减少行(列)酉对称矩阵的QR分解的计算量与存储量,并且不会丧失数值精度.同时推广和丰富了邹红星等(2002)的研究内容,拓宽了实际应用领域的范围.     

QR factorization for row or column symmetric matrix

The problem of fast computing the QR factorization of row or column symmetric matrix is considered. We address two new algorithms based on a correspondence of Q and R matrices between the row or column symmetric matrix and its mother matrix. Theoretical analysis and numerical evidence show that, for a class of row or column symmetric matrices, the QR factorization using the mother matrix rather than the row or column symmetric matrix per se can save dramatically the CPU time and memory without loss of any numerical precision.     

A block Cholesky-LU-based QR factorization for rectangular matrices

The Householder method provides a stable algorithm to compute the full QR factorization of a general matrix. The standard version of the algorithm uses a sequence of orthogonal reflections to transform the matrix into upper triangular form column by column. In order to exploit (level 3 BLAS or structured matrix) computational advantages for block-partitioned algorithms, we develop a block algorithm for the QR factorization. It is based on a well-known block version of the Householder method which recursively divides a matrix columnwise into two smaller matrices. However, instead of continuing the recursion down to single matrix columns, we introduce a novel way to compute the QR factors in implicit Householder representation for a larger block of several matrix columns, that is, we start the recursion at a block level instead of a single column. Numerical experiments illustrate to what extent the novel approach trades some of the stability of Householder's method for the computational efficiency of block methods.     

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 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.     

Sparse bivariate polynomial factorization

Motivated by Sasaki’s work on the extended Hensel construction for solving multivariate algebraic equations, we present a generalized Hensel lifting, which takes advantage of sparsity, for factoring bivariate polynomial over the rational number field. Another feature of the factorization algorithm presented in this article is a new recombination method, which can solve the extraneous factor problem before lifting based on numerical linear algebra. Both theoretical analysis and experimental data show that the algorithm is efficient, especially for sparse bivariate polynomials.     

New perturbation bounds and condition numbers for the hyperbolic QR factorization

Using the modified matrix-vector equation approach, the technique of Lyapunov majorant function and the Banach fixed point theorem, we obtain some new rigorous perturbation bounds for R factor of the hyperbolic QR factorization under normwise perturbation. These bounds are always tighter than the one given in the literature. Moreover, the optimal first-order perturbation bounds and the normwise condition numbers for the hyperbolic QR factorization are also presented.     

An Exact Least Trimmed Squares Algorithm for a Range of Coverage Values

A new algorithm to solve exact least trimmed squares (LTS) regression is presented. The adding row algorithm (ARA) extends existing methods that compute the LTS estimator for a given coverage. It employs a tree-based strategy to compute a set of LTS regressors for a range of coverage values. Thus, prior knowledge of the optimal coverage is not required. New nodes in the regression tree are generated by updating the QR decomposition of the data matrix after adding one observation to the regression model. The ARA is enhanced by employing a branch and bound strategy. The branch and bound algorithm is an exhaustive algorithm that uses a cutting test to prune nonoptimal subtrees. It significantly improves over the ARA in computational performance. Observation preordering throughout the traversal of the regression tree is investigated. A computationally efficient and numerically stable calculation of the bounds using Givens rotations is designed around the QR decomposition, avoiding the need to explicitly update the triangular factor when an observation is added. This reduces the overall computational load of the preordering device by approximately half. A solution is proposed to allow preordering when the model is underdetermined. It employs pseudo-orthogonal rotations to downdate the QR decomposition. The strategies are illustrated by example. Experimental results confirm the computational efficiency of the proposed algorithms. Supplemental materials (R package and formal proofs) are available online.     

Regularization Using QR Factorization and the Estimation of the Optimal Parameter

In this paper we propose a direct regularization method using QR factorization for solving linear discrete ill-posed problems. The decomposition of the coefficient matrix requires less computational cost than the singular value decomposition which is usually used for Tikhonov regularization. This method requires a parameter which is similar to the regularization parameter of Tikhonov's method. In order to estimate the optimal parameter, we apply three well-known parameter choice methods for Tikhonov regularization.This revised version was published online in October 2005 with corrections to the Cover Date.     

Perturbation analysis for the symplectic QR factorization

In this paper, the perturbation analysis for the symplectic QR factorization is considered. Some first-order and rigorous normwise perturbation bounds with normwise or componentwise perturbations in the given matrix are presented.     

An algorithm for solving the indefinite least squares problem with equality constraints

An algorithm for computing the solution of indefinite least squares problems and of indefinite least squares problems with equality constrained is presented. Such problems arise when solving total least squares problems and in H ^∞-smoothing. The proposed algorithm relies only on stable orthogonal transformations reducing recursively the associated augmented matrix to proper block anti-triangular form. Some numerical results are reported showing the properties of the algorithm.     

A parallel multisplitting solution of the least squares problem

The linear least squares problem, min_x∥Ax − b∥₂, is solved by applying a multisplitting (MS) strategy in which the system matrix is decomposed by columns into p blocks. The b and x vectors are partitioned consistently with the matrix decomposition. The global least squares problem is then replaced by a sequence of local least squares problems which can be solved in parallel by MS. In MS the solutions to the local problems are recombined using weighting matrices to pick out the appropriate components of each subproblem solution. A new two-stage algorithm which optimizes the global update each iteration is also given. For this algorithm the updates are obtained by finding the optimal update with respect to the weights of the recombination. For the least squares problem presented, the global update optimization can also be formulated as a least squares problem of dimension p. Theoretical results are presented which prove the convergence of the iterations. Numerical results which detail the iteration behavior relative to subproblem size, convergence criteria and recombination techniques are given. The two-stage MS strategy is shown to be effective for near-separable problems. © 1998 John Wiley & Sons, Ltd.