Evolutionary computation for optimal knots allocation in smoothing splines

In this paper, a novel methodology is presented for optimal placement and selections of knots, for approximating or fitting curves to data, using smoothing splines. It is well-known that the placement of the knots in smoothing spline approximation has an important and considerable effect on the behavior of the final approximation [1]. However, as pointed out in [2], although spline for approximation is well understood, the knot placement problem has not been dealt with adequately. In the specialized bibliography, several methodologies have been presented for selection and optimization of parameters within B-spline, using techniques based on selecting knots called dominant points, adaptive knots placement, by data selection process, optimal control over the knots, and recently, by using paradigms from computational intelligent, and Bayesian model for automatically determining knot placement in spline modeling. However, a common two-step knot selection strategy, frequently used in the bibliography, is an homogeneous distribution of the knots or equally spaced approach [3].     

An optimal adaptive algorithm for the approximation of concave functions

Motivated by the study of parametric convex programs, we consider approximation of concave functions by piecewise affine functions. Using dynamic programming, we derive a procedure for selecting the knots at which an oracle provides the function value and one supergradient. The procedure is adaptive in that the choice of a knot is dependent on the choice of the previous knots. It is also optimal in that the approximation error, in the integral sense, is minimized in the worst case. This work was partially supported by NSERC (Canada) and FCAR (Québec).     

Knot Placement for B-Spline Curve Approximation via $L_{∞, 1}$-Norm and Differential Evolution Algorithm

In this paper, we consider the knot placement problem in B-spline curve approximation. A novel two-stage framework is proposed for addressing this problem. In the first step, the $l_{\infty, 1}$-norm model is introduced for the sparse selection of candidate knots from an initial knot vector. By this step, the knot number is determined. In the second step, knot positions are formulated into a nonlinear optimization problem and optimized by a global optimization algorithm — the differential evolution algorithm (DE). The candidate knots selected in the first step are served for initial values of the DE algorithm. Since the candidate knots provide a good guess of knot positions, the DE algorithm can quickly converge. One advantage of the proposed algorithm is that the knot number and knot positions are determined automatically. Compared with the current existing algorithms, the proposed algorithm finds approximations with smaller fitting error when the knot number is fixed in advance. Furthermore, the proposed algorithm is robust to noisy data and can handle with few data points. We illustrate with some examples and applications.     

Adaptive Free-Knot Splines

This article proposes a function estimation procedure using free-knot splines as well as an associated algorithm for implementation in nonparametric regression. In contrast to conventional splines with knots confined to distinct design points, the splines allow selection of knot numbers and replacement of knots at any location and repeated knots at the same location. This exibility leads to an adaptive spline estimator that adapts any function with inhomogeneous smoothness, including discontinuity, which substantially improves the representation power of splines. Due to uses of a large class of spline functions, knot selection becomes extremely important. The existing knot selection schemes—such as stepwise selection—suffer the difficulty of knot confounding and are unsuitable for our purpose. A new knot selection scheme is proposed using an evolutionary Monte Carlo algorithm and an adaptive model selection criterion. The evolutionary algorithm locates the optimal knots accurately, whereas the adaptive model selection strategy guards against the selection error in searching through a large candidate knot space. The performance of the procedure is examined and illustrated via simulations. The procedure provides a significant improvement in performance over the other competing adaptive methods proposed in the literature. Finally, usefulness of the procedure is illustrated by an application to actual dataset.     

Differences of Alexander polynomials for knots caused by a single crossing change

Kondo and Sakai independently gave a characterization of Alexander polynomials for knots which are transformed into the trivial knot by a single crossing change. The first author gave a characterization of Alexander polynomials for knots which are transformed into the trefoil knot (and into the figure-eight knot) by a single crossing change. In this note, we will give a characterization of Alexander polynomials for knots which are transformed into the 10₁₃₂ knot (and into the (5,2)-torus knot) by a single crossing change. Moreover, this method can be applied for knots with monic Alexander polynomials.     

The BS class of Hermite spline quasi-interpolants on nonuniform knot distributions

