Prikladnaya Diskretnaya Matematika
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



Prikl. Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






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


Prikladnaya Diskretnaya Matematika, 2018, Number 39, Pages 13–32
DOI: https://doi.org/10.17223/20710410/39/2
(Mi pdm616)
 

Theoretical Backgrounds of Applied Discrete Mathematics

On an invariant for the problem of underdetermined data decomposing

L. A. Sholomov

Federal Research Center "Computer Science and Control" of RAS, Moscow, Russia
References:
Abstract: The subject of this article is the problem of the best decomposing an arbitrary underdetermined source into a product of underdetermined binary sources. Let A0={ai:iM} be a finite alphabet of basic symbols, T2M, and A={aT:TT} be an alphabet of underdetermined symbols. Any symbol ai, iT, is considered to be a specification of the symbol aT. The symbol aM, denoted by , is called indefinite. An underdetermined source X generates symbols aTA independently with probabilities pT. The entropy of the source X is the quantity
H(X)=minQ(TTpTlog2iTqi)
where the minimum is taken over the set of probability vectors Q=(qi, iM). Underdetermined sources X and Y are equivalent (XY) if H(XZ)=H(YZ) for any source Z. The source X is not weaker than Y (XY) if XYX. For the underdetermined source X and a natural s, we assign to each TT some vector λT{0,1,}s. If the component i (i=1,,s) of the vector is considered as the output value of some source Xi, then the product X1Xs of underdetermined binary sources arises. It's called decomposition associated with the source X. The decomposition X1Xs is considered to be exact if X1XsX. The decomposition is called (lower) approximation of the source X if X1XsX and, for any connected with X decomposition Z1Zt such that Z1ZtX, the relation X1XsZ1Zt is fulfilled. It is known that the exact decomposition of a source may not exist, but there is always an approximation that is unique up to equivalence. If the exact decomposition exists, then the approximation coincides with it. The aim of this paper is to construct approximations of minimal complexity (i.e., with the smallest number of factors).
The decomposition X1Xs is represented by a matrix Λ consisting of the columns λT, TT. For the matrix Λ, we construct a graph Gχ(Λ) with the set of vertices T. The graph is called the characteristic graph of Λ. In it, the vertices T and T are connected by the edge (T,T) if and only if the vectors λT and λT are inconsistent, i.e. do not allow a common specification. It is proved that decompositions are equivalent if and only if the characteristic graphs of their matrices coincide. It means that the characteristic graph is the invariant with respect to equivalent transformations of decompositions and completely determines a equivalence class of the decompositions. For the equivalence class formed by approximations of the given source X, the characteristic graph Gχapp(X) is also defined. The graph Gχapp(X) is formed by all edges (T,T) such that TT=. All decompositions belonging to a given equivalence class are described too. It is proved that there exists a one-to-one correspondence between the decompositions (in some standard form) and coverings of the characteristic graph Gχ with complete bipartite subgraphs. In particular, the approximate decompositions of the least complexity correspond to minimal coverings of Gχapp(X). The construction problem for approximating decompositions with minimal complexity turned out to be NP-complete. The article describes a rather economical way to solve this problem for tasks having not too large dimension.
Keywords: underdetermined source, decomposition, approximation, invariant of equivalent transformations, characteristic graph of approximation, biclique, NP-completeness.
Bibliographic databases:
Document Type: Article
UDC: 519.728
Language: Russian
Citation: L. A. Sholomov, “On an invariant for the problem of underdetermined data decomposing”, Prikl. Diskr. Mat., 2018, no. 39, 13–32
Citation in format AMSBIB
\Bibitem{Sho18}
\by L.~A.~Sholomov
\paper On an invariant for the problem of underdetermined data decomposing
\jour Prikl. Diskr. Mat.
\yr 2018
\issue 39
\pages 13--32
\mathnet{http://mi.mathnet.ru/pdm616}
\crossref{https://doi.org/10.17223/20710410/39/2}
\elib{https://elibrary.ru/item.asp?id=32724372}
Linking options:
  • https://www.mathnet.ru/eng/pdm616
  • https://www.mathnet.ru/eng/pdm/y2018/i1/p13
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Прикладная дискретная математика
    Statistics & downloads:
    Abstract page:212
    Full-text PDF :64
    References:37
     
      Contact us:
    math-net2025_01@mi-ras.ru
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025