|
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
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:i∈M} be a finite alphabet of basic symbols, T⊆2M, and A={aT:T∈T} be an alphabet of underdetermined symbols. Any symbol ai, i∈T, is considered to be a specification of the symbol aT. The symbol aM, denoted by ∗, is called indefinite. An underdetermined source X generates symbols aT∈A independently with probabilities pT. The entropy of the source X is the quantity
H(X)=minQ(−∑T∈TpTlog2∑i∈Tqi)
where the minimum is taken over the set of probability vectors Q=(qi, i∈M). Underdetermined sources X and Y are equivalent (X≂Y) if H(XZ)=H(YZ) for any source Z. The source X is not weaker than Y (X≿Y) if XY≂X. For the underdetermined source X and a natural s, we assign to each T∈T 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 X1…Xs of underdetermined binary sources arises. It's called decomposition associated with the source X. The decomposition X1…Xs is considered to be exact if X1…Xs≂X. The decomposition is called (lower) approximation of the source X if X1…Xs≾X and, for any connected with X decomposition Z1…Zt such that Z1…Zt≾X, the relation X1…Xs≿Z1…Zt 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 X1…Xs is represented by a matrix Λ consisting of the columns λT, T∈T. 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 Gappχ(X) is also defined. The graph Gappχ(X) is formed by all edges (T,T′) such that T∩T′=∅. 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 Gappχ(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.
Citation:
L. A. Sholomov, “On an invariant for the problem of underdetermined data decomposing”, Prikl. Diskr. Mat., 2018, no. 39, 13–32
Linking options:
https://www.mathnet.ru/eng/pdm616 https://www.mathnet.ru/eng/pdm/y2018/i1/p13
|
Statistics & downloads: |
Abstract page: | 212 | Full-text PDF : | 64 | References: | 37 |
|