Optimal approximation and quantisation (Q854015): Difference between revisions

The quantisation problem for probability measures aims to represent a measure \(\mu\) in \(\mathbb{R}^d\) using a finite set of points \(X = \{ x_1, \dots, x_n\}\) by minimising an objective function of the following type \[ F(X) = \int_{\mathbb{R}^d} \rho^r(y,X) \mu(dy), \] where \(\rho(y,X)\) is the distance from \(y \in \mathbb{R}^d\) to the nearest point from \(X\). The authors aim to elaborate a unified approach both to quantisation and approximation problems by considering general integral functionals of the type \[ I(K; X) = \int_K \eta(y,X) \,dy \] where \(K\) is a measurable subset of \(\mathbb{R}^d\) and \(\eta(y,X)\) is a measurable with respect to \(y\), translation-invariant and homogeneous of order \(r>0\) functional. The functional \(\eta\) depends on \(y\) and \(X \cap C(y,X)\), where \(C(y,X)\) is a certain set associated with the point \(y\) and a finite set \(X\). It is assumed that \(C(y,X)\) is translation-invariant and satisfies some separation and uniform boundedness conditions. The authors show that the minumum of \(n^{r/d} I(K; X)\) over all \(X\) with cardinality \(n\) has limit \(\mathcal{I}\) as \(n \to \infty\). The asymptotic quantisation errors can be then used to design the asymptotically optimal quantisers. The authors consider also the functional \[ E(h; X) = \int_{\mathbb{R}^d} h(\varphi(y,X) ) \eta(y,X) \,dy, \] where \(h\) is a certain function and \(\varphi(y,X)\) is a point in \(\mathbb{R}^d\) such that \(y \in C(y,X)\). Then they prove that the limit of the infimum of \(n^{r/d} E(h;X)\) over all sets \(X\) with cardinality at most \(n\) converges to the \(L_{d/(d+r)}\)-norm of \(h\) up to a constant that does not depend on \(h\) or \(\varphi\). In the last part of the article the authors show how to apply the results described above to the problem of function approximation in three cases: splines, tangent planes and triangulated surfaces.