Abstract: The K-local hyperplane distance nearest neighbor (HKNN) algorithm is a local classification method that builds nonlinear decision surfaces by using locally linear manifolds directly in the original sample space. Although it has been successfully applied in several classification tasks, it is limited to using the Euclidean distance metric, which is a significant limitation in the practice. In this paper we reformulate HKNN in terms of subspaces, and propose a variant, the Local Discriminative Common Vector (LDCV) method, that is more suitable for classification tasks where the classes have similar intra-class variations. We then extend both methods to the nonlinear case by using the kernel trick to map the data into a higherdimensional space, in which the linear manifolds are constructed. This construction allows us to use a wide variety of distance functions for the local classifiers, while computing distances between the query sample and the nonlinear manifolds remains straightforward owing to linear nature of the manifolds in the mapped space. We tested the proposed methods on several classification tasks, obtaining better results than both the Support Vector Machines (SVMs) and their local counterpart SVM-KNN on the USPS and Image segmentation databases, and outperforming the local SVM-KNN on the Caltech and Xerox10 visual recognition databases.

Abstract: The common vector (CV) method is a linear subspace classifier method which allows one to discriminate between classes of data sets, such as those arising in image and word recognition. This method utilizes subspaces that represent classes during classification. Each subspace is modeled such that common features of all samples in the corresponding class are extracted. To accomplish this goal, the method eliminates features that are in the direction of the eigenvectors corresponding to the nonzero eigenvalues of the covariance matrix of each class. In this paper, we introduce a variation of the CV method, which will be referred to as the modified CV (MCV) method. Then, a novel approach is proposed to apply the MCV method in a nonlinearly mapped higher dimensional feature space. In this approach, all samples are mapped into a higher dimensional feature space using a kernel mapping function, and then, the MCV method is applied in the mapped space. Under certain conditions, each class gives rise to a unique CV, and the method guarantees a 100% recognition rate with respect to the training set data. Moreover, experiments with several test cases also show that the generalization performance of the proposed kernel method is comparable to the generalization performances of other linear subspace classifier methods as well as the kernel-based nonlinear subspace method. While both the MCV method and its kernel counterpart did not outperform the support vector machine (SVM) classifier in most of the reported experiments, the application of our proposed methods is simpler than that of the multiclass SVM classifier. In addition, it is not necessary to adjust any parameters in our approach.

Abstract: In the 1920s, B. N. Delaunay proved that the dual graph of the Voronoi diagram of a discrete set of points in a Euclidean space gives rise to a collection of simplices, whose circumspheres contain no points from this set in their interior. Such Delaunay simplices tessellate the convex hull of these points. An equivalent formulation of this property is that the characteristic functions of the Delaunay simplices form a partition of unity. In the paper this result is generalized to the so-called Delaunay configurations. These are defined by considering all simplices for which the interiors of their circumspheres contain a fixed number of points from the given set, in contrast to the Delaunay simplices, whose circumspheres are empty. It is proved that every family of Delaunay configurations generates a partition of unity, formed by the so-called simplex splines. These are compactly supported piecewise polynomial functions which are multivariate analogs of the well-known univariate B-splines. It is also shown that the linear span of the simplex splines contains all algebraic polynomials of degree not exceeding the degree of the splines.

Abstract: In some pattern recognition tasks, the dimension of the sample space is larger than the number of the samples in the training set. This is known as the "small sample size problem". The Linear Discriminant Analysis (LDA) techniques cannot be applied directly to the small sample size case. The small sample size problem is also encountered when kernel approaches are used for recognition. In this paper we try to answer the question of "How should we choose the optimal projection vectors for feature extraction for the small sample size case?" Then, we propose a new method called the Kernel Discriminative Common Vector (Kernel DCV) method, based on our findings. In this method, we first nonlinearly map the original input space to an implicit higher-dimensional feature space through a kernel mapping, where the data are hoped to be linearly separable. Then, the optimal projection vectors are computed in the transformed space. The proposed method yields an optimal solution for maximizing the modified Fisher's Linear Discriminant criterion given in the paper. Thus, a 100% recognition rate is always guaranteed for the training set samples. Experiments on test data sets also show that the generalization ability of the proposed method outperforms other kernel approaches in many situations.

