Restructuring forward step of MARS algorithm using a new knot selection procedure based on a mapping approach

In high dimensional data modeling, Multivariate Adaptive Regression Splines (MARS) is a popular nonparametric regression technique used to define the nonlinear relationship between a response variable and the predictors with the help of splines. MARS uses piecewise linear functions for local fit and apply an adaptive procedure to select the number and location of breaking points (called knots). The function estimation is basically generated via a two-stepwise procedure: forward selection and backward elimination. In the first step, a large number of local fits is obtained by selecting large number of knots via a lack-of-fit criteria; and in the latter one, the least contributing local fits or knots are removed. In conventional adaptive spline procedure, knots are selected from a set of all distinct data points that makes the forward selection procedure computationally expensive and leads to high local variance. To avoid this drawback, it is possible to restrict the knot points to a subset of data points. In this context, a new method is proposed for knot selection which bases on a mapping approach like self organizing maps. By this method, less but more representative data points are become eligible to be used as knots for function estimation in forward step of MARS. The proposed method is applied to many simulated and real datasets, and the results show that it proposes a time efficient forward step for the knot selection and model estimation without degrading the model accuracy and prediction performance.     

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.     

一种分形图像编码的改进方法

在分析小波包变换和分形编码特点的基础上,先将图像进行小波包分解,对进一步细分的高频部分直接进行频域截断,对低频部分进行分形压缩.计算机模拟试验表明,上述方案与基本分形编码方法相比,在重建图像主观质量和运行时间上都显示出优越性.     

New polynomials of knots

For some knots and links with respect to regular isotopy, we introduce a new invariant, which is a Laurent polynomial in three variables. The properties of this invariant are studied. Kiev University, Kiev. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 49, No. 9, pp. 1230–1235, September, 1997.     

On a Sparse Representation of an n-Dimensional Laplacian in Wavelet Coordinates

Important parts of adaptive wavelet methods are well-conditioned wavelet stiffness matrices and an efficient approximate multiplication of quasi-sparse stiffness matrices with vectors in wavelet coordinates. Therefore it is useful to develop a well-conditioned wavelet basis with respect to which both the mass and stiffness matrices are sparse in the sense that the number of nonzero elements in each column is bounded by a constant. Consequently, the stiffness matrix corresponding to the n-dimensional Laplacian in the tensor product wavelet basis is also sparse. Then a matrix–vector multiplication can be performed exactly with linear complexity. In this paper, we construct a wavelet basis based on Hermite cubic splines with respect to which both the mass matrix and the stiffness matrix corresponding to a one-dimensional Poisson equation are sparse. Moreover, a proposed basis is well-conditioned on low decomposition levels. Small condition numbers for low decomposition levels and a sparse structure of stiffness matrices are kept for any well-conditioned second order partial differential equations with constant coefficients; furthermore, they are independent of the space dimension.     

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.     

Two constructions of weight systems for invariants of knots in non-trivial 3-manifolds

A new family of weight systems of finite type knot invariants of any positive degree in orientable 3-manifolds with non-trivial first homology group is constructed. The principal part of the Casson invariant of knots in such manifolds is split into the sum of infinitely many independent weight systems. Examples of knots separated by corresponding invariants and not separated by any other known finite type invariants are presented.     

基于正弦和余弦函数的小波滤波器的统一解析构造

首次提出用正弦函数和余弦函数解析构造任意长度的紧支集正交小波滤波系数,首先给出了对N＝2k-1时（k个参数）的解析结构,其次给出了N＝2k时正交小波滤波器的统一构造方法,此后验证了著名的Daubechies小波滤波器的构成参数,并验证了一些被广泛的使用的著名小波分析滤波器,所有这些滤波器容易用一组参数直接计算出来,小波滤波器的解析构造使得在应用中动态选择小波基变得极基容易,这一结果必将在小波理论,应用数学及模式识别等领域产生十分重要的作用。     

Algorithms in low-dimensional topology: holonomic parametrization of knots

In this work, we reintroduce the so-called AFL (Arkaden-Faden-Lage) representation of knots introduced by Kurt Reidemeister and show how it can be used to develop efficient algorithms in low-dimensional topology. In particular, we develop an algorithm to calculate the functions for the holonomic parametrization of knots introduced by Vassiliev in 1997, who proved that each knot type has a holonomic parametrization (but no method to find such a parametrization was known). Further, we show that the result of Vassiliev can be easily derived from the AFL representation of knots. This is one of the first practical results of the application of the AFL representation of knots that can open new perspectives in the field of low dimensional topology such as computation of the Kontsevich integral and some operators of quantum groups.     

