Local polynomial reproduction and moving least squares approximation

Local polynomial reproduction is a key ingredient in providingerror estimates for several approximation methods. To boundthe Lebesgue constants is a hard task especially in a multivariatesetting. We provide a result which allows us to bound the Lebesgueconstants uniformly and independently of the space dimensionby oversampling. We get explicit and small bounds for the Lebesgueconstants. Moreover, we use these results to establish errorestimates for the moving least squares approximation scheme,also with special emphasis on the involved constants. We discussthe numerical treatment of the method and analyse its effort.Finally, we give large scale examples.     

Fastiterative methods for least squares estimations

Least squares estimations have been used extensively in many applications, e.g. system identification and signal prediction. When the stochastic process is stationary, the least squares estimators can be found by solving a Toeplitz or near-Toeplitz matrix system depending on the knowledge of the data statistics. In this paper, we employ the preconditioned conjugate gradient method with circulant preconditioners to solve such systems. Our proposed circulant preconditioners are derived from the spectral property of the given stationary process. In the case where the spectral density functions() of the process is known, we prove that ifs() is a positive continuous function, then the spectrum of the preconditioned system will be clustered around 1 and the method converges superlinearly. However, if the statistics of the process is unknown, then we prove that with probability 1, the spectrum of the preconditioned system is still clustered around 1 provided that large data samples are taken. For finite impulse response (FIR) system identification problems, our numerical results show that annth order least squares estimator can usually be obtained inO(n logn) operations whenO(n) data samples are used. Finally, we remark that our algorithm can be modified to suit the applications of recursive least squares computations with the proper use of sliding window method arising in signal processing applications.Research supported in part by HKRGC grant no. 221600070, ONR contract no. N00014-90-J-1695 and DOE grant no. DE-FG03-87ER25037.     

Comparison of eigenvalue,logarithmic least squares and least squares methods in estimating ratios

Three methods—the eigenvalue, logarithmic least squares, and least squares methods—used to derive estimates of ratio scales from a positive reciprocal matrix are analyzed. The criteria for comparison are the measurement of consistency, dual solutions, and rank preservation. It is shown that the eigenvalue procedure, which is metric-free, leads to a structural index for measuring inconsistency, has two separate dual interpretations and is the only method that guarantees rank preservation under inconsistency conditions.     

Multivariate polynomial interpolation with perturbed data

Given a finite set of points \(\mathbb {X}\subset \mathbb {R}^{n}\), one may ask for polynomials p which belong to a subspace V and which attain given values at the points of \(\mathbb {X}\). We focus on subspaces V of \( \mathbb {R}[x_{1},\ldots ,x_{n}]\), generated by low order monomials. Such V were computed by the BM-algorithm, which is essentially based on an LU-decomposition. In this paper we present a new algorithm based on the numerical more stable QR-decomposition. If \(\mathbb {X}\) contains only points perturbed by measurement or rounding errors, the homogeneous interpolation problem is replaced by the problem of finding (normalized) polynomials minimizing \({\sum }_{u\in \mathbb {X}} p(u)^{2}\). We show that such polynomials can be found easily as byproduct in the QR-decomposition and present an error bound showing the quality of the approximation.     

An approach to the interpolation of nonuniformly spaced data

In this paper, we consider the spline in tension as an interpolatory tool that helps us avoid large projector norm. Tension parameters are computed in advance in such a way that the prescribed exponential decay of fundamental functions is assured. Further, an interpolation error bound for a smooth function is produced. This bound depends on the choice of tension parameters, and is of order 4 for small tension values but reduces to 2 as parameters grow to infinity.     

Numerical methods for solving linear least squares problems

A common problem in a Computer Laboratory is that of finding linear least squares solutions. These problems arise in a variety of areas and in a variety of contexts. Linear least squares problems are particularly difficult to solve because they frequently involve large quantities of data, and they are ill-conditioned by their very nature. In this paper, we shall consider stable numerical methods for handling these problems. Our basic tool is a matrix decomposition based on orthogonal Householder transformations.Reproduction in Whole or in Part is permitted for any Purpose of the United States government. This report was supported in part by Office of Naval Research Contract Nonr-225(37) (NR 044-11) at Stanford University.     

Rank-k modification methods for recursive least squares problems

In least squares problems, it is often desired to solve the same problem repeatedly but with several rows of the data either added, deleted, or both. Methods for quickly solving a problem after adding or deleting one row of data at a time are known. In this paper we introduce fundamental rank-k updating and downdating methods and show how extensions of rank-1 downdating methods based on LINPACK, Corrected Semi-Normal Equations (CSNE), and Gram-Schmidt factorizations, as well as new rank-k downdating methods, can all be derived from these fundamental results. We then analyze the cost of each new algorithm and make comparisons tok applications of the corresponding rank-1 algorithms. We provide experimental results comparing the numerical accuracy of the various algorithms, paying particular attention to the downdating methods, due to their potential numerical difficulties for ill-conditioned problems. We then discuss the computation involved for each downdating method, measured in terms of operation counts and BLAS calls. Finally, we provide serial execution timing results for these algorithms, noting preferable points for improvement and optimization. From our experiments we conclude that the Gram-Schmidt methods perform best in terms of numerical accuracy, but may be too costly for serial execution for large problems.Research supported in part by the Joint Services Electronics Program, contract no. F49620-90-C-0039.     