Abstract: We present results summarizing the utility of bivariate B-splines for solving data fitting and related problems. These basis functions are defined by certain collections of points in the plane, called knots. The B-splines are piecewise quadratic compactly-supported functions, possessing optimal order of differentiability (C^1). The linear span of these functions gives rise to a spline space with good approximation properties. Our experimental results show that the B-spline basis also entertains excellent spectral properties, rendering the B-splines useful for, among other things, iterative solution of data fitting and scattering problems in computational electromagnetics.

Abstract: In face recognition tasks, the dimension of the sample space is typically larger than the number of the samples in the training set. As a consequence, the within-class scatter matrix is singular and the Linear Distriminant Analysis (LDA) method cannot be applied directly. This problem is known as the "small sample size problem". In this paper, we propose a new face recognition method called the Discriminative Common Vector method, based on a variation of Fisher's Linear Discriminant Analysis for the small size case. Two different algorithms are given to extract the discriminative common vectors representing each person in the training set while the other uses the subspace methods and the Gram-Schmidt orthogonalization procedure to obtain the discriminative common vectors. The thesese vectors are used for classification of new faces. The proposed method yields an optimal solution for maximizing the modified Fisher's Linear Discriminant criterion given in the paper. Our results show that the Discriminative Common Vector method is superior to other methods in terms of recognition accuracy, efficiency, and numerical stability.

Abstract: Bounds are provided on how well functions in Sobolev spaces on the sphere can be approximated by spherical splines, where a spherical spline of degree $d$ is a $C^r$ function whose pieces are the restrictions of homogoneous polynomials of degree $d$ to the sphere. The bounds are expressed in terms of appropriate seminorms defined with the help of radial projection, and are obtained using appropriate quasi-interpolation operators.

Abstract: A new class of Godunov-type numerical methods for solving nonlinear scalar conservation laws in one space dimension is introduced. This new class of methods, called weakly non-oscillatory (WNO), is a generalization of the classical non-oscillatory schemes. Under certain conditions, convergence and error estimates for the methods are proved. Examples of such WNO schemes include modified versions of Min-Mod and UNO.

Abstract: The problem of solving pseudodifferential equations on spheres by collocation with zonal kernels is considered and bounds for the approximation error are established. The bounds are given in terms of the maximum separation distance of the collocation points, the order of the pseudodifferential operator, and the smoothness of the employed zonal kernel. A by-product of the results is an improvement on the previously known convergence order estimates for Lagrange interpolation.

Abstract: This chapter addresses the topic of ``splines on surfaces'', an area of spline theory concerned with the construction of functions defined on manifolds in three-dimensional Euclidean space. For the most part, the mathematical aspects of this discipline are in their infancy and therefore much of what we will say here has an exploratory character.

Abstract: The utility of subdivision techniques is investigated from the point of view of geometric modeling applications. This report summarizes the findings and recommendations of the authors concerning the usefulness of subdivision surfaces for geometric modeling, and in particular for engineering applications.

Abstract: In the first part of the paper, the problem of defining multivariate splines in a natural way is formulated and discussed. Then, several existing constructions of multivariate splines are surveyed, namely those based on simplex splines. Various difficulties and practical limitations associated with such constructions are pointed out. The second part of the paper is concerned with the description of a new generalization of univariate splines. This generalization utilizes the novel concept of the so-called Delaunay configurations, used to select collections of knot-sets for simplex splines. The linear span of the simplex splines forms a spline space with several interesting properties. The space depends uniquely and in a local way on the prescribed knots and does not require the use of auxiliary or perturbed knots, as is the case with some earlier constructions. Moreover, the spline space has a useful structure that makes it possible to represent polynomials explicitly in terms of simplex splines. This representation closely resembles a familiar univariate result in which polar forms are used to express polynomials as linear combinations of the classical B-splines.

Abstract:A construction of bivariate splines is described, based on a new concept of higher degree Delaunay configurations. The crux of this construction is that knot-sets for simplex B-splines are selected by considering groups of ``nearby'' knots. The new approach gives rise to a natural generalization of univariate splines in that the linear span of this collection of B-splines forms a space which is analogous to the classical univariate splines. This new spline space depends uniquely and in a local way on the prescribed knot locations, and there is no need to use auxiliary or perturbed knots as in some earlier constructions.

