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.     

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.     

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.     

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.     

Derivative-free optimization and neural networks for robust regression

Large outliers break down linear and nonlinear regression models. Robust regression methods allow one to filter out the outliers when building a model. By replacing the traditional least squares criterion with the least trimmed squares (LTS) criterion, in which half of data is treated as potential outliers, one can fit accurate regression models to strongly contaminated data. High-breakdown methods have become very well established in linear regression, but have started being applied for non-linear regression only recently. In this work, we examine the problem of fitting artificial neural networks (ANNs) to contaminated data using LTS criterion. We introduce a penalized LTS criterion which prevents unnecessary removal of valid data. Training of ANNs leads to a challenging non-smooth global optimization problem. We compare the efficiency of several derivative-free optimization methods in solving it, and show that our approach identifies the outliers correctly when ANNs are used for nonlinear regression.     

Solving Quadratically Constrained Least Squares Problems Using a Differential-Geometric Approach

A quadratically constrained linear least squares problem is usually solved using a Lagrange multiplier for the constraint and then solving iteratively a nonlinear secular equation for the optimal Lagrange multiplier. It is well-known that, due to the closeness to a pole for the secular equation, standard methods for solving the secular equation can be slow, and sometimes it is not easy to select a good starting value for the iteration. The problem can be reformulated as that of minimizing the residual of the least squares problem on the unit sphere. Using a differential-geometric approach we formulate Newton's method on the sphere, and thereby avoid the difficulties associated with the Lagrange multiplier formulation. This Newton method on the sphere can be implemented efficiently, and since it is easy to find a good starting value for the iteration, and the convergence is often quite fast, it has a clear advantage over the Lagrange multiplier method. A numerical example is given.     

基于最小截平方和估计的监测数据分析方法

水工程安全监测数据中不可避免地存在离群点,而应用最为广泛的最小二乘法(least square,LS)不具备剔除离群点的能力,反而更易吸收离群点,使回归曲线严重偏离实际。针对LS在此方面的缺陷,本文在最小化残差平方和理论的基础上,提出采用最小截平方和估计(least trimmed squares,LTS)方法来构建水工程安全监控模型。根据实际工程的监测资料并对监测资料分析处理,剔除离群点得到最优数据群。通过求解最优数据群的回归系数,进而得到最接近实际数据的拟合曲线。相比于LS估计,LTS估计所得结果更具有合理性、稳健性,且能够显著提高数据的预测精度。因此,LTS估计在水工程安全监测等数据分析中具有良好的应用前景。     

Robust Frequency Estimation Using Elemental Sets

Abstract

The extraction of sinusoidal signals from time-series data is a classic problem of ongoing interest in the statistics and signal processing literatures. Obtaining least squares estimates is difficult because the sum of squares has local minima O(1/n) apart in the frequencies. In practice the frequencies are often estimated using ad hoc and inefficient methods. Problems of data quality have received little attention. An elemental set is a subset of the data containing the minimum number of points such that the unknown parameters in the model can be identified. This article shows that, using a variant of the classical method of Prony, parameter estimates for a sum of sinusoids can be obtained algebraically from an elemental set. Elemental set methods are used to construct finite algorithm estimators that approximately minimize the least squares, least trimmed sum of squares, or least median of squares criteria. The elemental set estimators prove able in simulations to resolve the frequencies to the correct local minima of the objective functions. When used as the first stage of an MM estimator, the constructed estimators based on the trimmed sum of squares and least median of squares criteria produce final estimators which have high breakdown properties and which are simultaneously efficient when no outliers are present. The approach can also be applied to sums of exponentials, and sums of damped sinusoids. The article includes simulations with one and two sinusoids and two data examples.     

Asymptotic theory of least squares estimator in a nonregular nonlinear regression model

The asymptotic properties of the least squares estimator are derived for a nonregular nonlinear model via the study of weak convergence of the least squares process. This approach was adapted earlier by the author in the smooth case. The model discussed here is not amenable to analysis via the normal equations and Taylor expansions used by earlier authors.     

