Shape preserving approximation using least squares splines

Least squares polynomial splines are an effective tool for data fitting, but they may fail to preserve essential properties of the underlying function, such as monotonicity or convexity. The shape restrictions are translated into linear inequality conditions on spline coefficients. The basis functions are selected in such a way that these conditions take a simple form, and the problem becomes non-negative least squares problem, for which effecitive and robust methods of solution exist. Multidimensional monotone approximation is achieved by using tensor-product splines with the appropriate restrictions. Additional inter polation conditions can also be introduced. The conversion formulas to traditional B-spline representation are provided.     

Faster least squares approximation

Least squares approximation is a technique to find an approximate solution to a system of linear equations that has no exact solution. In a typical setting, one lets n be the number of constraints and d be the number of variables, with n >> d{n \gg d}. Then, existing exact methods find a solution vector in O(nd ²) time. We present two randomized algorithms that provide accurate relative-error approximations to the optimal value and the solution vector of a least squares approximation problem more rapidly than existing exact algorithms. Both of our algorithms preprocess the data with the Randomized Hadamard transform. One then uniformly randomly samples constraints and solves the smaller problem on those constraints, and the other performs a sparse random projection and solves the smaller problem on those projected coordinates. In both cases, solving the smaller problem provides relative-error approximations, and, if n is sufficiently larger than d, the approximate solution can be computed in O(nd ln d) time.     

Shape preserving histogram approximation

We present a new method for reconstructing the density function underlying a given histogram. First we analyze the univariate case taking the approximating function in a class of quadratic-like splines with variable degrees. For the analogous bivariate problem we introduce a new scheme based on the Boolean sum of univariate B-splines and show that for a proper choice of the degrees, the splines are positive and satisfy local monotonicity constraints.     

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

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

On discrete rational least squares approximation

Summary The paper deals with the finite rational least squares approximation to a discrete function. An approximation without poles and depending on a parameter is defined which tends to the least squares approximation for 0. It gives an acceptable approximation when the least squares approximation does not exist. Further it is shown that, if the discrete function to be fitted is sufficiently close to a rational function, then the least squares approximation exists.     

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.     

Convergence of discrete and penalized least squares spherical splines

We study the convergence of discrete and penalized least squares spherical splines in spaces with stable local bases. We derive a bound for error in the approximation of a sufficiently smooth function by the discrete and penalized least squares splines. The error bound for the discrete least squares splines is explicitly dependent on the mesh size of the underlying triangulation. The error bound for the penalized least squares splines additionally depends on the penalty parameter.     

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     

An error estimate for least squares approximation

Upper and lower error bounds are obtained for the error of the bestL ₂ polynomial approximation of degreen for a function belonging toC ⁿ⁺¹ [?1, 1].     

Shape preserving approximation in vector ordered spaces

The aim of this note is to extend some classical results on the shape preserving approximation of real functions (of real variables) to functions with values in ordered vector spaces.     

Error bounds for least squares approximation by polynomials

Let f ε Cⁿ⁺¹[−1, 1] and let H[f](x) be the nth degree weighted least squares polynomial approximation to f with respect to the orthonormal polynomials q_k associated with a distribution dα on [−1, 1]. It is shown that if q_n+1/q_n max(q_n+1(1)/q_n(1), −q_n+1(−1)/q_n(−1)), then f − H[f] f^{n + 1} · q_n+1/q_{n + 1}^{(n + 1)}, where · denotes the supremum norm. Furthermore, it is shown that in the case of Jacobi polynomials with distribution (1 − t)^α (1 + t)^β dt, α, β > −1, the condition on q_n+1/q_n is satisfied when either max(α,β) −1/2 or −1 < α = β < −1/2.     

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.     

Bounds for the least squares distance using scaled total least squares

Summary. The standard approaches to solving overdetermined linear systems construct minimal corrections to the data to make the corrected system compatible. In ordinary least squares (LS) the correction is restricted to the right hand side c, while in scaled total least squares (STLS) [14,12] corrections to both c and B are allowed, and their relative sizes are determined by a real positive parameter . As , the STLS solution approaches the LS solution. Our paper [12] analyzed fundamentals of the STLS problem. This paper presents a theoretical analysis of the relationship between the sizes of the LS and STLS corrections (called the LS and STLS distances) in terms of . We give new upper and lower bounds on the LS distance in terms of the STLS distance, compare these to existing bounds, and examine the tightness of the new bounds. This work can be applied to the analysis of iterative methods which minimize the residual norm, and the generalized minimum residual method (GMRES) [15] is used here to illustrate our theory. Received July 20, 2000 / Revised version received February 28, 2001 / Published online July 25, 2001     

A shape preserving area true approximation of histogram by rational splines

For a given histogram, we consider an application of a simple rational spline to a shape preserving area true approximation of the histogram. An algorithm for determination of the spline is as easy as one with a quadratic polynomial spline, while the latter does not always preserve the shape of the histogram. Some numerical examples are given at the end of the paper.     

A parallel algorithm for discrete least squares rational approximation

Summary A new method for discrete least squares linearized rational approximation is presented. It generalizes the algorithm of Rutishauser-Gragg-Harrod-Reichel for discrete least squares polynomial approximation to the rational case. The algorithm is fast in the sense that it requires orderm computation time wherem is the number of data points and is the degree of the approximant. We describe how this algorithm can be implemented in parallel.     

Uniform approximation on the sphere by least squares polynomials

Numerical Algorithms - The paper concerns the uniform polynomial approximation of a function f, continuous on the unit Euclidean sphere of ?3 and known only at a finite number of points that...     

Shape constrained smoothing using smoothing splines

Summary  In some regression settings one would like to combine the flexibility of nonparametric smoothing with some prior knowledge about the regression curve. Such prior knowledge may come from a physical or economic theory, leading to shape constraints such as the underlying regression curve being positive, monotone, convex or concave. We propose a new method for calculating smoothing splines that fulfill these kinds of constraints. Our approach leads to a quadratic programming problem and the infinite number of constraints are replaced by a finite number of constraints that are chosen adaptively. We show that the resulting problem can be solved using the algorithm of Goldfarb and Idnani (1982, 1983) and illustrate our method on several real data sets.     

A note on an error estimate for least squares approximation

An asymptotic expansion is obtained which provides upper and lower bounds for the error of the bestL ₂ polynomial approximation of degreen forx ⁿ⁺¹ on [–1, 1]. Because the expansion proceeds in only even powers of the reciprocal of the large variable, and the error made by truncating the expansion is numerically less than, and has the same sign as the first neglected term, very good bounds can be obtained. Via a result of Phillips, these results can be extended fromx ⁿ⁺¹ to anyfC ⁿ⁺¹[–1, 1], provided upper and lower bounds for the modulus off ⁽ⁿ⁺¹⁾ are available.