Abstract: Let $X$ and $Y$ be topological vector spaces, $A$ be a continuous linear map from $X$ to $Y$, $C \subset X$, $B$ be a convex set dense in $C$, and $d \in Y$ be a data point. Conditions are derived guaranteeing the set $B \cap A^{-1}(d)$ to be nonempty and dense in $C \cap A^{-1}(d)$. The paper generalizes earlier results by the authors to the case where $Y$ is infinite dimensional. The theory is illustrated with two examples concerning the existence of smooth monotone extensions of functions defined on a domain of the Euclidean space to a larger domain.

Abstract: A class of generalized polynomials is considered consisting of the null spaces of certain differential operators with constant coefficients. This class strictly contains ordinary polynomials and appropriately scaled trigonometric polynomials. An analog of the classical Bernstein operator is introduced and it is shown that generalized Bernstein polynomials of a continuous function converge to this function. A convergence result is also proved for degree elevation of the generalized polynomials. Moreover, the geometric nature of these functions is discussed and a connection with certain rational parametric curves is established.

Abstract: Under the assumption that a given two-scale refinement equation possesses a continuous solution, called a refinable function, necessary and sufficient conditions are derived for convergence of the corresponding univariate stationary subdivision scheme with a finitely supported mask. These conditions are expressed using the factorization of the subdivision mask and do not require the computation of a spectral radius of matrices or solving an eigenvalue problem.

The main result is that subdivision is convergent if and only if it is convergent for sequences characterizing linear dependence relations for integershifts of the refinable function. Moreover, this function can be generated by employing a convergent subdivision corresponding to an appropriately chosen mask.

As a consequence of the main results it is shown that subdivision associated with a nonnegative mask, satisfying a simple condition, converges if and only if the corresponding refinement equation possesses a continuous solution.

Abstract: We show how to design cam profiles using NURBS curves whose support functions are appropriately scaled trigonometric splines. In particular, we discuss the design of cams with various side conditions of practical interest, such as interpolation conditions, constant diameter, minimal acceleration or jerk, and constant dwells. In contrast to general polynomial curves, these NURBS curves have the useful property that their offsets are of the same type, and hence also have an exact NURBS representation.

Abstract: We review the theory of homogeneous splines and their relationship to special rational splines considered by J.~S\'{a}nchez-Reyes and independently by P.~de~Casteljau who called them focal splines. Applying an appropriate duality, we transform focal splines into a remarkable class of rational curves with rational offsets. We investigate geometric properties of these dual focal splines, and discuss applications to curve design problems.

Abstract: Let $X$ be a topological vector space, $Y=\R^n$, $n \in \N$, $A$ a continuous linear map from $X$ to $Y$, $C \subset X$, $B$ a convex set dense in $C$, and $d \in Y$ a data point. We derive conditions which guarantee that the set $B \cap A^{-1}(d)$ is nonempty and dense in $C \cap A^{-1}(d)$. Some applications to shape preserving interpolation and approximation are described.

Abstract: Homogeneous simplex splines, also known as cone splines or multivariate truncated power functions, are discussed from a perspective of homogeneous divided differences and polar forms. This makes it possible to derive the basic properties of these splines in a simple and economic way. In addition, a construction of spaces of homogeneous simplex splines is considered, which in the non-homogeneous setting is due to Dahmen, Micchelli, and Seidel. A proof for this construction is presented, based on knot insertion. Restricting the homogeneous splines to a sphere gives rise to spaces of spherical simplex splines.

Abstract: Spaces of polynomial splines defined on planar triangulations are very useful tools for fitting scattered data in the plane. Recently, [\cite{ANS2}, \cite{ANS3}], using homogeneous polynomials, we have developed analogous spline spaces defined on triangulations on the sphere and on sphere-like surfaces. Using these spaces, it is possible to construct analogs of many of the classical interpolation and fitting methods. Here we examine some of the more interesting ones in detail. For interpolation, we discuss macro-element methods and minimal energy splines, and for fitting, we consider discrete least squares and penalized least squares.

Abstract: Recently, we have introduced spaces of splines defined on triangulations lying on the sphere or on sphere-like surfaces. These spaces arose out of a new kind of Bernstein-Bezier theory on such surfaces. The purpose of this paper is to contribute to the development of a constructive theory for such spline spaces analogous to the well-known theory of polynomial splines on planar triangulations. Rather than working with splines on sphere-like surfaces directly, we instead investigate more general spaces of homogeneous splines in R^3. In particular, we present formulae for the dimensions of such spline spaces, and construct locally supported bases for them.

