On the Gauss-Newton method for l1 orthogonal distance regression

The problem of fitting a curve or surface to data has many applications.There are also many fitting criteria which can be used, andone which is widely used in metrology, for example, is thatof minimizing the least squares norm of the orthogonal distancesfrom the data points to the curve or surface. The Gauss–Newtonmethod, in correct separated form, is a popular method for solvingthis problem. There is also interest in alternatives to leastsquares, and here we focus on the use of the l₁ norm, whichis traditionally regarded as important when the data containwild points. The effectiveness of the Gauss–Newton methodin this case is studied, with particular attention given tothe influence of zero distances. Different aspects of the computationare illustrated by consideration of two particular fitting problems.     

Incomplete total least squares

Fitting data points with some model function such that the sum of squared orthogonal distances is minimized is well-known as TLS, i.e. as total least squares, see Van Huffel (1997). We consider situations where the model is such that there might be no perpendiculars from certain data points onto the model function and where one has to replace certain orthogonal distances by shortest ones, e.g. to corner or border line points. We introduce this considering the (now incomplete) TLS fit by a finite piece of a straight line. Then we study general model functions with linear parameters and modify a well-known descent algorithm (see Seufer (1996), Seufer/Sp?th (1997), Sp?th (1996), Sp?th (1997a) and Sp?th (1997b)) for fitting with them. As applications (to be used in computational metrology) we discuss incomplete TLS fitting with a segment of a circle, the area of a circle in space, with a cylinder, and with a rectangle (see also Gander/Hrebicek (1993)). Numerical examples are given for each case. Received August 27, 1997 / Revised version received February 23, 1998     

Implicit Surface Fitting Using Directional Constraints

A commonly used technique for fitting curves and surfaces to measured data is that known as orthogonal distance regression, where the sum of squares of orthogonal distances from the data points to the surface is minimized. An alternative has recently been proposed for curves and surfaces which are parametrically defined, which minimizes the sum of squares in given directions which depend on the measuring process. In addition to taking account of that process, it is claimed that this technique has the advantage of complying with traditional fixed-regressor assumptions, enabling standard inference theory to apply. Here we consider extending this idea to curves and surfaces where the only assumption made is that there is an implicit formulation. Numerical results are given to illustrate the algorithmic performance.This revised version was published online in October 2005 with corrections to the Cover Date.     

On the solution of the errors in variables problem using thel 1 norm

A fundamental problem in data analysis is that of fitting a given model to observed data. It is commonly assumed that only the dependent variable values are in error, and the least squares criterion is often used to fit the model. When significant errors occur in all the variables, then an alternative approach which is frequently suggested for this errors in variables problem is to minimize the sum of squared orthogonal distances between each data point and the curve described by the model equation. It has long been recognized that the use of least squares is not always satisfactory, and thel ₁ criterion is often superior when estimating the true form of data which contain some very inaccurate observations. In this paper the measure of goodness of fit is taken to be thel ₁ norm of the errors. A Levenberg-Marquardt method is proposed, and the main objective is to take full advantage of the structure of the subproblems so that they can be solved efficiently.     

Influence Diagnostics in Partially Varying-Coefficient Models

When a real-world data set is fitted to a specific type of models,it is often encountered that oneor a set of observations have undue influence on the model fitting,which may lead to misleading conclusions.Therefore,it is necessary for data analysts to identify these influential observations and assess their impacton various aspects of model fitting.In this paper,one type of modified Cook's distances is defined to gaugethe influence of one or a set observations on the estimate of the constant coefficient part in partially varying-coefficient models,and the Cook's distances are expressed as functions of the corresponding residuals andleverages.Meanwhile,a bootstrap procedure is suggested to derive the reference values for the proposed Cook'sdistances.Some simulations are conducted,and a real-world data set is further analyzed to examine theperformance of the proposed method.The experimental results are satisfactory.     

Efficient computation of the Gauss-Newton direction when fitting NURBS using ODR