The BS Hermite spline quasi-interpolation scheme is presented. It is related to the continuous extension of the BS linear multistep methods, a class of Boundary Value Methods for the solution of Ordinary Differential Equations. In the ODE context, using the numerical solution and the associated numerical derivative produced by the BS methods, it is possible to compute, with a local approach, a suitable spline with knots at the mesh points collocating the differential equation at the knots and having the same convergence order as the numerical solution. Starting from this spline, here we derive a new quasi-interpolation scheme having the function and the derivative values at the knots as input data. When the knot distribution is uniform or the degree is low, explicit formulas can be given for the coefficients of the new quasi-interpolant in the B-spline basis. In the general case these coefficients are obtained as solution of suitable local linear systems of size 2d×2d, where d is the degree of the spline. The approximation order of the presented scheme is optimal and the numerical results prove that its performances can be very good, in particular when suitable knot distributions are used.     

Three-Convex Approximation by Free Knot Splines in C [0, 1]

A Jackson-type estimate is obtained for the approximation of 3 -convex functions by 3 -convex splines with free knots. The order of approximation is the same as for the Jackson-type estimate for unconstrained approximation by splines with free knots. Shape-preserving free knot spline approximation of k -convex functions, k > 3 , is also considered. January 15, 1996. Date revised: December 9, 1996.     

On \pi-hyperbolic knots with the same 2-fold branched coverings

We consider the following problem from the Kirby's list (Problem 3.25): Let K be a knot in and M(K) its 2-fold branched covering space. Describe the equivalence class [K] of K in the set of knots under the equivalence relation if is homeomorphic to . It is known that there exist arbitrarily many different hyperbolic knots with the same 2-fold branched coverings, due to mutation along Conway spheres. Thus the most basic class of knots to investigate are knots which do not admit Conway spheres. In this paper we solve the above problem for knots which do not admit Conway spheres, in the following sense: we give upper bounds for the number of knots in the equivalence class [K] of a knot K and we describe how the different knots in the equivalence class of K are related. Received: 3 August 1998 / in final form: 17 June 1999     

Cobordism of disk knots

We study cobordisms and cobordisms rel boundary of PL locally-flat disk knots D ⁿ⁻² ↪ D ⁿ . Any two disk knots are cobordant if the cobordisms are not required to fix the boundary sphere knots, and any two even-dimensional disk knots with isotopic boundary knots are cobordant rel boundary. However, the cobordism rel boundary theory of odd-dimensional disk knots is more subtle. Generalizing results of J. Levine on the cobordism of sphere knots, we define disk knot Seifert matrices and show that two higher-dimensional disk knots with isotopic boundaries are cobordant rel boundary if and only if their disk knot Seifert matrices are algebraically cobordant. We also ask which algebraic cobordism classes can be realized given a fixed boundary knot and provide a complete classification when the boundary knot has no 2-torsion in its middle-dimensional Alexander module. In the course of this classification, we establish a close connection between the Blanchfield pairing of a disk knot and the Farber-Levine torsion pairing of its boundary knot (in fact, for disk knots satisfying certain connectivity assumptions, the disk knot Blanchfield pairing will determine the boundary Farber-Levine pairing). In addition, we study the dependence of disk knot Seifert matrices on choices of Seifert surface, demonstrating that all such Seifert matrices are rationally S-equivalent, but not necessarily integrally S-equivalent.     

Penalized Estimation of Free-Knot Splines

Abstract

Polynomial splines are often used in statistical regression models for smooth response functions. When the number and location of the knots are optimized, the approximating power of the spline is improved and the model is nonparametric with locally determined smoothness. However, finding the optimal knot locations is an historically difficult problem. We present a new estimation approach that improves computational properties by penalizing coalescing knots. The resulting estimator is easier to compute than the unpenalized estimates of knot positions, eliminates unnecessary “corners” in the fitted curve, and in simulation studies, shows no increase in the loss. A number of GCV and AIC type criteria for choosing the number of knots are evaluated via simulation.     

Constrained approximation by splines with free knots

In this paper, a method that combines shape preservation and least squares approximation by splines with free knots is developed. Besides the coefficients of the spline a subset of the knot sequence, the so-calledfree knots, is included in the optimization process resulting in a nonlinear least squares problem in both the coefficients and the knots. The original problem, a special case of aconstrained semi-linear least squares problem, is reduced to a problem that has only the knots of the spline as variables. The reduced problem is solved by a generalized Gauss-Newton method. Special emphasise is given to the efficient computation of the residual function and its Jacobian. Dedicated to our colleague and teacher Prof. Dr. J. W. Schmidt on the occasion of his 65th birthday Research of the first author was supported by Deutsche Forschungsgemeinschaft under grant Schm 968/2-1,2-2.     

Writhe polynomials and shell moves for virtual knots and links

