Method for Constructing Optimal Dark Coverings
- Authors: Kamenev G.K.1
-
Affiliations:
- Dorodnicyn Computing Center, Federal Research Center “Computer Science and Control”, Russian Academy of Sciences
- Issue: Vol 58, No 7 (2018)
- Pages: 1040-1048
- Section: Article
- URL: https://journal-vniispk.ru/0965-5425/article/view/179695
- DOI: https://doi.org/10.1134/S0965542518070084
- ID: 179695
Cite item
Abstract
The problem of constructing metric ε-nets and corresponding coverings by balls for compact sets with a probability measure is considered. In the case of sets having metrically significant parts with a small measure (dark sets), methods for constructing ε-nets are combined with the deep holes method in a unified approach. According to this approach, a constructed metric net is supplemented with its deep hole (the most distant element of the set) until the required accuracy is achieved. An existing implementation of the method for a metric set with a given probability measure is based on a pure global search for deep holes. To construct dark coverings, the method is implemented on the basis of a random multistart. For the resulting nets, the logarithm of the number of their elements is shown to be close to ε-entropy, which means that they are optimal. Techniques for estimating the reliability and completeness of constructed (ε, δ)-coverings in the sense of C.E. Shannon are described. The methods under consideration can be used to construct coverings of implicitly given sets with a measure defined on the preimage and to recover compact supports of multidimensional random variables with an unknown distribution law.
About the authors
G. K. Kamenev
Dorodnicyn Computing Center, Federal Research Center “Computer Science and Control”,Russian Academy of Sciences
Author for correspondence.
Email: gkk@ccas.ru
Russian Federation, Moscow, 119333
Supplementary files
