Approximation with polynomial kernels and SVM classifiers

This paper presents an error analysis for classification algorithms generated by regularization schemes with polynomial kernels. Explicit convergence rates are provided for support vector machine (SVM) soft margin classifiers. The misclassification error can be estimated by the sum of sample error and regularization error. The main difficulty for studying algorithms with polynomial kernels is the regularization error which involves deeply the degrees of the kernel polynomials. Here we overcome this difficulty by bounding the reproducing kernel Hilbert space norm of Durrmeyer operators, and estimating the rate of approximation by Durrmeyer operators in a weighted L¹ space (the weight is a probability distribution). Our study shows that the regularization parameter should decrease exponentially fast with the sample size, which is a special feature of polynomial kernels. Dedicated to Charlie Micchelli on the occasion of his 60th birthday Mathematics subject classifications (2000) 68T05, 62J02. Ding-Xuan Zhou: The first author is supported partially by the Research Grants Council of Hong Kong (Project No. CityU 103704).     

An Algorithm for Approximate Multiparametric Linear Programming

Multiparametric programming considers optimization problems where the data are functions of a parameter vector and describes the optimal value and an optimizer as explicit functions of the parameters. In this paper, we consider a linear program where the right-hand side is an affine function of a parameter vector; we propose an algorithm for approximating its solution. Given a full-dimensional simplex in the parameter space and an optimizer for each simplex vertex, the algorithm formulates the linear interpolation of the given solutions as an explicit function of the parameters, giving a primal feasible approximation of an optimizer inside the simplex. If the resulting absolute error in the objective exceeds a prescribed tolerance, then the algorithm subdivides the simplex into smaller simplices where it applies recursively. We propose both a basic version and a refined version of the algorithm. The basic version is polynomial in the output size, provided a polynomial LP solver is used; the refined version may give a smaller output. A global error bound for the optimizer is derived and some computational tests are discussed.     

Error analysis of multicategory support vector machine classifiers

The paper is related to the error analysis of Multicategory Support Vector Machine (MSVM) classifiers based on reproducing kernel Hilbert spaces. We choose the polynomial kernel as Mercer kernel and give the error estimate with De La Vallée Poussin means. We also introduce the standard estimation of sample error, and derive the explicit learning rate.     

Multi-kernel regularized classifiers

A family of classification algorithms generated from Tikhonov regularization schemes are considered. They involve multi-kernel spaces and general convex loss functions. Our main purpose is to provide satisfactory estimates for the excess misclassification error of these multi-kernel regularized classifiers when the loss functions achieve the zero value. The error analysis consists of two parts: regularization error and sample error. Allowing multi-kernels in the algorithm improves the regularization error and approximation error, which is one advantage of the multi-kernel setting. For a general loss function, we show how to bound the regularization error by the approximation in some weighted L^q$L^q$ spaces. For the sample error, we use a projection operator. The projection in connection with the decay of the regularization error enables us to improve convergence rates in the literature even for the one-kernel schemes and special loss functions: least-square loss and hinge loss for support vector machine soft margin classifiers. Existence of the optimization problem for the regularization scheme associated with multi-kernels is verified when the kernel functions are continuous with respect to the index set. Concrete examples, including Gaussian kernels with flexible variances and probability distributions with some noise conditions, are used to illustrate the general theory.     

Gap functions and error bounds for nonsmooth convex vector optimization problem

Abstract

In this article, our main aim is to develop gap functions and error bounds for a (non-smooth) convex vector optimization problem. We show that by focusing on convexity we are able to quite efficiently compute the gap functions and try to gain insight about the structure of set of weak Pareto minimizers by viewing its graph. We will discuss several properties of gap functions and develop error bounds when the data are strongly convex. We also compare our results with some recent results on weak vector variational inequalities with set-valued maps, and also argue as to why we focus on the convex case.     

Learning errors of linear programming support vector regression

