On Frobenius normwise condition numbers for Moore–Penrose inverse and linear least‐squares problems

Condition numbers play an important role in numerical analysis. Classical condition numbers are normwise: they measure the size of both input perturbations and output errors using norms. In this paper, we give explicit, computable expressions depending on the data, for the normwise condition numbers for the computation of the Moore–Penrose inverse as well as for the solutions of linear least‐squares problems with full‐column rank. Copyright © 2007 John Wiley & Sons, Ltd.     

A note on stable perturbations of Moore–Penrose inverses

Perturbation bounds for Moore–Penrose inverses of rectangular matrices play a significant role in the perturbation analysis for linear least squares problems. In this note, we derive a sharp upper bound for Moore–Penrose inverses, which is better than a well known existing one. Copyright © 2011 John Wiley & Sons, Ltd.     

The condition numbers for weighted Moore-Penrose inverse and weighted linear least squares problem

Condition numbers play an important role in numerical analysis. Classical normise condition numbers are used to measure the size of both input perturbations and output errors. In this paper, we study the weighted normwise relative condition numbers for the weighted Moore-Penrose inverse and the weighted linear least-squares (WLS) problems in the case of the full-column rank matrix. The bounds or formulas for the weighted condition numbers are presented. The obtained results can be viewed as extensions of the earlier works studied by others.     

On mixed and componentwise condition numbers for Moore-Penrose inverse and linear least squares problems

Classical condition numbers are normwise: they measure the size of both input perturbations and output errors using some norms. To take into account the relative of each data component, and, in particular, a possible data sparseness, componentwise condition numbers have been increasingly considered. These are mostly of two kinds: mixed and componentwise. In this paper, we give explicit expressions, computable from the data, for the mixed and componentwise condition numbers for the computation of the Moore-Penrose inverse as well as for the computation of solutions and residues of linear least squares problems. In both cases the data matrices have full column (row) rank.

     

On the Moore–Penrose inverse in solving saddle‐point systems with singular diagonal blocks

This paper deals with the role of the generalized inverses in solving saddle‐point systems arising naturally in the solution of many scientific and engineering problems when finite‐element tearing and interconnecting based domain decomposition methods are used to the numerical solution. It was shown that the Moore–Penrose inverse may be obtained in this case at negligible cost by projecting an arbitrary generalized inverse using orthogonal projectors. Applying an eigenvalue analysis based on the Moore–Penrose inverse, we proved that for simple model problems, the number of conjugate gradient iterations required for the solution of associate dual systems does not depend on discretization norms. The theoretical results were confirmed by numerical experiments with linear elasticity problems. Copyright © 2011 John Wiley & Sons, Ltd.     

A condition analysis of the weighted linear least squares problem using dual norms

In this paper, based on the theory of adjoint operators and dual norms, we define condition numbers for a linear solution function of the weighted linear least squares problem. The explicit expressions of the normwise and componentwise condition numbers derived in this paper can be computed at low cost when the dimension of the linear function is low due to dual operator theory. Moreover, we use the augmented system to perform a componentwise perturbation analysis of the solution and residual of the weighted linear least squares problems. We also propose two efficient condition number estimators. Our numerical experiments demonstrate that our condition numbers give accurate perturbation bounds and can reveal the conditioning of individual components of the solution. Our condition number estimators are accurate as well as efficient.     

Perturbation analysis for mixed least squares–total least squares problems

In many linear parameter estimation problems, one can use the mixed least squares–total least squares (MTLS) approach to solve them. This paper is devoted to the perturbation analysis of the MTLS problem. Firstly, we present the normwise, mixed, and componentwise condition numbers of the MTLS problem, and find that the normwise, mixed, and componentwise condition numbers of the TLS problem and the LS problem are unified in the ones of the MTLS problem. In the analysis of the first‐order perturbation, we first provide an upper bound based on the normwise condition number. In order to overcome the problems encountered in calculating the normwise condition number, we give an upper bound for computing more effectively for the MTLS problem. As two estimation techniques for solving the linear parameter estimation problems, interesting connections between their solutions, their residuals for the MTLS problem, and the LS problem are compared. Finally, some numerical experiments are performed to illustrate our results.     

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.     

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.     

Removal of blur in images based on least squares solutions

We propose an image restoration method. The method generalizes image restoration algorithms that are based on the Moore–Penrose solution of certain matrix equations that define the linear motion blur. Our approach is based on the usage of least squares solutions of these matrix equations, wherein an arbitrary matrix of appropriate dimensions is included besides the Moore–Penrose inverse. In addition, the method is a useful tool for improving results obtained by other image restoration methods. Toward that direction, we investigate the case where the arbitrary matrix is replaced by the matrix obtained by the Haar basis reconstructed image. The method has been tested by reconstructing an image after the removal of blur caused by the uniform linear motion and filtering the noise that is corrupted with the image pixels. The quality of the restoration is observable by a human eye. Benefits of using the method are illustrated by the values of the improvement in signal‐to‐noise ratio and in the values of peak signal‐to‐noise ratio. Copyright © 2013 John Wiley & Sons, Ltd.     

Fast enclosure for the minimum norm least squares solution of the matrix equation AXB = C

