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.
Keywordscompetitive algorithms, error estimation, learning algorithms, numerical integration, numerical methods, optimization method, vector quantization, Voronoi diagram

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.