In this paper, we give several results of learning errors for linear programming support vector regression. The corresponding theorems are proved in the reproducing kernel Hilbert space. With the covering number, the approximation property and the capacity of the reproducing kernel Hilbert space are measured. The obtained result (Theorem 2.1) shows that the learning error can be controlled by the sample error and regularization error. The mentioned sample error is summarized by the errors of learning regression function and regularizing function in the reproducing kernel Hilbert space. After estimating the generalization error of learning regression function (Theorem 2.2), the upper bound (Theorem 2.3) of the regularized learning algorithm associated with linear programming support vector regression is estimated.     

Robust multicategory support vector machines using difference convex algorithm

The support vector machine (SVM) is one of the most popular classification methods in the machine learning literature. Binary SVM methods have been extensively studied, and have achieved many successes in various disciplines. However, generalization to multicategory SVM (MSVM) methods can be very challenging. Many existing methods estimate k functions for k classes with an explicit sum-to-zero constraint. It was shown recently that such a formulation can be suboptimal. Moreover, many existing MSVMs are not Fisher consistent, or do not take into account the effect of outliers. In this paper, we focus on classification in the angle-based framework, which is free of the explicit sum-to-zero constraint, hence more efficient, and propose two robust MSVM methods using truncated hinge loss functions. We show that our new classifiers can enjoy Fisher consistency, and simultaneously alleviate the impact of outliers to achieve more stable classification performance. To implement our proposed classifiers, we employ the difference convex algorithm for efficient computation. Theoretical and numerical results obtained indicate that for problems with potential outliers, our robust angle-based MSVMs can be very competitive among existing methods.     

一元向量有理插值的误差公式

Ｇｒａｖｅｓ－Ｍｏｒｒｉｓ于１９８３年利用向量的Ｓａｍｅｌｓｏｎ逆变换建立了一种实用的向量有理插值方法。本文得到了该向量有理插值的一个精确的误差公式。     

Fehlerabschätzungen bei Polynomgleichungen mit dem Fixpunktsatz von Brouwer

Summary It is supposed that to every zero of a polynomial of degreem an approximation is known. A method is described to give a simultaneous error estimation. The idea is to construct an operator of them-dimensional vector space such that the components of its fixed point are exactly the zeros of the polynomial. Under certain conditions an error bound for the fixed point and hence for the zeros of the polynomial follows from BROUWER'S fixed point theorem. The estimation received is numerically useful.     

A triangular spectral method for the Stokes eigenvalue problem by the stream function formulation

An efficient spectral method is developed in this paper for the two‐dimensional Stokes eigenvalues on arbitrary triangle. By using the spectral theory of compact operator and approximate property of orthogonal polynomial, we give the error estimate of the approximate eigenvalues and eigenfunctions. In addition, we also present some numerical results to show the validity of our algorithm and the correctness of the theoretical results.     

Error estimates for irregular sampling of band-limited functions on a locally compact Abelian group

Band-limited functions f can be recovered from their sampling values (f(x_i)) by means of iterative methods, if only the sampling density is high enough. We present an error analysis for these methods, treating the typical forms of errors, i.e., jitter error, truncation error, aliasing error, quantization error, and their combinations. The derived apply uniformly to whole families of spaces, e.g., to weighted L^p-spaces over some locally compact Abelian group with growth rate up to some given order. In contrast to earlier papers we do not make use of any (relative) separation condition on the sampling sets. Furthermore we discard the assumption on polynomial growth of the weights that has been used over Euclidean spaces. Consequently, even for the case of regular sampling, i.e., sampling along lattices in G, the results are new in the given generality.     

Lagrange四边形单位分解有限元法的最优误差分析

用构造最优局部逼近空间的方法对Lagrange型四边形单位分解有限元法进行了最优误差分析.单位分解取Lagrange型四边形上的标准双线性基函数,构造了一个特殊的局部多项式逼近空间,给出了具有2阶再生性的Lagrange型四边形单位分解有限元插值格式,从而得到了高于局部逼近阶的最优插值误差.     

改进Lagrange插值多项式误差上界的系数