Abstract: In this article we consider a class of functions, called $\cD$-polynomials, which are contained in the null space of certain second order differential operators with constant coefficients. The class of splines generated by these $\cD$-polynomials strictly contains the polynomial, trigonometric and hyperbolic splines. The main objective of this paper is to present a unified theory of this class of splines via the concept of a polar form. By systematically employing polar forms, we extend essentially all of the well-known results concerning polynomial splines. Among other topics, we introduce a Schoenberg operator and define control curves for these splines. We also examine the knot insertion and subdivision algorithms and prove that the subdivision schemes converge quadratically.

Abstract: In this paper we discuss a natural way to define barycentric coordinates on the sphere and on general sphere-like surfaces. This leads to a theory of Bernstein-Bezier polynomials which parallels the familiar planar case. Our constructions are based on a study of homogeneous polynomials on trihedra in $\RR^3$. The special case of Bernstein-Bezier polynomials on a circle is considered in detail.

Abstract: We discuss a natural way to define barycentric coordinates associated with circular arcs. This leads to a theory of Bernstein-Bezier polynomials which parallels the familiar interval case, and which has close connections to trigonometric polynomials.

Abstract: We introduce control curves for trigonometric splines and show that they have properties similar to those for classical polynomial splines. In particular, we discuss knot-insertion algorithms, and show that as more and more knots are inserted into a trigonometric spline, the associated control curves converge to the spline. In addition, we establish a convex-hull property and a variation-diminishing result.

Abstract: We begin by defining the polar form for a special type of function, namely a trigonometric polynomial, in order to illustrate the similarities between trigonometric polar forms and polynomial polar forms. After deriving properties and developing some results concerning trigonometric polar forms, we consider the generalization to functions that are elements of certain null spaces of constant coefficient differential operators.

Abstract: The problem of interpolating scattered 3D data by a geometrically smooth surface is considered. A completely local method is proposed, based on employing degenerate triangular Bernstein-B\'ezier patches. An analysis of these patches is given and some numerical experiments with quartic and quintic patches are presented.

Abstract: A local construction of a $GC^1$ interpolating surface to given scattered data in $\R^3$ can give rise to degenerate Bernstein-B\'{e}zier patches. That means the parametrization at vertices is not regular in the sense that the length of the tangent vector to any curve passing through a vertex is zero at that vertex. This implies that the curvature of these curves tends to infinity whenever one approaches a vertex. This fact seems to have not a negative influence on the shape of the surface.

Abstract: The notion of the univariate divided differences is generalized to the multivariate case. This generalization is based on a pointwise evaluation of a certain multivariate function. Several properties of the defined multivariate divided difference functional are derived and a link with the multivariate simplex splines is established. This gives a new generalization of the so called truncated power function, which is different from the one given in \cite{Dahmen79,Dahmen80}.

Abstract: Discrete analogues of multivariate simplex splines are introduced. Their study yields a subdivision scheme for simplex splines.

Abstract: Some negative results concerning convexity preserving approximation and interpolation of multivariate functions are presented. We prove that the approximation based on both interpolation and local operators cannot be convexity preserving, provided the approximation space is (locally) finite dimensional. In both cases we can dispense with the asssumption of the linearity of the approximation operator and the assumption that the approximation space is a space of piecewise polynomials. Some consequences for the construction of shape preserving approximations are discussed.

Abstract: Bivariate quadratic simplicial B-splines defined by their corresponding set of knots derived from a (suboptimal) constrained Delaunay triangulation of the domain are employed to obtain a C^1 smooth surface. The generation of triangle vertices is adjusted to the areal distribution of the data in the domain. We emphasize here that the vertices of the triangles initially define the knots of the B-splines and do generally not coincide with the abscissae of the data. Thus, this approach is well suited to process scattered data. With each vertex of a given triangle we associate two additional points which give rise to six configurations of five knots defining six linearly independent bivariate quadratic B-splines supported on the convex hull of the corresponding five knots.

