Nonlinear approximation using Gaussian kernels

It is well known that nonlinear approximation has an advantage over linear schemes in the sense that it provides comparable approximation rates to those of the linear schemes, but to a larger class of approximands. This was established for spline approximations and for wavelet approximations, and more recently by DeVore and Ron (in press) [2] for homogeneous radial basis function (surface spline) approximations. However, no such results are known for the Gaussian function, the preferred kernel in machine learning and several engineering problems. We introduce and analyze in this paper a new algorithm for approximating functions using translates of Gaussian functions with varying tension parameters. At heart it employs the strategy for nonlinear approximation of DeVore-Ron, but it selects kernels by a method that is not straightforward. The crux of the difficulty lies in the necessity to vary the tension parameter in the Gaussian function spatially according to local information about the approximand: error analysis of Gaussian approximation schemes with varying tension are, by and large, an elusive target for approximators. We show that our algorithm is suitably optimal in the sense that it provides approximation rates similar to other established nonlinear methodologies like spline and wavelet approximations. As expected and desired, the approximation rates can be as high as needed and are essentially saturated only by the smoothness of the approximand.     

On approximate approximations using Gaussian kernels

This paper discusses quasi-interpolation and interpolation withGaussians. Estimates are obtained showing a high-order approximationup to some saturation error negligible in numerical applications.The construction of local high-order quasi-interpolation formulasis given. Supported in part by the International Centre for MathematicalSciences, Edinburgh.     

Gaussian kernels have only Gaussian maximizers

A Gaussian integral kernelG(x, y) onR ⁿ ×R ⁿ is the exponential of a quadratic form inx andy; the Fourier transform kernel is an example. The problem addressed here is to find the sharp bound ofG as an operator fromL ^p (R ⁿ ) toL ^p (R ⁿ ) and to prove that theL ^p (R ⁿ ) functions that saturate the bound are necessarily Gaussians. This is accomplished generally for 1<pq< and also forp>q in some special cases. Besides greatly extending previous results in this area, the proof technique is also essentially different from earlier ones. A corollary of these results is a fully multidimensional, multilinear generalization of Young's inequality.Oblatum 19-XII-1989Work partially supported by U.S. National Science Foundation grant PHY-85-15288-A03     

Positivity improvement and Gaussian kernels

We show that a positivity improving property of multilinear operators with Gaussian kernels can be determined, with sharp constants, by testing Gaussian functions only. This result can be considered as a reversed form of Lieb's theorem on maximizers of Gaussian kernels.     

Dimension dependent hypercontractivity for Gaussian kernels

We derive sharp, local and dimension dependent hypercontractive bounds on the Markov kernel of a large class of diffusion semigroups. Unlike the dimension free ones, they capture refined properties of Markov kernels, such as trace estimates. They imply classical bounds on the Ornstein?CUhlenbeck semigroup and a dimensional and refined (transportation) Talagrand inequality when applied to the Hamilton?CJacobi equation. Hypercontractive bounds on the Ornstein?CUhlenbeck semigroup driven by a non-diffusive Lévy semigroup are also investigated. Curvature-dimension criteria are the main tool in the analysis.     

Gaussian limit for determinantal point processes with J-Hermitian kernels

We show that the central limit theorem for linear statistics over determinantal point processes with J-Hermitian kernels holds under fairly general conditions. In particular, we establish the Gaussian limit for linear statistics over determinantal point processes on the union of two copies of Rdwhen the correlation kernels are J-Hermitian translation-invariant.     

Gauss-Hermite quadratures for functions from Hilbert spaces with Gaussian reproducing kernels

We study univariate integration with the Gaussian weight for a positive variance α. This is done for the reproducing kernel Hilbert space with the Gaussian kernel for a positive shape parameter γ. We study Gauss-Hermite quadratures, although this choice of quadratures may be questionable since polynomials do not belong to this space of functions. Nevertheless, we provide the explicit formula for the error of the Gauss-Hermite quadrature using n function values. In particular, for 2αγ ²<1 we have an exponential rate of convergence, and for 2αγ ²=1 we have no convergence, whereas for 2αγ ²>1 we have an exponential divergence.     

Error estimates for approximate approximations with Gaussian kernels on compact intervals

The aim of this paper is the investigation of the error which results from the method of approximate approximations applied to functions defined on compact intervals, only. This method, which is based on an approximate partition of unity, was introduced by Maz’ya in 1991 and has mainly been used for functions defined on the whole space up to now. For the treatment of differential equations and boundary integral equations, however, an efficient approximation procedure on compact intervals is needed.In the present paper we apply the method of approximate approximations to functions which are defined on compact intervals. In contrast to the whole space case here a truncation error has to be controlled in addition. For the resulting total error pointwise estimates and L₁-estimates are given, where all the constants are determined explicitly.     

Global errors for approximate approximations with Gaussian kernels on compact intervals

This paper investigates the global errors which result when the method of approximate approximations is applied to a function defined on a compact interval. By extending the functions to a wider interval, we are able to introduce modified forms of the quasi-interpolant operators. Using these operators as approximation tools, we estimate upper bounds on the errors in terms of a uniform norm. We consider only continuous and differentiable functions. A similar problem is solved for the two-dimensional case.     

Cover-based bounds on the numerical rank of Gaussian kernels