A SELF-ADAPTIVE ALGORITHM FOR NONLINEAR LEAST SQUARES WITH LINEAR CONSTRAINTS

An algorithm for solving nonlinear least squares problems with general linear inequality constraints is described.At each step,the problem is reduced to an unconstrained linear least squares problem in a subs pace defined by the active constraints,which is solved using the quasi-Newton method.The major update formula is similar to the one given by Dennis,Gay and Welsch (1981).In this paper,we state the detailed implement of the algorithm,such as the choice of active set,the solution of subproblem and the avoidance of zigzagging.We also prove the globally convergent property of the algorithm.     

Minimax estimation and the least squares method

This paper is devoted to the problem of minimax estimation of parameters in linear regression models with uncertain second order statistics. The solution to the problem is shown to be the least squares estimator corresponding to the least favourable matrix of the second moments. This allows us to construct a new algorithm for minimax estimation closely connected with the least squares method. As an example, we consider the problem of polynomial regression introduced by A. N. Kolmogorov     

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

Some observations on local least squares

In previous work we introduced a construction to produce biorthogonal multiresolutions from given subdivisions. The approach involved estimating the solution to a least squares problem by means of a number of smaller least squares approximations on local portions of the data. In this work we use a result by Dahlquist, et al. on the method of averages to make observational comparisons between this local least squares estimation and full least squares approximation. We have explored examples in two problem domains: data reduction and data approximation. We observe that, particularly for design matrices with a repetitive pattern of column entries, the least squares solution is often well estimated by local least squares, that the estimation rapidly improves with the size of the local least squares problems, and that the quality of the estimate is largely independent of the size of the full problem. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 93E24     

拟合模糊观测数据的线性回归模型

本文讨论了实验观测数据为一般模糊数的线性最优拟合问题，通过定义模糊数空间中的距离，建立了模糊数空间到模糊数空间的回归模型，证明了最小二乘问题的解与其正则方程组的解的一致性，进而由正则方程组导出了问题的显式解。本模型的计算简便，具有实用价值。     

Bias of LS estimators in nonlinear regression models with constraints. Part I: General Case

We derive expressions for the asymptotic approximation of the bias of the least squares estimators in nonlinear regression models with parameters which are subject to nonlinear equality constraints.The approach suggested modifies the normal equations of the estimator, and approximates them up to o _p(N ^–1), where N is the number of observations. The bias equations so obtained are solved under different assumptions on constraints and on the model. For functions of the parameters the invariance of the approximate bias with respect to reparametrisations is demonstrated. Singular models are considered as well, in which case the constraints may serve either to identify the parameters, or eventually to restrict the parameter space.     

Least‐squares problems for Michaelis–Menten kinetics

The Michaelis–Menten kinetics is fundamental in chemical and physiological reaction theory. The problem of parameter identification, which is not well posed for arbitrary data, is shown to be closely related to the Chebyshev sum inequality. This inequality yields sufficient conditions for existence of feasible solutions both for nonlinear and for linear least‐squares problems. The conditions are natural and practical as they are satisfied if the data show the expected monotone and concave behaviour. Copyright © 2007 John Wiley & Sons, Ltd.     

A dynamic meshless method for the least squares problem with some noisy subdomains

The interpolation method by radial basis functions is used widely for solving scattered data approximation. However, sometimes it makes more sense to approximate the solution by least squares fit. This is especially true when the data are contaminated with noise. A meshfree method namely, meshless dynamic weighted least squares (MDWLS) method, is presented in this paper to solve least squares problems with noise. The MDWLS method by Gaussian radial basis function is proposed to fit scattered data with some noisy areas in the problem’s domain. Existence and uniqueness of a solution is proved. This method has one parameter which can adjusts the accuracy according to the size of noises. Another advantage of the developed method is that it can be applied to problems with nonregular geometrical domains. The new approach is applied for some problems in two dimensions and the obtained results confirm the accuracy and efficiency of the proposed method. The numerical experiments illustrate that our MDWLS method has better performance than the traditional least squares method in case of noisy data.     

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.     

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.