Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Zh. Vychisl. Mat. Mat. Fiz.: Year: Volume: Issue: Page: Find

 Zh. Vychisl. Mat. Mat. Fiz., 2018, Volume 58, Number 7, Pages 1089–1097 (Mi zvmmf10746)

Method for constructing optimal dark coverings

G. K. Kamenev

Dorodnicyn Computing Center, Federal Research Center “Computer Science and Control”, Russian Academy of Sciences, Moscow, Russia

Abstract: The problem of constructing metric $\varepsilon$-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 $\varepsilon$-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 $\varepsilon$-entropy, which means that they are optimal. Techniques for estimating the reliability and completeness of constructed $(\varepsilon, \delta)$-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.

Key words: $\varepsilon$-nets, Shannon $(\varepsilon, \delta)$-net, $\varepsilon$-entropy, $\varepsilon$-capacity, fractal dimension, coverings, approximation, deep holes method, global optimization, local optimization, pure global search, random multistart, mathematical modeling, support of a random variable.

 Funding Agency Grant Number Russian Foundation for Basic Research 18-01-00465_à

DOI: https://doi.org/10.31857/S004446690000330-4

References: PDF file   HTML file

English version:
Computational Mathematics and Mathematical Physics, 2018, 58:7, 1040–1048

Bibliographic databases:

UDC: 519.977
Revised: 26.12.2017

Citation: G. K. Kamenev, “Method for constructing optimal dark coverings”, Zh. Vychisl. Mat. Mat. Fiz., 58:7 (2018), 1089–1097; Comput. Math. Math. Phys., 58:7 (2018), 1040–1048

Citation in format AMSBIB
\Bibitem{Kam18} \by G.~K.~Kamenev \paper Method for constructing optimal dark coverings \jour Zh. Vychisl. Mat. Mat. Fiz. \yr 2018 \vol 58 \issue 7 \pages 1089--1097 \mathnet{http://mi.mathnet.ru/zvmmf10746} \crossref{https://doi.org/10.31857/S004446690000330-4} \elib{https://elibrary.ru/item.asp?id=35723863} \transl \jour Comput. Math. Math. Phys. \yr 2018 \vol 58 \issue 7 \pages 1040--1048 \crossref{https://doi.org/10.1134/S0965542518070084} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000442613300004} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85052198569}