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     

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.     

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.     

A SUCCESSIVE LEAST SQUARES METHOD FOR STRUCTURED TOTAL LEAST SQUARES

A new method for Total Least Squares (TLS) problems is presented. It differs from previous approaches and is based on the solution of successive Least Squares problems.The method is quite suitable for Structured TLS (STLS) problems. We study mostly the case of Toeplitz matrices in this paper. The numerical tests illustrate that the method converges to the solution fast for Toeplitz STLS problems. Since the method is designed for general TLS problems, other structured problems can be treated similarly.     

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.

     

An efficient meshfree point collocation moving least squares method to solve the interface problems with nonhomogeneous jump conditions

We are going to study a simple and effective method for the numerical solution of the closed interface boundary value problem with both discontinuities in the solution and its derivatives. It uses a strong‐form meshfree method based on the moving least squares (MLS) approximation. In this method, for the solution of elliptic equation, the second‐order derivatives of the shape functions are needed in constructing the global stiffness matrix. It is well‐known that the calculation of full derivatives of the MLS approximation, especially in high dimensions, is quite costly. In the current work, we apply the diffuse derivatives using an efficient technique. In this technique, we calculate the higher‐order derivatives using the approximation of lower‐order derivatives, instead of calculating directly derivatives. This technique can improve the accuracy of meshfree point collocation method for interface problems with nonhomogeneous jump conditions and can efficiently estimate diffuse derivatives of second‐ and higher‐orders using only linear basis functions. To introduce the appropriate discontinuous shape functions in the vicinity of interface, we choose the visibility criterion method that modifies the support of weight function in MLS approximation and leads to an efficient computational procedure for the solution of closed interface problems. The proposed method is applied for elliptic and biharmonic interface problems. For the biharmonic equation, we use a mixed scheme, which replaces this equation by a coupled elliptic system. Also the application of the present method to elasticity equation with discontinuities in the coefficients across a closed interface has been provided. Representative numerical examples demonstrate the accuracy and robustness of the proposed methodology for the closed interface problems. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 1031–1053, 2015     

A numerically stable least squares solution to the quadratic programming problem

The strictly convex quadratic programming problem is transformed to the least distance problem — finding the solution of minimum norm to the system of linear inequalities. This problem is equivalent to the linear least squares problem on the positive orthant. It is solved using orthogonal transformations, which are memorized as products. Like in the revised simplex method, an auxiliary matrix is used for computations. Compared to the modified-simplex type methods, the presented dual algorithm QPLS requires less storage and solves ill-conditioned problems more precisely. The algorithm is illustrated by some difficult problems.      

Solution of large‐scale weighted least‐squares problems

A sequence of least‐squares problems of the form min_y∥G^1/2(A^T y?h)∥₂, where G is an n×n positive‐definite diagonal weight matrix, and A an m×n (m?n) sparse matrix with some dense columns; has many applications in linear programming, electrical networks, elliptic boundary value problems, and structural analysis. We suggest low‐rank correction preconditioners for such problems, and a mixed solver (a combination of a direct solver and an iterative solver). The numerical results show that our technique for selecting the low‐rank correction matrix is very effective. Copyright © 2002 John Wiley & Sons, Ltd.     

三维弹性问题无网格分析的奇异杂交边界点方法

提出了一种求解三维线弹性问题的奇异杂交边界点方法．将修正变分原理与移动最小二乘法结合起来,利用了前者的降维优势和后者的无网格特性．使用刚体位移法处理方法中的强奇异积分,提出了一种自适应的积分方案,解决了原有的杂交边界点方法中存在的“边界层效应”．在该方法中,将基本解的源点直接布在边界上,避免了在正则化杂交边界点法中不确定参数的选取．三维弹性力学问题算例体现了这些特点．结果表明该方法与已知的精确解符合较好,同时研究了影响该方法精度的一些参数．     

The Impact of Equal Weighting of Low- and High-Confidence Observations on Robust Linear Regression Computations

Equal weighting of low- and high-confidence observations occurs for Huber, Talwar, and Barya weighting functions when Newton's method is used to solve robust linear regression problems. This leads to easy updates and/or downdates of existing matrix factorizations or easy computation of coefficient matrices in linear systems from previous ones. Thus Newton's method based on these functions has been shown to be computationally cheap. In this paper we show that a combination of Newton's method and an iterative method is a promising approach for solving robust linear regression problems. We show that Newton's method based on the Talwar function is an active set method. Further we show that it is possible to obtain improved estimates of the solution vector by combining a line search method like Newton's method with an active set method.This revised version was published online in October 2005 with corrections to the Cover Date.     

