Linear least squares problems with data over incomplete grids

The paper addresses bivariate surface fitting problems, where data points lie on the vertices of a rectangular grid. Efficient and stable algorithms can be found in the literature to solve such problems. If data values are missing at some grid points, there exists a computational method for finding a least squares spline by fixing appropriate values for the missing data. We extended this technique to arbitrary least squares problems as well as to linear least squares problems with linear equality constraints. Numerical examples are given to show the effectiveness of the technique presented. AMS subject classification (2000)  65D05, 65D07, 65D10, 65F05, 65F20     

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.     

Circle fitting by linear and nonlinear least squares

The problem of determining the circle of best fit to a set of points in the plane (or the obvious generalization ton-dimensions) is easily formulated as a nonlinear total least-squares problem which may be solved using a Gauss-Newton minimization algorithm. This straight-forward approach is shown to be inefficient and extremely sensitive to the presence of outliers. An alternative formulation allows the problem to be reduced to a linear least squares problem which is trivially solved. The recommended approach is shown to have the added advantage of being much less sensitive to outliers than the nonlinear least squares approach.This work was completed while the author was visiting the Numerical Optimisation Centre, Hatfield Polytechnic and benefitted from the encouragement and helpful suggestions of Dr. M. C. Bartholomew-Biggs and Professor L. C. W. Dixon.     

Least Squares Solution of Bivariate Surface Fitting Problems Using Tensor Product Splines

The paper treats bivariate surface fitting problems, where the data points lie on lines parallel to one of the axes. The associated bivariate collocation matrix is investigated as a block Kronecker product of univariate collocation matrices. Based on various properties of this block Kronecker product, such scattered data are characterized where the associated interpolation problem using tensor product splines admits a unique solution.     

Practical alternating least squares for tensor ring decomposition

Tensor ring (TR) decomposition has been widely applied as an effective approach in a variety of applications to discover the hidden low-rank patterns in multidimensional and higher-order data. A well-known method for TR decomposition is the alternating least squares (ALS). However, solving the ALS subproblems often suffers from high cost issue, especially for large-scale tensors. In this paper, we provide two strategies to tackle this issue and design three ALS-based algorithms. Specifically, the first strategy is used to simplify the calculation of the coefficient matrices of the normal equations for the ALS subproblems, which takes full advantage of the structure of the coefficient matrices of the subproblems and hence makes the corresponding algorithm perform much better than the regular ALS method in terms of computing time. The second strategy is to stabilize the ALS subproblems by QR factorizations on TR-cores, and hence the corresponding algorithms are more numerically stable compared with our first algorithm. Extensive numerical experiments on synthetic and real data are given to illustrate and confirm the above results. In addition, we also present the complexity analyses of the proposed algorithms.     

基于最小二乘近似的模型平均方法

本文提出基于最小二乘近似的模型平均方法.该方法可用于线性模型、广义线性模型和分位数回归等各种常用模型.特别地,经典的Mallows模型平均方法是该方法的特例.现存的模型平均文献中,渐近分布的证明一般需要局部误设定假设,所得的极限分布的形式也比较复杂.本文将在不使用局部误设定假设的情形下证明该方法的渐近正态性.另外,本文...     

Solution of linear least squares via the ABS algorithm

The ABS class for linear and nonlinear systems has been recently introduced by Abaffy, Broyden, Galantai and Spedicato. Here we consider various ways of applying these algorithms to the determination of the minimal euclidean norm solution of over-determined linear systems in the least squares sense. Extensive numerical experiments show that the proposed algorithms are efficient and that one of them usually gives better accuracy than standard implementations of the QR orthogonalization algorithm with Householder reflections.     

On stable least squares solution to the system of linear inequalities

The system of inequalities is transformed to the least squares problem on the positive ortant. This problem is solved using orthogonal transformations which are memorized as products. Author’s previous paper presented a method where at each step all the coefficients of the system were transformed. This paper describes a method applicable also to large matrices. Like in revised simplex method, in this method an auxiliary matrix is used for the computations. The algorithm is suitable for unstable and degenerate problems primarily.      

An algorithm for least squares analysis of spectroscopic data

This paper describes a variant of the Gauss-Newton-Hartley algorithm for nonlinear least squares, in which aQR implementation is used to solve the linear least squares problem. We follow Grey's idea of updating variables at intermediate stages of the orthogonalization. This technique, applied in partitions identified with known or suspected spectral lines, appears to be especially suited to the analysis of spectroscopic data. We suggest that this algorithm is an attractive candidate for the optimization role in Ekenberg's interactive computer graphics curve fitting program.     

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.     

Implicitly-weighted total least squares

