A space quantization method for numerical integration

TitleA space quantization method for numerical integration
Publication TypeJournal Article
Year of Publication1998
AuthorsGilles Pagès
JournalJ. Comput. Appl. Math.
Volume89
Pagination1–38
ISSN0377-0427
Keywordscompetitive algorithms, error estimation, learning algorithms, numerical integration, numerical methods, optimization method, vector quantization, Voronoi diagram
Abstract

We propose a new method (SQM) for numerical integration of $ C^\alpha $ functions ($ \alpha \in (0,2] $) defined on a convex subset $ C $ of $ \mathbb{R}^d $ with respect to a continuous distribution $ \mu $. It relies on a space quantization of $ C $ by a $ n $-tuple = (x_1,\cdots, x_n) \in C^n $. $ \int f d\mu $ is approximated by a weighted sum of the $ f (x_i) $'s. The integration error bound depends on the distortion $ E_n^{z,\mu}(x) $ of the Voronoï tessellation of $ x $. This notion comes from Information Theoretists. Its main properties (existence of a minimizing $ n $-tuple in $ C^n $, asymptotics of $ \min\limits_{C^n} E_n^{\alpha,\mu} $ as $ n \to + \infty $) are presented for a wide class of measures $ \mu $. A simple stochastic optimization procedure is proposed to compute, in any dimension $ d $, $ x^* $ and the characteristics of its Voronoï tessellation. Some new results on the Competitive Learning Vector Quantization algorithm (when $ \alpha = 2 $) are obtained as a by-product. Some tests, simulations and provisional remarks are proposed as a conclusion.