We consider a subproblem in parameter estimation using the Gauss-Newton algorithm with regularization for NURBS curve fitting. The NURBS curve is fitted to a set of data points in least-squares sense, where the sum of squared orthogonal distances is minimized. Control-points and weights are estimated. The knot-vector and the degree of the NURBS curve are kept constant. In the Gauss-Newton algorithm, a search direction is obtained from a linear overdetermined system with a Jacobian and a residual vector. Because of the properties of our problem, the Jacobian has a particular sparse structure which is suitable for performing a splitting of variables. We are handling the computational problems and report the obtained accuracy using different methods, and the elapsed real computational time. The splitting of variables is a two times faster method than using plain normal equations.     

Fitting Parametric Curves and Surfaces by <Emphasis Type="Italic">l</Emphasis><Subscript>∞</Subscript> Distance Regression

For fitting curves or surfaces to observed or measured data, a common criterion is orthogonal distance regression. We consider here a natural generalization of a particular formulation of that problem which involves the replacement of least squares by the Chebyshev norm. For example, this criterion may be a more appropriate one in the context of accept/reject decisions for manufactured parts. The resulting problem has some interesting features: it has much structure which can be exploited, but generally the solution is not unique. We consider a method of Gauss-Newton type and show that if the non-uniqueness is resolved in a way which is consistent with a particular way of exploiting the structure in the linear subproblem, this can not only allow the method to be properly defined, but can permit a second order rate of convergence. Numerical examples are given to illustrate this. AMS subject classification (2000) 65D10, 65K05     

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     

Fitting concentric circles to measurements

Measurements for fitting a given number of concentric circles are recorded. For each concentric circle several measurements are taken. The problem is to fit the given number of circles to the data such that all circles have a common center. This is a generalization of the problem of fitting a set of points to one circle. Three objectives, to be minimized, are considered: the least squares of distances from the circles, the maximum distance from the circles, and the sum of the distances from the circles. Very efficient optimal solution procedures are constructed. Problems based on a total of 10,000 measurements are solved in about 10 s with the least squares objective, $<$ 2 s with the maximum distance objective, and a little more than 1 min for the minisum objective.     

Consistent least squares fitting of ellipsoids

Summary. A parameter estimation problem for ellipsoid fitting in the presence of measurement errors is considered. The ordinary least squares estimator is inconsistent, and due to the nonlinearity of the model, the orthogonal regression estimator is inconsistent as well, i.e., these estimators do not converge to the true value of the parameters, as the sample size tends to infinity. A consistent estimator is proposed, based on a proper correction of the ordinary least squares estimator. The correction is explicitly given in terms of the true value of the noise variance.Mathematics Subject Classification (2000): 65D15, 65D10, 15A63Revised version received August 15, 2003     

An adaptive wavelet viscosity method for hyperbolic conservation laws

We extend the multiscale finite element viscosity method for hyperbolic conservation laws developed in terms of hierarchical finite element bases to a (pre‐orthogonal spline‐)wavelet basis. Depending on an appropriate error criterion, the multiscale framework allows for a controlled adaptive resolution of discontinuities of the solution. The nonlinearity in the weak form is treated by solving a least‐squares data fitting problem. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2008     

Book Reviews

This paper modifies the usual meaning of regression from ‘minimizing the sum of squared distances’ to ‘minimizing the sum of square perpendicular distances’. With this modified definition, the best‐fit plane, circle, and sphere may be meaningfully considered.

These regression problems are motivated by the current development of software to control robotized coordinate measuring machines (CMMs) used to perform quality assurance work. A brief outline of CMMs is given and the application of the modified regression definition to a plane, circle and sphere is illustrated. In §3 the equation of the best fitting plane is calculated for various sets of data points.     

On orthogonal linear ℓ1 approximation

Summary The problem is considered of orthogonal ₁ fitting of discrete data. Local best approximations are characterized and the question of the robustness of these solutions is considered. An algorithm for the problem is presented, along with numerical results of its application to some data sets.     

干线网络的选址问题研究

考虑平面上和三维空间中同时确定多条干线的干线网络选址问题.对于平面上情形,通过最小化每个点到离它最近干线的加权距离之和,给出了一种有限步终止算法和基于k-means聚类分析、加权全最小一乘和重抽样方法的线性类算法;对于空间情形,给出了线性聚类算法.通过计算机仿真说明以上算法可以有效地确定平面和空间中干线网络位置.     

Clustering reduced interval data using Hausdorff distance

