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
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.
$\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.
Computational Mathematics and Mathematical Physics, 2018, 58:7, 1040–1048
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
\paper Method for constructing optimal dark coverings
\jour Zh. Vychisl. Mat. Mat. Fiz.
\jour Comput. Math. Math. Phys.
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|