A Faster and Simpler Recursive Algorithm for the LAPACK Routine DGELS

We present new algorithms for computing the linear least squares solution to overdetermined linear systems and the minimum norm solution to underdetermined linear systems. For both problems, we consider the standard formulation min AX – B _F and the transposed formulation min A ^T X – B _F , i.e, four different problems in all. The functionality of our implementation corresponds to that of the LAPACK routine DGELS. The new implementation is significantly faster and simpler. It outperforms the LAPACK DGELS for all matrix sizes tested. The improvement is usually 50–100% and it is as high as 400%. The four different problems of DGELS are essentially reduced to two, by use of explicit transposition of A. By explicit transposition we avoid computing Householder transformations on vectors with large stride. The QR factorization of block columns of A is performed using a recursive level-3 algorithm. By interleaving updates of B with the factorization of A, we reduce the number of floating point operations performed for the linear least squares problem. By avoiding redundant computations in the update of B we reduce the work needed to compute the minimum norm solution. Finally, we outline fully recursive algorithms for the four problems of DGELS as well as for QR factorization.This revised version was published online in October 2005 with corrections to the Cover Date.     

A note on the complex semi‐definite matrix Procrustes problem

This note outlines an algorithm for solving the complex ‘matrix Procrustes problem’. This is a least‐squares approximation over the cone of positive semi‐definite Hermitian matrices, which has a number of applications in the areas of Optimization, Signal Processing and Control. The work generalizes the method of Allwright (SIAM J. Control Optim. 1988; 26 (3):537–556), who obtained a numerical solution to the real‐valued version of the problem. It is shown that, subject to an appropriate rank assumption, the complex problem can be formulated in a real setting using a matrix‐dilation technique, for which the method of Allwright is applicable. However, this transformation results in an over‐parametrization of the problem and, therefore, convergence to the optimal solution is slow. Here, an alternative algorithm is developed for solving the complex problem, which exploits fully the special structure of the dilated matrix. The advantages of the modified algorithm are demonstrated via a numerical example. Copyright © 2007 John Wiley & Sons, Ltd.     

矩阵方程AXB+CY D=E的三对角中心对称极小范数最小二乘解

本文研究了矩阵方程AXB+CY D=E的三对角中心对称极小范数最小二乘解问题.利用矩阵的Kronecker积和Moore-Penrose广义逆方法,得到了矩阵方程AXB+CY D=E的三对角中心对称极小范数最小二乘解的表达式.     

Condition numbers and perturbation analysis for the Tikhonov regularization of discrete ill‐posed problems

One of the most successful methods for solving the least‐squares problem min_x∥Ax?b∥₂ with a highly ill‐conditioned or rank deficient coefficient matrix A is the method of Tikhonov regularization. In this paper, we derive the normwise, mixed and componentwise condition numbers and componentwise perturbation bounds for the Tikhonov regularization. Our results are sharper than the known results. Some numerical examples are given to illustrate our results. Copyright © 2010 John Wiley & Sons, Ltd.     

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.     

The structured total least‐squares approach for non‐linearly structured matrices

In this paper, an extension of the structured total least‐squares (STLS) approach for non‐linearly structured matrices is presented in the so‐called ‘Riemannian singular value decomposition’ (RiSVD) framework. It is shown that this type of STLS problem can be solved by solving a set of Riemannian SVD equations. For small perturbations the problem can be reformulated into finding the smallest singular value and the corresponding right singular vector of this Riemannian SVD. A heuristic algorithm is proposed. Some examples of Vandermonde‐type matrices are used to demonstrate the improved accuracy of the obtained parameter estimator when compared to other methods such as least squares (LS) or total least squares (TLS). Copyright © 2002 John Wiley & Sons, Ltd.     

Backward Error Bounds for Constrained Least Squares Problems

We derive an upper bound on the normwise backward error of an approximate solution to the equality constrained least squares problem min _Bx=d b – Ax₂. Instead of minimizing over the four perturbations to A, b, B and d, we fix those to B and d and minimize over the remaining two; we obtain an explicit solution of this simplified minimization problem. Our experiments show that backward error bounds of practical use are obtained when B and d are chosen as the optimal normwise relative backward perturbations to the constraint system, and we find that when the bounds are weak they can be improved by direct search optimization. We also derive upper and lower backward error bounds for the problem of least squares minimization over a sphere: .     

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.     

Least‐squares solutions and least‐rank solutions of the matrix equation AXA* = B and their relations

A Hermitian matrix X is called a least‐squares solution of the inconsistent matrix equation AXA^* = B, where B is Hermitian. A^* denotes the conjugate transpose of A if it minimizes the F‐norm of B ? AXA^*; it is called a least‐rank solution of AXA^* = B if it minimizes the rank of B ? AXA^*. In this paper, we study these two types of solutions by using generalized inverses of matrices and some matrix decompositions. In particular, we derive necessary and sufficient conditions for the two types of solutions to coincide. Copyright © 2012 John Wiley & Sons, Ltd.     

