A space quantization method for numerical integration

Title	A space quantization method for numerical integration
Publication Type	Journal Article
Year of Publication	1998
Authors	Gilles Pagès
Journal	J. Comput. Appl. Math.
Volume	89
Pagination	1–38
ISSN	0377-0427
Keywords	competitive 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.