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.     

Solution of sparse linear least squares problems using givens rotations

We describe a direct method for solving sparse linear least squares problems. The storage required for the method is no more than that needed for the conventional normal equations approach. However, the normal equations are not computed; orthogonal transformations are applied to the coefficient matrix, thus avoiding the potential numerical instability associated with computing the normal equations. Our approach allows full exploitation of sparsity, and permits the use of a fixed (static) data structure during the numerical computation. Finally, the method processes the coefficient matrix one row at a time, allowing for the convenient use of auxiliary storage and updating operations.     

Stability of the solutions of linear least squares problems

Numerische Mathematik - In 1966 Golub and Wilkinson gave upper bounds for the errors of least squares solutions based on orthogonal transformations, in which the square of the condition number of...     

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)     

Solving bilinear tensor least squares problems and application to Hammerstein identification

Bilinear tensor least squares problems occur in applications such as Hammerstein system identification and social network analysis. A linearly constrained problem of medium size is considered, and nonlinear least squares solvers of Gauss–Newton‐type are applied to numerically solve it. The problem is separable, and the variable projection method can be used. Perturbation theory is presented and used to motivate the choice of constraint. Numerical experiments with Hammerstein models and random tensors are performed, comparing the different methods and showing that a variable projection method performs best.     

A contribution to perturbation analysis for total least squares problems

In this note, we present perturbation analysis for the total least squares (Tls) problems under the genericity condition. We review the three condition numbers proposed respectively by Zhou et al. (Numer. Algorithm, 51 (2009), pp. 381–399), Baboulin and Gratton (SIAM J. Matrix Anal. Appl. 32 (2011), pp. 685–699), Li and Jia (Linear Algebra Appl. 435 (2011), pp. 674–686). We also derive new perturbation bounds.     

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

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.     

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     

Sparse linear problems of the least squares method

One gives a survey of the direct method of solving large sparse diverse overdetermined linear systems of full column rank in the least squares sense. The survey covers practically all investigations on this topic, published in the seventies and in the beginning of the eighties.Translated from Itogi Nauki i Tekhniki, Seriya Matematicheskii Analiz, Vol. 23, pp. 219–285, 1985.     

A note on the least squares solution of the groundwater flow equation

The least squares finite element method is a member of the weighted residuals class of numerical methods for solving partial differential equations. The least squares finite element method is applied to the groundwater flow equation. Space is discretized with a C¹ continuous trial function and parameters are approximated with a C⁰ bilinear basis. Solutions for problems containing parameters with large localized spatial gradients are characterized by errors that are propagated throughout the entire domain. Second-order spatial convergence is observed, and extreme mesh refinement is required to match Galerkin and mixed least squares finite element results. Temporal discretization should be kept separate from the least squares spatial discretization. © 1994 John Wiley & Sons, Inc.     

Solving regularized total least squares problems via a sequence of eigenvalue problems

A computational approach for solving regularized total least squares problems via a sequence of eigenvalue problems has recently been introduced by Renaut and Guo. Combining this approach with thick starts using the nonlinear Arnoldi method lead to a very efficient method for large RTLS problems. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A note on an error estimate for least squares approximation

An asymptotic expansion is obtained which provides upper and lower bounds for the error of the bestL ₂ polynomial approximation of degreen forx ⁿ⁺¹ on [–1, 1]. Because the expansion proceeds in only even powers of the reciprocal of the large variable, and the error made by truncating the expansion is numerically less than, and has the same sign as the first neglected term, very good bounds can be obtained. Via a result of Phillips, these results can be extended fromx ⁿ⁺¹ to anyfC ⁿ⁺¹[–1, 1], provided upper and lower bounds for the modulus off ⁽ⁿ⁺¹⁾ are available.     

A note on extended least squares methods for cluster sampling

A class of linear models for a two-stage cluster sample is considered. The best linear unbiased predictor of the finite population total can be obtained through extended least squares under these models. The effort of computing the prediction variance of the predictor may be reduced.     

On derivative estimation and the solution of least squares problems

Surface interpolation finds application in many aspects of science and technology. Two specific areas of interest are surface reconstruction techniques for plant architecture and approximating cell face fluxes in the finite volume discretisation strategy for solving partial differential equations numerically. An important requirement of both applications is accurate local gradient estimation. In surface reconstruction this gradient information is used to increase the accuracy of the local interpolant, while in the finite volume framework accurate gradient information is essential to ensure second order spatial accuracy of the discretisation.