二进小波的构造方法研究

提出两种二进小波的构造方法.首先,将Mallat构造的B-样条二进小波推广得到一种构造B-样条二进小波的新方法;其次,基于二进提升方案提出构造二进小波的另一种新方法—–构造定理,并通过调整定理中提升参数的形式、以新的B-样条二进小波作为初始二进小波,具体构造了具有有限长单位脉冲响应、高阶消失矩、线性相位的提升二进小波,这些提升二进小波不能由Sweldens提升方案得到.     

Improved cubature formulae of high degrees of exactness for the square

The method of constructing minimal cubature rules with high algebraic degrees of exactness is developed by adapting a powerful algorithm for solving the system of nonlinear equations. As a result, new cubature formulae of degrees 15, 17, 19, 21, and 23 are derived for the square. They lead to lower numbers of knots and/or to better quality with respect to those known previously. The formulae obtained should be considered as the most efficient for the calculation of two-dimensional integrals with a high precision.     

A new algorithm for fixed design regression and denoising

In this paper, we present a new algorithm to estimate a regression function in a fixed design regression model, by piecewise (standard and trigonometric) polynomials computed with an automatic choice of the knots of the subdivision and of the degrees of the polynomials on each sub-interval. First we give the theoretical background underlying the method: the theoretical performances of our penalized least-squares estimator are based on non-asymptotic evaluations of a mean-square type risk. Then we explain how the algorithm is built and possibly accelerated (to face the case when the number of observations is great), how the penalty term is chosen and why it contains some constants requiring an empirical calibration. Lastly, a comparison with some well-known or recent wavelet methods is made: this brings out that our algorithm behaves in a very competitive way in term of denoising and of compression.     

Wavelet variance analysis for gappy time series

The wavelet variance is a scale-based decomposition of the process variance for a time series and has been used to analyze, for example, time deviations in atomic clocks, variations in soil properties in agricultural plots, accumulation of snow fields in the polar regions and marine atmospheric boundary layer turbulence. We propose two new unbiased estimators of the wavelet variance when the observed time series is ‘gappy,’ i.e., is sampled at regular intervals, but certain observations are missing. We deduce the large sample properties of these estimators and discuss methods for determining an approximate confidence interval for the wavelet variance. We apply our proposed methodology to series of gappy observations related to atmospheric pressure data and Nile River minima.     

Novel Chebyshev wavelets algorithms for optimal control and analysis of general linear delay models

A new efficient type of Chebyshev wavelet is used to find the optimal solutions of general linear, continuous-time, multi-delay systems with quadratic performance indices and also to obtain the responses of linear time-delay systems. According to the new definition of Chebyshev wavelets, the operational matrices of integration, product, delay and inverse time and the integration matrix are derived. Furthermore, new operational matrices as the piecewise delay operational matrix and the stretch operational matrix of the desired Chebyshev wavelets are introduced to analyze systems with, in turn, piecewise constant delays and stretched arguments or proportional delays. Two novel algorithms based on newly Chebyshev wavelet method are proposed for the optimal control and the analysis of delay models. Some examples are solved to establish that the accuracy and applicability of Chebyshev wavelet method in delay systems are increased.     

New perspectives on self-linking

We initiate the study of classical knots through the homotopy class of the nth evaluation map of the knot, which is the induced map on the compactified n-point configuration space. Sending a knot to its nth evaluation map realizes the space of knots as a subspace of what we call the nth mapping space model for knots. We compute the homotopy types of the first three mapping space models, showing that the third model gives rise to an integer-valued invariant. We realize this invariant in two ways, in terms of collinearities of three or four points on the knot, and give some explicit computations. We show this invariant coincides with the second coefficient of the Conway polynomial, thus giving a new geometric definition of the simplest finite-type invariant. Finally, using this geometric definition, we give some new applications of this invariant relating to quadrisecants in the knot and to complexity of polygonal and polynomial realizations of a knot.     

Isomorphism of the Groups of Vassiliev Invariants of Legendrian and Pseudo-Legendrian Knots

