Efficient quantisation and weak covering of high dimensional cubes

DOI10.1007/S00454-022-00396-7MaRDI QIDQ2167316zbMATH OpenOpenAlexFDO

Authors Jack Noonan, A. Zhigljavsky

Publication date 25 August 2022

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2005.07938

zbMATH Keywords

computer experimentscoveringfacility locationhigh dimensionquantisationspace-fillingVoronoi set

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Lattice packing and covering (number-theoretic aspects) (11H31) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17)

Abstract: Let $mathbb{Z}_n=Z_1,ldots,Z_n$ be a design; that is, a collection of $n$ points $Z_{j}in[-1,1{]}^d$. We study the quality of quantization of $[-1,1{]}^d$ by the points of $mathbb{Z}_n$ and the problem of quality of coverage of $[-1,1{]}^d$ by ${calB}_d(mathbb{Z}_n,r)$, the union of balls centred at $Z_{j}inmathbb{Z}_n$. We concentrate on the cases where the dimension $d$ is not small ($dgeq5$) and $n$ is not too large, $nleq{2}^d$. We define the design $mathbb{D}_{n,delta}$ as a $2^{d-1}$ design defined on vertices of the cube $[-delta,delta{]}^d$, $0leqdeltaleq1$. For this design, we derive a closed-form expression for the quantization error and very accurate approximations for {the coverage area} vol$([-1,1{]}^{d}cap{calB}_d(mathbb{Z}_n,r))$. We provide results of a large-scale numerical investigation confirming the accuracy of the developed approximations and the efficiency of the designs $mathbb{D}_{n,delta}$.

Recommendations

• Covering of high-dimensional cubes and quantization
• Efficient multivariate approximation on the cube
• Non-lattice Covering and Quantization of High Dimensional Sets
• Sparse approximation over the cube
• Maximal inequality for high-dimensional cubes
• Covering the cube by affine hyperplanes
• Covering cubes and the closest vector problem
• Decomposition and approximation of multivariate functions on the cube
• scientific article; zbMATH DE number 4112541
• Efficient and Practical Implementations of Cubature on Wiener Space

Cites work

• Bayesian and High-Dimensional Global Optimization
• Bayesian quadrature, energy minimization, and space-filling design
• Covering of high-dimensional cubes and quantization
• Design of computer experiments: space filling and beyond
• Foundations of quantization for probability distributions
• scientific article; zbMATH DE number 3504209 (Why is no real title available?)
• scientific article; zbMATH DE number 1224949 (Why is no real title available?)
• scientific article; zbMATH DE number 741240 (Why is no real title available?)
• Kernel techniques: From machine learning to meshless methods
• Latinized improved LHS, and CVT point sets in hypercubes
• Minimax and maximin space-filling designs: some properties and methods for construction
• Non-lattice Covering and Quantization of High Dimensional Sets
• Scattered Data Approximation
• The design and analysis of computer experiments.

Cited in

(3)

• Covering of high-dimensional cubes and quantization
• Non-lattice Covering and Quantization of High Dimensional Sets
• Improving exploration strategies in large dimensions and rate of convergence of global random search algorithms

This page was built for publication: Efficient quantisation and weak covering of high dimensional cubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2167316)