Summary  In the last decade, factorial and clustering techniques have been developed to analyze multidimensional interval data (MIDs). In classic data analysis, PCA and clustering of the most significant components are usually performed to extract cluster structure from data. The clustering of the projected data is then performed, once the noise is filtered out, in a subspace generated by few orthogonal variables. In the framework of interval data analysis, we propose the same strategy. Several computational questions arise from this generalization. First of all, the representation of data onto a factorial subspace: in classic data analysis projected points remain points, but projected MIDs do not remains MIDs. Further, the choice of a distance between the represented data: many distances between points can be computed, few distances between convex sets of points are defined. We here propose optimized techniques for representing data by convex shapes, for computing the Hausdorff distance between convex shapes, based on an L ₂ norm, and for performing a hierarchical clustering of projected data.     

A Non-Iterative Alternative to Ordinal Log-Linear Models

Log-linear modeling is a popular statistical tool for analysing a contingency table. This presentation focuses on an alternative approach to modeling ordinal categorical data. The technique, based on orthogonal polynomials, provides a much simpler method of model fitting than the conventional approach of maximum likelihood estimation, as it does not require iterative calculations nor the fitting and refitting to search for the best model. Another advantage is that quadratic and higher order effects can readily be included, in contrast to conventional log-linear models which incorporate linear terms only.

The focus of the discussion is the application of the new parameter estimation technique to multi-way contingency tables with at least one ordered variable. This will also be done by considering singly and doubly ordered two-way contingency tables. It will be shown by example that the resulting parameter estimates are numerically similar to corresponding maximum likelihood estimates for ordinal log-linear models.     

Self-Orthogonal and Self-Dual Codes Constructed via Combinatorial Designs and Diophantine Equations

Combinatorial designs have been widely used, in the construction of self-dual codes. Recently, new methods of constructing self-dual codes are established using orthogonal designs (ODs), generalized orthogonal designs (GODs), a set of four sequences and Diophantine equations over GF(p). These methods had led to the construction of many new self-dual codes over small finite fields and rings. In this paper, we used some methods to construct self-orthogonal and self dual codes over GF(p), for some primes p. The construction is achieved by using some special kinds of combinatorial designs like orthogonal designs and GODs. Moreover, we combine eight circulant matrices, a system of Diophantine equations over GF(p), and a recently discovered array to obtain a new construction method. Using this method new self-dual and self-orthogonal codes are obtained. Specifically, we obtain new self-dual codes [32,16,12] over GF(11) and GF(13) which improve the previously known distances.     

Exponentials Reproducing Subdivision Schemes

This paper is concerned with a family of nonstationary, interpolatory subdivision schemes that have the capability of reproducing functions in a finite-dimensional subspace of exponential polynomials. We give conditions for the existence and uniqueness of such schemes, and analyze their convergence and smoothness. It is shown that the refinement rules of an even-order exponentials reproducing scheme converge to the Dubuc—Deslauriers interpolatory scheme of the same order, and that both schemes have the same smoothness. Unlike the stationary case, the application of a nonstationary scheme requires the computation of a different rule for each refinement level. We show that the rules of an exponentials reproducing scheme can be efficiently derived by means of an auxiliary orthogonal scheme , using only linear operations. The orthogonal schemes are also very useful tools in fitting an appropriate space of exponential polynomials to a given data sequence.     

Orthogonal least squares fitting with linear manifolds

Summary The problem is considered of fitting a linear manifold of dimensions with 1sn–1 to a given set of points in ⁿ such that the sum of orthogonal squared distances attains a minimum.     

Guided Projections for Analyzing the Structure of High-Dimensional Data

A powerful data transformation method named guided projections is proposed creating new possibilities to reveal the group structure of high-dimensional data in the presence of noise variables. Using projections onto a space spanned by a selection of a small number of observations allows measuring the similarity of other observations to the selection based on orthogonal and score distances. Observations are iteratively exchanged from the selection creating a nonrandom sequence of projections, which we call guided projections. In contrast to conventional projection pursuit methods, which typically identify a low-dimensional projection revealing some interesting features contained in the data, guided projections generate a series of projections that serve as a basis not just for diagnostic plots but to directly investigate the group structure in data. Based on simulated data, we identify the strengths and limitations of guided projections in comparison to commonly employed data transformation methods. We further show the relevance of the transformation by applying it to real-world datasets.