A polynomial algorithm for minimum quadratic cost flow problems

Network flow problems with quadratic separable costs appear in a number of important applications such as; approximating input-output matrices in economy; projecting and forecasting traffic matrices in telecommunication networks; solving nondifferentiable cost flow problems by subgradient algorithms. It is shown that the scaling technique introduced by Edmonds and Karp (1972) in the case of linear cost flows for deriving a polynomial complexity bound for the out-of-kilter method, may be extended to quadratic cost flows and leads to a polynomial algorithm for this class of problems. The method may be applied to the solution of singly constrained quadratic programs and thus provides an alternative approach to the polynomial algorithm suggested by Helgason, Kennington and Lall (1980).     

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.     

线性流形上次反对称矩阵逆特征值问题的最小二乘解

讨论了线性流形上次反对称矩阵逆特征值问题的最小二乘问题及其最佳逼近，给出了这些问题解的通式；并就这些问题的特殊情况进行了讨论，得到了一些结果。     

求解加权线性最小二乘问题的预处理迭代方法

给出了求解一类加权线性最小二乘问题的预处理迭代方法,也就是预处理的广义加速超松弛方法（GAOR）,得到了一些收敛和比较结果．比较结果表明当原来的迭代方法收敛时,预处理迭代方法会比原来的方法具有更好的收敛率．而且,通过数值算例也验证了新预处理迭代方法的有效性．     

一个新的求解线性规划最小二乘算法

§1Introduction Currently,therearetwopopularapproachesinlinearprogramming:pivotalgorithm andinterior-pointalgorithm.Manyoftheirvariantsdevelopedbothintheoryand applicationsarestillinprogress.Thepivotmethodobtainstheoptimalsolutionviamoving consecutivelytoabettercorner-pointinthefeasibleregion,anditsmodificationstryto improvethespeedofattainingtheoptimality.Incontrast,theinterior-pointalgorithmis claimedasaninterior-pointapproach,whichgoesfromafeasiblepointtoafeasiblepoint throughtheinterioroft…     

剔除相关性的最小二乘研究

本文提出了一种新的回归模型,剔除相关性的最小二乘,它有效的克服了变量间的相关性,兼顾到变量的筛选。并与最小二乘、向后删除变量法、偏最小二乘比较分析。发现剔除相关性的最小二乘能很好的处理自变量间多重相关性,对变量进行有效的筛选,克服了回归系数反常的现象。     

Bivariate least squares approximation with linear constraints

In this article linear least squares problems with linear equality constraints are considered, where the data points lie on the vertices of a rectangular grid. A fast and efficient computational method for the case when the linear equality constraints can be formulated in a tensor product form is presented. Using the solution of several univariate approximation problems the solution of the bivariate approximation problem can be derived easily. AMS subject classification (2000)  65D05, 65D07, 65D10, 65F05, 65F20     

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     

A NONMONOTONE TRUST REGION METHOD FOR NONLINEAR LEAST SQUARES PROBLEMS

In this paper we present a nonmonotone trust region method for nonlinear least squares problems with zero-residual and prove its convergence properties. The extensive numerical results are reported which show that the nonmonotone trust region method is generally superior to the usual trust region method.     

A continuation method for solving separable nonlinear least squares problems

Given the data (x_i, y_i), i=1, 2, …, n, the problem is to find the values of the linear and nonlinear parameters â and b? which minimize the nonlinear functional |F(b)a?y|₂² over $\text{a ?}\text{R}{}^{\mathrm{p}}\text{, b ?}\text{R}{}^{\mathrm{q}}\text{,}\text{where}\text{F ?}\text{R}{}^{\mathrm{n\times p}}$ is a variable matrix and assumed to be of full rank, and $\text{y ?}\text{R}{}^{\mathrm{n}}$ is a constant vector.In this paper, we present a method for solving this problem by imbedding it into a one-parameter family of problems and by following its solution path using a predictor-corrector algorithm. In the course of iterations, the original problem containing p+q+1 variables is transformed into a problem with q+1 nonlinear variables by taking the separable structure of the problem into account. By doing so, the method reduces to solving a series of equations of smaller size and a considerable saving in the storage is obtained.Results of numerical experiments are reported to demonstrate the effectiveness of the proposed method.