Covering of high-dimensional cubes and quantization

DOI10.1007/S43069-020-0015-8MaRDI QIDQ2225655zbMATH OpenOpenAlexFDO

Authors A. Zhigljavsky, Jack Noonan

Publication date 8 February 2021

Published in SN Operations Research Forum (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

computer experimentsfacility locationquantizationcoveringhigh dimensionspace-filling

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Numerical methods for mathematical programming, optimization and variational techniques (65K99) Acceleration of convergence in numerical analysis (65B99)

Abstract: As the main problem, we consider covering of a $d$-dimensional cube by $n$ balls with reasonably large $d$ (10 or more) and reasonably small $n$, like $n=100$ or $n=1000$. We do not require the full coverage but only 90% or 95% coverage. We establish that efficient covering schemes have several important properties which are not seen in small dimensions and in asymptotical considerations, for very large $n$. One of these properties can be termed `do not try to cover the vertices' as the vertices of the cube and their close neighbourhoods are very hard to cover and for large $d$ there are far too many of them. We clearly demonstrate that, contrary to a common belief, placing balls at points which form a low-discrepancy sequence in the cube, makes for a very inefficient covering scheme. For a family of random coverings, we are able to provide very accurate approximations to the coverage probability. We then extend our results to the problems of coverage of a cube by smaller cubes and quantization, the latter being also referred to as facility location. Along with theoretical considerations and derivation of approximations, we discuss results of a large-scale numerical investigation.

Recommendations

• Efficient quantisation and weak covering of high dimensional cubes
• Covering of space by random sets
• scientific article; zbMATH DE number 2065240
• On the coverage of k-dimensional space by k-dimensional spheres
• Covering a unit hypercube with hypercubes.

Cites work

• scientific article; zbMATH DE number 3976091 (Why is no real title available?)
• scientific article; zbMATH DE number 50672 (Why is no real title available?)
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 3504209 (Why is no real title available?)
• scientific article; zbMATH DE number 480248 (Why is no real title available?)
• scientific article; zbMATH DE number 741240 (Why is no real title available?)
• Constructing Sobol Sequences with Better Two-Dimensional Projections
• Design of computer experiments: space filling and beyond
• Foundations of Data Science
• Minimax models in the theory of numerical methods. Transl. from the 1989 Russian orig. by Olga Chuyan
• On the worst-case optimal multi-objective global optimization
• On-line covering a cube by a sequence of cubes
• On-line covering the unit cube by cubes
• Random coverings in several dimensions

Cited in

(7)

• Covering of space by random sets
• Non-lattice Covering and Quantization of High Dimensional Sets
• Incremental space-filling design based on coverings and spacings: improving upon low discrepancy sequences
• Maximizing cover probability by using multivariate normal distributions
• A new partition method for DIRECT-type algorithm based on minimax design
• Improving exploration strategies in large dimensions and rate of convergence of global random search algorithms
• Efficient quantisation and weak covering of high dimensional cubes

Describes a project that uses

Uses Software

• sobol.cc

This page was built for publication: Covering of high-dimensional cubes and quantization

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