Fast algorithms for enclosing the minimum norm least squares solution of the matrix equation AXB = C are proposed. To develop these algorithms, theories for obtaining error bounds of numerical solutions are established. The error bounds obtained by these algorithms are verified in the sense that all the possible rounding errors have been taken into account. Techniques for accelerating the enclosure and obtaining smaller error bounds are introduced. Numerical results show the properties of the proposed algorithms. Copyright © 2015 John Wiley & Sons, Ltd.     

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.     

Computing the conditioning of the components of a linear least‐squares solution

In this paper, we address the accuracy of the results for the overdetermined full rank linear least‐squares problem. We recall theoretical results obtained in (SIAM J. Matrix Anal. Appl. 2007; 29 (2):413–433) on conditioning of the least‐squares solution and the components of the solution when the matrix perturbations are measured in Frobenius or spectral norms. Then we define computable estimates for these condition numbers and we interpret them in terms of statistical quantities when the regression matrix and the right‐hand side are perturbed. In particular, we show that in the classical linear statistical model, the ratio of the variance of one component of the solution by the variance of the right‐hand side is exactly the condition number of this solution component when only perturbations on the right‐hand side are considered. We explain how to compute the variance–covariance matrix and the least‐squares conditioning using the libraries LAPACK (LAPACK Users' Guide (3rd edn). SIAM: Philadelphia, 1999) and ScaLAPACK (ScaLAPACK Users' Guide. SIAM: Philadelphia, 1997) and we give the corresponding computational cost. Finally we present a small historical numerical example that was used by Laplace (Théorie Analytique des Probabilités. Mme Ve Courcier, 1820; 497–530) for computing the mass of Jupiter and a physical application if the area of space geodesy. Copyright © 2008 John Wiley & Sons, Ltd.     

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.     

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.     

Accuracy of Gram–Schmidt orthogonalization and Householder transformation for the solution of linear least squares problems

Accuracy of a Gram–Schmidt algorithm for the solution of linear least squares equations is compared with accuracy of least squares subroutines in three highly respected mathematical packages that use Householder transformations. Results from the four programs for 13 test problems were evaluated at 16 digit precision on four different desktop computers using four different compilers. Singular values obtained from the different programs are compared and the effect of pivoting to improve the accuracy is discussed. Solution vectors from the program using the Gram–Schmidt algorithm were generally more accurate or comparable to solution vectors from the programs using the Householder transformations. © 1997 John Wiley & Sons, Ltd.     

Procrustes problems and inverse eigenproblems for multilevel block α‐circulants

Let n = (n₁,n₂,…,n_k) and α = (α₁,α₂,…,α_k) be integer k‐tuples with α_i∈{1,2,…,n_i?1} and for all i = 1,2,…,k. Multilevel block α ‐circulants are (k + 1)‐level block matrices, where the first k levels have the block α_i‐circulant structure with orders and the entries in the (k + 1)‐st level are unstructured rectangular matrices with the same size . When k = 1, Trench discussed on his paper "Inverse problems for unilevel block α‐circulants" the Procrustes problems and inverse problems of unilevel block α‐circulants and their approximations. But the results are not perfect for the case gcd( α , n ) > 1 (i.e., gcd(α₁,n₁) > 1). In this paper, we also discuss Procrustes problems for multilevel block α ‐circulants. Our results can further make up for the deficiency when k = 1. When , inverse eigenproblems for this kind of matrices are also solved. By using the related results, we can design an artificial Hopfield neural network system that possesses the prescribed equilibria, where the Jacobian matrix of this system has the constrained multilevel α ‐circulative structure. Finally, some examples are employed to illustrate the effectiveness of the proposed results. Copyright © 2016 John Wiley & Sons, Ltd.     

Inverse scattering problem for Sturm–Liouville operator with nonlinear dependence on the spectral parameter in the boundary condition

The inverse problem of the scattering theory for Sturm–Liouville operator on the half line with boundary condition depending quadratic on the spectral parameter is considered. Scattering data are defined, some properties of the scattering data are examined, the main equation is obtained, solvability of the integral equation is proved and uniqueness of algorithm to the potential with given scattering data is studied. Copyright © 2010 John Wiley & Sons, Ltd.     

On the subdomain‐Galerkin/least squares method for 2‐ and 3‐D mixed elliptic problems with reaction terms

In this article we apply the subdomain‐Galerkin/least squares method, which is first proposed by Chang and Gunzburger for first‐order elliptic systems without reaction terms in the plane, to solve second‐order non‐selfadjoint elliptic problems in two‐ and three‐dimensional bounded domains with triangular or tetrahedral regular triangulations. This method can be viewed as a combination of a direct cell vertex finite volume discretization step and an algebraic least‐squares minimization step in which the pressure is approximated by piecewise linear elements and the flux by the lowest order Raviart‐Thomas space. This combined approach has the advantages of both finite volume and least‐squares methods. Among other things, the combined method is not subject to the Ladyzhenskaya‐Babus?ka‐Brezzi condition, and the resulting linear system is symmetric and positive definite. An optimal error estimate in the H¹(Ω) × H(div; Ω) norm is derived. An equivalent residual‐type a posteriori error estimator is also given. © 2002 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 18: 738–751, 2002; Published online in Wiley InterScience (www.interscience.wiley.com); DOI 10.1002/num.10030.