Hybrid methods for large sparse nonlinear least squares

Hybrid methods are developed for improving the Gauss-Newton method in the case of large residual or ill-conditioned nonlinear least-square problems. These methods are used usually in a form suitable for dense problems. But some standard approaches are unsuitable, and some new possibilities appear in the sparse case. We propose efficient hybrid methods for various representations of the sparse problems. After describing the basic ideas that help deriving new hybrid methods, we are concerned with designing hybrid methods for sparse Jacobian and sparse Hessian representations of the least-square problems. The efficiency of hybrid methods is demonstrated by extensive numerical experiments.This work was supported by the Czech Republic Grant Agency, Grant 201/93/0129. The author is indebted to Jan Vlek for his comments on the first draft of this paper and to anonymous referees for many useful remarks.     

Symmetric block-SOR methods for rank-deficient least squares problems

In this article, we develop symmetric block successive overrelaxation (S-block-SOR) methods for finding the solution of the rank-deficient least squares problems. We propose an S2-block-SOR and an S3-block-SOR method for solving such problems and the convergence of these two methods is studied. The comparisons between the S2-block and the S3-block methods are presented with some numerical examples.     

Factorized quasi-Newton methods for nonlinear least squares problems

This paper provides a modification to the Gauss—Newton method for nonlinear least squares problems. The new method is based on structured quasi-Newton methods which yield a good approximation to the second derivative matrix of the objective function. In particular, we propose BFGS-like and DFP-like updates in a factorized form which give descent search directions for the objective function. We prove local and q-superlinear convergence of our methods, and give results of computational experiments for the BFGS-like and DFP-like updates.This work was supported in part by the Grant-in-Aid for Encouragement of Young Scientists of the Japanese Ministry of Education: (A)61740133 and (A)62740137.     

Semidiscrete least squares methods for linear hyperbolic systems

Some approximate methods for solving linear hyperbolic systems are presented and analyzed. The methods consist of discretizing with respect to time and solving the resulting hyperbolic system for fixed time by least squares finite element methods. An analysis of least squares approximations is given, including optimal order estimates for piecewise polynomial approximation spaces. Numerical results for the inviscid Burgers' equation are also presented. © 1992 John Wiley & Sons, Inc.     

Penalized least squares estimation with weakly dependent data

In statistics and machine learning communities, the last fifteen years have witnessed a surge of high-dimensional models backed by penalized methods and other state-of-the-art variable selection techniques. The high-dimensional models we refer to differ from conventional models in that the number of all parameters p and number of significant parameters s are both allowed to grow with the sample size T. When the field-specific knowledge is preliminary and in view of recent and potential affluence of data from genetics, finance and on-line social networks, etc., such (s, T, p)-triply diverging models enjoy ultimate flexibility in terms of modeling, and they can be used as a data-guided first step of investigation. However, model selection consistency and other theoretical properties were addressed only for independent data, leaving time series largely uncovered. On a simple linear regression model endowed with a weakly dependent sequence, this paper applies a penalized least squares (PLS) approach. Under regularity conditions, we show sign consistency, derive finite sample bound with high probability for estimation error, and prove that PLS estimate is consistent in L ₂ norm with rate \(\sqrt {s\log s/T}\).     

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.     

Constrained least squares methods for linear timevarying DAE systems

Summary This paper presents a family of methods for accurate solution of higher index linear variable DAE systems, . These methods use the DAE system and some of its first derivatives as constraints to a least squares problem that corresponds to a Taylor series ofy, or an approximative equality derived from a Pade' approximation of the exponential function. Accuracy results for systems transformable to standard canonical form are given. Advantages, disadvantages, stability properties and implementation of these methods are discussed and two numerical examples are given, where we compare our results with results from more traditional methods.     

On the least squares fit by radial functions to multidimensional scattered data

Summary This paper investigates some aspects of discrete least squares approximation by translates of certain classes of radial functions. Its specific aims are (i) to provide conditions under which the associated least squares matrix is invertible and (ii) to give upper bounds for the Euclidean norms of the inverses of these matrices (when they exist).The second named author was supported by the National Science Foundation under grant number DMS-8901345     

AOR iterative methods for rank deficient least squares problems

In this paper we study the semiconvergence of accelerated overrelaxation (AOR) iterative methods for the least squares solution of minimal norm of rank deficient linear systems. Necessary and sufficient conditions for the semiconvergence of the AOR and JOR iterative methods are given. The optimum parameters and the associated convergence factor are derived.     

A weighted least squares method for scattered data fitting

In this paper, we present a weighted least squares method to fit scattered data with noise. Existence and uniqueness of a solution are proved and an error bound is derived. The numerical experiments illustrate that our weighted least squares method has better performance than the traditional least squares method in case of noisy data.