In a total least squares (TLS) problem, we estimate an optimal set of model parameters X, so that (A-ΔA)X=B-ΔB, where A is the model matrix, B is the observed data, and ΔA and ΔB are corresponding corrections. When B is a single vector, Rao (1997) and Paige and Strakoš (2002) suggested formulating standard least squares problems, for which ΔA=0, and data least squares problems, for which ΔB=0, as weighted and scaled TLS problems. In this work we define an implicitly-weighted TLS formulation (ITLS) that reparameterizes these formulations to make computation easier. We derive asymptotic properties of the estimates as the number of rows in the problem approaches infinity, handling the rank-deficient case as well. We discuss the role of the ratio between the variances of errors in A and B in choosing an appropriate parameter in ITLS. We also propose methods for computing the family of solutions efficiently and for choosing the appropriate solution if the ratio of variances is unknown. We provide experimental results on the usefulness of the ITLS family of solutions.     

Bivariate Free Knot Splines

We consider the least squares approximation of gridded 2D data by tensor product splines with free knots. The smoothing functional to be minimized—a generalization of the univariate Schoenberg functional—is chosen in such a way that the solution of the bivariate problem separates into the solution of a sequence of univariate problems in case of fixed knots. The resulting optimization problem is a constrained separable least squares problem with tensor product structure. Based on some ideas developed by the authors for the univariate case, an efficient method for solving the specially structured 2D problem is proposed, analyzed and tested on hand of some examples from the literature.     

Least squares approximation by splines with free knots

Suppose we are given noisy data which are considered to be perturbed values of a smooth, univariate function. In order to approximate these data in the least squares sense, a linear combination of B-splines is used where the tradeoff between smoothness and closeness of the fit is controlled by a smoothing term which regularizes the least squares problem and guarantees unique solvability independent of the position of knots. Moreover, a subset of the knot sequence which defines the B-splines, the so-calledfree knots, is included in the optimization process.The resulting constrained least squares problem which is linear in the spline coefficients but nonlinear in the free knots is reduced to a problem that has only the free knots as variables. The reduced problem is solved by a generalized Gauss-Newton method. The method developed can be combined with a knot removal strategy in order to obtain an approximating spline with as few parameters as possible.Dedicated to Professor Dr.-Ing. habil. Dr. h.c. Helmut Heinrich on the occasion of his 90th birthdayResearch of the second author was partly supported by Deutsche Forschungsgemeinschaft under grant Schm 968/2-1.     

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.     

Real structure-preserving algorithm for quaternion equality constrained least squares problem

Quaternion equality constrained least squares problem is an extremely effective tool in studying quantum mechanics and quantum field theory. However, the computation of the quaternion equality constrained least squares problem is extremely complex. In this paper, we first prove that quaternion equality constrained least squares problem is equivalent to weighted quaternion least squares problem when the parameter $\tau \to +\infty$. Then, for weighted quaternion least squares problem, applying the special structure of real representation of quaternion, we propose real structure–preserving algorithm to obtain the solution of quaternion equality contained least squares problem. At last, we give numerical examples to illustrate the effectiveness of our method.     

On nonlinear weighted total least squares parameter estimation problem for the three-parameter Weibull density

The three-parameter Weibull density function is widely employed as a model in reliability and lifetime studies. Estimation of its parameters has been approached in the literature by various techniques, because a standard maximum likelihood estimate does not exist. In this paper we consider the nonlinear weighted total least squares fitting approach. As a main result, a theorem on the existence of the total least squares estimate is obtained, as well as its generalization in the total _lq$l_q$ norm (q?1$q?1$). Some numerical simulations to support the theoretical work are given.     

ECLES: A general method for local editing of parameters with linear constraints

We describe ECLES (Editing by Constrained LEast Squares), a general method for interactive local editing of objects that are defined by a list of parameters subject to a set of linear or affine constraints. The method is intended for situations where each edit action affects only a small set of the parameters; some of which (the “anchors”) are to be set to new given values, whereas the rest (the “derived” ones) are to be modified so as to preserve the constraints. We use exact integer arithmetic in order to reliably determine solvability, to detect and eliminate redundancies in the set of constraints, and to ensure that the solution exactly satisfies the constraints. We also use constrained least squares to choose a suitable solution when the constraints allow multiple solutions. Unlike the usual finite element approach, the method allows editing of any set of anchors with any sufficiently large set of derived parameters. As an example of application, we show how the method can be used to edit smooth ( ${\mathsf{C}}^1$) deformations of geometric mesh models.     

Linear restrictions and two step least squares with applications

In this paper we consider the full rank regression model with arbitrary covariance matrix: Y = Xß + ε. It is shown that the effect of restricting the information Y to T = A′Y may be analyzed through an associatedi regression problem which is amenable to solution by two step least squares. The results are applied to the important case of missing observations, where some classical results are rederived.     

On condition numbers for Moore–Penrose inverse and linear least squares problem involving Kronecker products

In this paper, we investigate the normwise, mixed, and componentwise condition numbers and their upper bounds for the Moore–Penrose inverse of the Kronecker product and more general matrix function compositions involving Kronecker products. We also present the condition numbers and their upper bounds for the associated Kronecker product linear least squares solution with full column rank. In practice, the derived upper bounds for the mixed and componentwise condition numbers for Kronecker product linear least squares solution can be efficiently estimated using the Hager–Higham Algorithm. Copyright © 2012 John Wiley & Sons, Ltd.     

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.