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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
Received: 11.05.2017
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{http://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{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85052198569}


Linking options:
  • http://mi.mathnet.ru/eng/zvmmf10746
  • http://mi.mathnet.ru/eng/zvmmf/v58/i7/p1089

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • ∆урнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Number of views:
    This page:50
    References:16

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020