A popular approach for analyzing high-dimensional datasets is to perform dimensionality reduction by applying non-parametric affinity kernels. Usually, it is assumed that the represented affinities are related to an underlying low-dimensional manifold from which the data is sampled. This approach works under the assumption that, due to the low-dimensionality of the underlying manifold, the kernel has a low numerical rank. Essentially, this means that the kernel can be represented by a small set of numerically-significant eigenvalues and their corresponding eigenvectors.We present an upper bound for the numerical rank of Gaussian convolution operators, which are commonly used as kernels by spectral manifold-learning methods. The achieved bound is based on the underlying geometry that is provided by the manifold from which the dataset is assumed to be sampled. The bound can be used to determine the number of significant eigenvalues/eigenvectors that are needed for spectral analysis purposes. Furthermore, the results in this paper provide a relation between the underlying geometry of the manifold (or dataset) and the numerical rank of its Gaussian affinities.The term cover-based bound is used because the computations of this bound are done by using a finite set of small constant-volume boxes that cover the underlying manifold (or the dataset). We present bounds for finite Gaussian kernel matrices as well as for the continuous Gaussian convolution operator. We explore and demonstrate the relations between the bounds that are achieved for finite and continuous cases. The cover-oriented methodology is also used to provide a relation between the geodesic length of a curve and the numerical rank of Gaussian kernel of datasets that are sampled from it.     

A universal envelope for Gaussian processes and their kernels

The central theme in our paper deals with mathematical issues involved in the answer to the following question: How can we generate stochastic processes from their correlation data? Since Gaussian processes are determined by moment information up to order two, we focus on the Gaussian case. Two functional analytic tools are used here, in more than one variant. They are: operator factorization; and direct integral decompositions in the form of Karhunen-Loève expansions. We define and study a new interplay between the theory of positive definition functions, and their reproducing kernels, on the one hand, and Gaussian stochastic processes, on the other. The three classes of processes we study are as follows: Processes associated with: (a) arbitrarily given sigma finite regular measures on a fixed Borel measure space; (b) with Hilbert spaces of sigma-functions; and (c) with systems of self-similar measures arising in the theory of iterated function systems. Starting with a non-degenerate positive definite function K on some fixed set S, we show that there is a choice of a universal sample space Ω, which can be realized as a “boundary” of (S,K). Its boundary-theoretic properties are analyzed, and we point out their relevance to the study of electrical networks on countable infinite graphs.     

Gaussian parsimonious clustering models with covariates and a noise component

Advances in Data Analysis and Classification - We consider model-based clustering methods for continuous, correlated data that account for external information available in the presence of...     

On Multiple Singular Integrals along Polynomial Curves with Rough Kernels

This paper is devoted to the study of a class of singular integral operators defined by polynomial mappings on product domains. Some rather weak size conditions, which imply the Lp boundedness of these singular integral operators as well as the corresponding maximal truncated singular integral operators for some fixed 1〈p〈 ∞,are given.     

A closer look at covering number bounds for Gaussian kernels

We establish some new bounds on the log-covering numbers of (anisotropic) Gaussian reproducing kernel Hilbert spaces. Unlike previous results in this direction we focus on small explicit constants and their dependency on crucial parameters such as the kernel bandwidth and the size and dimension of the underlying space.     

Rates of clustering for some Gaussian self-similar processes

Summary The analogue of Strassen's functional law of the iterated logarithm in known for many Gaussian processes which have suitable scaling properties, and here we establish rates at which this convergence takes place. We provide a new proof of the best upper bound for the convergence toK by suitably normalized Brownian motion, and then continue with this method to get similar bounds for the Brownian sheet and other self-similar Gaussian processes. The previous method, which produced these results for Brownian motion in ₁, was highly dependent on many special properties unavailable when dealing with other Gaussian processes.Supported in part by NSF Grant NSF-88-07121Supported in part by NSF Grant DMS-85-21586     

Model selection for Gaussian latent block clustering with the integrated classification likelihood

Block clustering aims to reveal homogeneous block structures in a data table. Among the different approaches of block clustering, we consider here a model-based method: the Gaussian latent block model for continuous data which is an extension of the Gaussian mixture model for one-way clustering. For a given data table, several candidate models are usually examined, which differ for example in the number of clusters. Model selection then becomes a critical issue. To this end, we develop a criterion based on an approximation of the integrated classification likelihood for the Gaussian latent block model, and propose a Bayesian information criterion-like variant following the same pattern. We also propose a non-asymptotic exact criterion, thus circumventing the controversial definition of the asymptotic regime arising from the dual nature of the rows and columns in co-clustering. The experimental results show steady performances of these criteria for medium to large data tables.     

Fuzzy bilevel programming with multiple objectives and cooperative multiple followers

Classic bilevel programming deals with two level hierarchical optimization problems in which the leader attempts to optimize his/her objective, subject to a set of constraints and his/her follower’s solution. In modelling a real-world bilevel decision problem, some uncertain coefficients often appear in the objective functions and/or constraints of the leader and/or the follower. Also, the leader and the follower may have multiple conflicting objectives that should be optimized simultaneously. Furthermore, multiple followers may be involved in a decision problem and work cooperatively according to each of the possible decisions made by the leader, but with different objectives and/or constraints. Following our previous work, this study proposes a set of models to describe such fuzzy multi-objective, multi-follower (cooperative) bilevel programming problems. We then develop an approximation Kth-best algorithm to solve the problems.