The writhe polynomial is a fundamental invariant of an oriented virtual knot. We introduce a set of local moves for oriented virtual knots called shell moves. The first aim of this paper is to prove that two oriented virtual knots have the same writhe polynomial if and only if they are related by a finite sequence of shell moves. The second aim of this paper is to classify oriented 2-component virtual links up to shell moves by using several invariants of virtual links.     

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.     

Characterization Theorem for Best Polynomial Spline Approximation with Free Knots,Variable Degree and Fixed Tails

In this paper, we derive a necessary condition for a best approximation by piecewise polynomial functions of varying degree from one interval to another. Based on these results, we obtain a characterization theorem for the polynomial splines with fixed tails, that is the value of the spline is fixed in one or more knots (external or internal). We apply nonsmooth nonconvex analysis to obtain this result, which is also a necessary and sufficient condition for inf-stationarity in the sense of Demyanov–Rubinov. This paper is an extension of a paper where similar conditions were obtained for free tails splines. The main results of this paper are essential for the development of a Remez-type algorithm for free knot spline approximation.     

Spline interpolation at knot averages

It is well known that when interpolation points coincide with knots, the knot sequence must obey some restriction in order to guarantee the existence and boundedness of the interpolation projector. But, when the interpolation points are chosen to be the knot averages, the corresponding quadratic or cubic spline interpolation projectors are bounded independently of the knot sequence. Based on this fact, de Boor in 1975 made a conjecture that interpolation by splines of orderk at knot averages is bounded for anyk. In this paper we disprove de Boor's conjecture fork 20.Communicated by Wolfgang Dahmen.     

New obstructions to doubly slicing knots

A knot in the 3-sphere is called doubly slice if it is a slice of an unknotted 2-sphere in the 4-sphere. We give a bi-sequence of new obstructions for a knot being doubly slice. We construct it following the idea of Cochran-Orr-Teichner's filtration of the classical knot concordance group. This yields a bi-filtration of the monoid of knots (under the connected sum operation) indexed by pairs of half integers. Doubly slice knots lie in the intersection of this bi-filtration. We construct examples of knots which illustrate the non-triviality of this bi-filtration at all levels. In particular, these are new examples of algebraically doubly slice knots that are not doubly slice, and many of these knots are slice. Cheeger-Gromov's von Neumann rho invariants play a key role to show non-triviality of this bi-filtration. We also show some classical invariants are reflected at the initial levels of this bi-filtration, and obtain a bi-filtration of the double concordance group.     

Interpolation and Approximation by Splines on [0, ∞ )

We investigate interpolation and approximation problems by splines, which possess a countable set of knots on the positive axis. In particular, we characterize those sets of points, which admit unique Lagrange interpolation and give some sufficient and some necessary conditions for best approximations. Moreover, we show that the classical results of spline-approximation theory are not available for splines with a countable set of knots.     

Isotopy invariants for smooth tori in 4-manifolds

In this paper we define invariants under smooth isotopy for certain two-dimensional knots using some refined Cerf theory. One of the invariants is the knot type of some classical knot generalizing the string number of closed braids. The other invariant is a generalization of the unique invariant of degree 1 for classical knots in 3-manifolds. Possibly, these invariants can be used to distinguish smooth embeddings of tori in some 4-manifolds but which are equivalent as topological embeddings.     

On the Alexander polynomials of knots with Gordian distance one

We consider a condition on a pair of the Alexander polynomials of knots which are realizable by a pair of knots with Gordian distance one. We show that there are infinitely many mutually disjoint infinite subsets in the set of the Alexander polynomials of knots such that every pair of distinct elements in each subset is not realizable by any pair of knots with Gordian distance one. As one of the subsets, we have an infinite set containing the Alexander polynomials of the trefoil knot and the figure eight knot. We also show that every pair of distinct Alexander polynomials such that one is the Alexander polynomial of a slice knot is realizable by a pair of knots of Gordian distance one, so that every pair of distinct elements in the infinite subset consisting of the Alexander polynomials of slice knots is realizable by a pair of knots with Gordian distance one. These results solve problems given by Y. Nakanishi and by I. Jong.     

Union and tangle

Shibuya proved that any union of two nontrivial knots without local knots is a prime knot. In this note, we prove it in a general setting. As an application, for any nontrivial knot, we give a knot diagram such that a single unknotting operation on the diagram cannot yield a diagram of a trivial knot.