The study of the Vassiliev invariants of Legendrian knots was started by D. Fuchs and S. Tabachnikov who showed that the groups of C-valued Vassiliev invariants of Legendrian and of framed knots in the standard contact R³ are canonically isomorphic. Recently we constructed the first examples of contact 3-manifolds where Vassiliev invariants of Legendrian and of framed knots are different. Moreover in these examples Vassiliev invariants of Legendrian knots distinguish Legendrian knots that are isotopic as framed knots and homotopic as Legendrian immersions. This raised the question what information about Legendrian knots can be captured using Vassiliev invariants. Here we answer this question by showing that for any contact 3-manifold with a cooriented contact structure the groups of Vassiliev invariants of Legendrian knots and of knots that are nowhere tangent to a vector field that coorients the contact structure are canonically isomorphic.     

Interpolatory integration rules and orthogonal polynomials with varying weights

We investigate which types of asymptotic distributions can be generated by the knots of convergent sequences of interpolatory integration rules. It will turn out that the class of all possible distributions can be described exactly, and it will be shown that the zeros of polynomials that are orthogonal with respect to varying weight functions are good candidates for knots of integration rules with a prescribed asymptotic distribution.Research supported by the Deutsche Forschungsgemeinschaft (AZ: Sta 299/4-2).     

Selecting the Number of Knots for Penalized Splines

Penalized splines, or P-splines, are regression splines fit by least-squares with a roughness penalty.P-splines have much in common with smoothing splines, but the type of penalty used with a P-spline is somewhat more general than for a smoothing spline. Also, the number and location of the knots of a P-spline is not fixed as with a smoothing spline. Generally, the knots of a P-spline are at fixed quantiles of the independent variable and the only tuning parameters to choose are the number of knots and the penalty parameter. In this article, the effects of the number of knots on the performance of P-splines are studied. Two algorithms are proposed for the automatic selection of the number of knots. The myopic algorithm stops when no improvement in the generalized cross-validation statistic (GCV) is noticed with the last increase in the number of knots. The full search examines all candidates in a fixed sequence of possible numbers of knots and chooses the candidate that minimizes GCV.The myopic algorithm works well in many cases but can stop prematurely. The full-search algorithm worked well in all examples examined. A Demmler–Reinsch type diagonalization for computing univariate and additive P-splines is described. The Demmler–Reinsch basis is not effective for smoothing splines because smoothing splines have too many knots. For P-splines, however, the Demmler–Reinsch basis is very useful for super-fast generalized cross-validation.     

非平稳时间序列分析的WAVELET—改进GM(1,1)组合方法及其应用

提出非平稳时间序列分析的WAVELET—改进GM(1,1)组合方法.首先利用Mallat算法对非平稳时间序列进行小波分解;然后采用能量阈值选择策略对高频系数进行处理,并将其与低频系数进行小波重构;最后运用改进的GM(1,1)方法预测.该方法不仅能充分拟合低频信息,而且可避免对高频信息的过拟合.实验结果证明,该方法比传统的非平稳时间序列预测方法具有更高的预测精度.     

Computation of differential operators in aggregated wavelet frame coordinates

Manuel Werner ^{Adaptive wavelet algorithms for solving operator equations havebeen shown to converge with the best possible rates in linearcomplexity. For the latter statement, all costs are taken intoaccount, i.e. also the cost of approximating entries from theinfinite stiffness matrix with respect to the wavelet basisusing suitable quadrature. A difficulty is the constructionof a suitable wavelet basis on the generally non-trivially shapeddomain on which the equation is posed. In view of this, recentlycorresponding algorithms have been proposed that require onlya wavelet frame instead of a basis. By employing an overlappingdecomposition of the domain, where each subdomain is the smoothparametric image of the unit cube, and by lifting a waveletbasis on this cube to each of the subdomains, the union of thesecollections defines such a frame. A potential bottleneck withinthis approach is the efficient approximation of entries correspondingto pairs of wavelets from different collections. Indeed, suchwavelets are piecewise smooth with respect to mutually non-nestedpartitions. In this paper, considering partial differentialoperators and spline wavelets on the subdomains, we proposean easy implementable quadrature scheme to approximate the requiredentries, which allows the fully discrete adaptive frame algorithmto converge with the optimal rate in linear complexity.}