ON THE ACCURACY OF THE LEAST SQUARES AND THE TOTAL LEAST SQUARES METHODS

Consider solving an overdetermined system of linear algebraic equations by both the least squares method (LS) and the total least squares method (TLS). Extensive published computational evidence shows that when the original system is consistent. one often obtains more accurate solutions by using the TLS method rather than the LS method. These numerical observations contrast with existing analytic perturbation theories for the LS and TLS methods which show that the upper bounds for the LS solution are always smaller than the corresponding upper bounds for the TLS solutions. In this paper we derive a new upper bound for the TLS solution and indicate when the TLS method can be more accurate than the LS method.Many applied problems in signal processing lead to overdetermined systems of linear equations where the matrix and right hand side are determined by the experimental observations (usually in the form of a lime series). It often happens that as the number of columns of the matrix becomes larger, the ra     

Least‐squares method for the Oseen equation

This article studies the least‐squares finite element method for the linearized, stationary Navier–Stokes equation based on the stress‐velocity‐pressure formulation in d dimensions (d = 2 or 3). The least‐squares functional is simply defined as the sum of the squares of the L² norm of the residuals. It is shown that the homogeneous least‐squares functional is elliptic and continuous in the norm. This immediately implies that the a priori error estimate of the conforming least‐squares finite element approximation is optimal in the energy norm. The L² norm error estimate for the velocity is also established through a refined duality argument. Moreover, when the right‐hand side f belongs only to , we derive an a priori error bound in a weaker norm, that is, the norm. © 2016 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 1289–1303, 2016     

The conditioning of least‐squares problems in variational data assimilation

In variational data assimilation a least‐squares objective function is minimised to obtain the most likely state of a dynamical system. This objective function combines observation and prior (or background) data weighted by their respective error statistics. In numerical weather prediction, data assimilation is used to estimate the current atmospheric state, which then serves as an initial condition for a forecast. New developments in the treatment of observation uncertainties have recently been shown to cause convergence problems for this least‐squares minimisation. This is important for operational numerical weather prediction centres due to the time constraints of producing regular forecasts. The condition number of the Hessian of the objective function can be used as a proxy to investigate the speed of convergence of the least‐squares minimisation. In this paper we develop novel theoretical bounds on the condition number of the Hessian. These new bounds depend on the minimum eigenvalue of the observation error covariance matrix and the ratio of background error variance to observation error variance. Numerical tests in a linear setting show that the location of observation measurements has an important effect on the condition number of the Hessian. We identify that the conditioning of the problem is related to the complex interactions between observation error covariance and background error covariance matrices. Increased understanding of the role of each constituent matrix in the conditioning of the Hessian will prove useful for informing the choice of correlated observation error covariance matrix and observation location, particularly for practical applications.     

Parallel variable distribution for total least squares

A novel parallel method for determining an approximate total least squares (TLS) solution is introduced. Based on domain decomposition, the global TLS problem is partitioned into several dependent TLS subproblems. A convergent algorithm using the parallel variable distribution technique (SIAM J. Optim. 1994; 4 :815–832) is presented. Numerical results support the development and analysis of the algorithms. Copyright © 2005 John Wiley & Sons, Ltd.     

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.     

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.     

On greedy randomized coordinate descent methods for solving large linear least‐squares problems

For solving large scale linear least‐squares problem by iteration methods, we introduce an effective probability criterion for selecting the working columns from the coefficient matrix and construct a greedy randomized coordinate descent method. It is proved that this method converges to the unique solution of the linear least‐squares problem when its coefficient matrix is of full rank, with the number of rows being no less than the number of columns. Numerical results show that the greedy randomized coordinate descent method is more efficient than the randomized coordinate descent method.     

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.     

Analysis and computation of least‐squares methods for a compressible Stokes problem

We develop and analyze a negative norm least‐squares method for the compressible Stokes equations with an inflow boundary condition. Least‐squares principles are derived for a first‐order form of the equations obtained by using ω = ?×u and φ = ? · u as new dependent variables. The resulting problem is incompletely elliptic, i.e., it combines features of elliptic and hyperbolic equations. As a result, well‐posedness of least‐squares functionals cannot be established using the ADN elliptic theory and so we use direct approaches to prove their norm‐equivalence. The article concludes with numerical examples that illustrate the theoretical convergence rates. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

An analysis for the compressible Stokes equations by first‐order system of least‐squares finite element method

This article applies the first‐order system least‐squares (fosls) finite element method developed by Cai, Manteuffel and McCormick to the compressible Stokes equations. By introducing a new dependent velocity flux variable, we recast the compressible Stokes equations as a first‐order system. Then it is shown that the ellipticity and continuity hold for the least‐squares functionals employing the mixture of H^?1 and L², so that the fosls finite element methods yield best approximations for the velocity flux and velocity. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17:689–699, 2001     

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.