当用Lagrange插值多项式逼近函数时,重要的是要了解误差项的性态.本文研究具有等距节点的Lagrange插值多项式,估计了Lagrange插值多项式逼近函数误差项的上界,改进了小于5次Lagrange插值多项式逼近函数误差界的系数.     

Finite‐time stability of a class of oscillating systems with two delays

In this paper, we study finite‐time stability of an oscillating system with 2 delays. To derive a bounded of state vector, we use a representation of explicit solution involving 2‐delayed matrix polynomial of 2 indices after deriving some fundamental estimates for such delayed matrix polynomial of 2 indices. A sufficient condition is given. Finally, an example is given to demonstrate the application of the main result.     

Nordsieck representation of DIMSIMs

A new representation for diagonally implicit multistage integration methods (DIMSIMs) is derived in which the vector of external stages directly approximates the Nordsieck vector. The methods in this formulation are zero-stable for any choice of variable mesh. They are also easy to implement since changing step-size corresponds to a simple rescaling of the vector of external approximations. The paper contains an analysis of local truncation error and of error accumulation in a variable step-size situation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Composite Quantile Estimation in Partial Functional Linear Regression Model Based on Polynomial Spline

In this paper, we consider composite quantile regression for partial functional linear regression model with polynomial spline approximation. Under some mild conditions, the convergence rates of the estimators and mean squared prediction error, and asymptotic normality of parameter vector are obtained. Simulation studies demonstrate that the proposed new estimation method is robust and works much better than the least-squares based method when there are outliers in the dataset or the random error follows heavy-tailed distributions. Finally, we apply the proposed methodology to a spectroscopic data sets to illustrate its usefulness in practice.     

Shape calculus and finite element method in smooth domains

The use of finite elements in smooth domains leads naturally to polyhedral or piecewise polynomial approximations of the boundary. Hence the approximation error consists of two parts: the geometric part and the finite element part. We propose to exploit this decomposition in the error analysis by introducing an auxiliary problem defined in a polygonal domain approximating the original smooth domain. The finite element part of the error can be treated in the standard way. To estimate the geometric part of the error, we need quantitative estimates related to perturbation of the geometry. We derive such estimates using the techniques developed for shape sensitivity analysis.     

Correction to Generic polynomial vector fields are not integrable

In the paper Generic polynomial vector fields are not integrable [1], we study some generic aspects of polynomial vector fields or polynomial derivations with respect to their integration. Using direct sums of derivations together with our previous results we showed that, for all n ≥ 3 and s ≥ 2, the absence of polynomial first integrals, or even of Darboux polynomials, is generic for homogeneous polynomial vector fields of degree s in n variables. To achieve this task, we need an example of such vector fields of degree s ≥ 2 for any prime number n ≥ 3 of variables and also for n = 4. The purpose of this note is to correct a gap in our paper for n = 4 by completing the corresponding proof.     

Bivariate second-order linear partial differential equations and orthogonal polynomial solutions

In this paper we construct the main algebraic and differential properties and the weight functions of orthogonal polynomial solutions of bivariate second-order linear partial differential equations, which are admissible potentially self-adjoint and of hypergeometric type. General formulae for all these properties are obtained explicitly in terms of the polynomial coefficients of the partial differential equation, using vector matrix notation. Moreover, Rodrigues representations for the polynomial eigensolutions and for their partial derivatives of any order are given. As illustration, these results are applied to a two parameter monic Appell polynomials. Finally, the non-monic case is briefly discussed.     

Gap functions for vector variational inequalities

In this article, we intend to study several scalar-valued gap functions for Stampacchia and Minty-type vector variational inequalities. We first introduce gap functions based on a scalarization technique and then develop a gap function without any scalarizing parameter. We then develop its regularized version and under mild conditions develop an error bound for vector variational inequalities with strongly monotone data. Further, we introduce the notion of a partial gap function which satisfies all, but one of the properties of the usual gap function. However, the partial gap function is convex and we provide upper and lower estimates of its directional derivative.