Abstract: The dissertation is devoted to the study of theoretical and practical aspects of multivariate splines and related topics from the constructive approximation theory. In Section 1.1 the notion of polyhedral spline is introduced and a brief survey of known results is given. Section 1.2 gives an introduction to the topics of interpolation of scattered data, Bernstein-B\'ezier representation over triangular partitions and to geometric continuity. In Section 1.3 we are concerned with the topic of shape preserving approximation.

In Chapters 2-6 we are dealing with multivariate simplex splines. In particular, we establish the notion of multivariate divided difference and a relation with multivariate simplex splines, which is reminiscent of a well known relation between B-splines and univariate divided differences (Chapters 2 and 3). In Chapter 4 we derive certain recurrence relations for simplex splines and study some related topics. In Chapter 5 we introduce the notion of discrete simplex spline and propose a subdivision scheme for the evaluation of simplex splines. Similar questions are studied in connection with Bernstein polynomials in Chapter 6.

In Chapter 7, written jointly with Dr. P. R. Pfluger from the University of Amsterdam, we study the problem of interpolation of data scattered in the three dimensional Euclidean space. We employ the Bernstein-B\'ezier representation for polynomials over triangles. We propose a method for constructing a piecewise polynomial interpolation which is local \ie such that the interpolant is only affected locally by changes in the data. We prove that the locality of the interpolant gives rise to degenerate polynomial patches i.e., patches with coalescent control points.

In Chapters 8 and 9 we study a number of problems of shape preserving approximation. First, in Chapter 8, we derive some theoretical results concerning convexity preserving preserving approximation and interpolation. These results are of a negative character. In particular, it is shown that approximation based both on interpolation and local operators cannot be convexity preserving, provided the approximation space is (locally) finite dimensional. Some consequences for the construction of shape preserving approximants are discussed. One of them is that piecewise polynomial functions on fixed partitions of the domain in question are not suitable for the purpose of convexity preserving approximation. In Chapter 9, written jointly with Dr. B. Mulansky from the Technical University of Dresden, we consider the problem of the existence of shape preserving interpolation operators in general linear topological spaces.

Abstract: Some alternatives to the ``classical'' subdivision of Bernstein polynomials (i.e., based on utilizing the well-known de Casteljau algorithm), are sketched. Our schemes have ``asymptotically'' lower computational complexities and can be carried out such that the resulting ``control points'' take the precise values of the polynomial surface being subdivided. For one particular approach, the so called discrete Bernstein basis polynomials are introduced.

Abstract: Some new results on multivariate simplex B-splines and their practical application are presented. New recurrence relations are derived based on [2] and [15]. Remarks on boundary conditions are given and an example of an application of bivariate quadratic simplex splines is presented. The application concerns the approximation of a surface which is constrained by a differential equation.

Abstract: The problem of interpolating discrete data in R^3 is considered. The data consists of positional values and normal vectors. The objective is to interpolate this data by a geometrically smooth (GC^1) surface. This is acomplished by exploiting the so called degenerate triangular polynomial patches, which admit a ``completely local'' interpolation scheme.

Abstract: This paper is a continuation of the first part of our paper on multivariate divided differences. In this paper more properties of the divided differences are derived and the connection with multivariate simplex splines is further investigated.

Abstract: Discrete Bernstein polynomials over simplices are introduced. A number of basic properties, analogous to the properties of continuous Bernstein polynomials are established, such as degree elevation, de Casteljau algorithm, and others.

Abstract: We give a definition of the multivariate divided difference functional which is consistent with the corresponding univariate notion. It is based on the pointwise evaluation of a certain multivariate function. We also show its close relation to the multivariate (simplex) B-splines. Some remarks on the B-spline evaluation are made.

Abstract: We are concerned with methods for computing with multivariate simplex splines. The motivation came from a paper by Cohen, Lyche, and Riesenfeld, where a new recurrence relation for multivariate simplex splines has been derived. Extensions of the ideas in that paper yield new recurrence relations for directional derivatives and inner products of simplex splines. We discuss algorithmical and numerical properties of the new relations and give a comparison with other methods established earlier in the literature.

Abstract: This paper is concerned with the evaluation of multivariate B-splines in a stable and efficient way for arbitrary spatial dimension and arbitrary degree. An algorithm for evaluating B-splines is discussed using both the basic recurrence relations for B-splines and their derivatives and the simplex method for obtaining nonnegative barycentric coordinates. Some numerical experiments are included.