On an invariant for the problem of underdetermined data decomposing

L. A. Sholomov

Prikladnaâ diskretnaâ matematika, no. 1 (2018), pp. 13-32.

Résumé

The subject of this article is the problem of the best decomposing an arbitrary underdetermined source into a product of underdetermined binary sources. Let $A_0=\{a_i\colon i\in M\}$ be a finite alphabet of basic symbols, $\mathcal T\subseteq 2^M$, and $A=\{a_T\colon T\in\mathcal T\}$ be an alphabet of underdetermined symbols. Any symbol $a_i$, $i\in T$, is considered to be a specification of the symbol $a_T$. The symbol $a_M$, denoted by $*$, is called indefinite. An underdetermined source $X$ generates symbols $a_T\in A$ independently with probabilities $p_T$. The entropy of the source $X$ is the quantity $$ \mathcal H(X)=\min_Q\left(-\sum_{T\in\mathcal T}p_T\log_2\sum_{i\in T}q_i\right) $$ where the minimum is taken over the set of probability vectors $Q=(q_i,\ i\in M)$. Underdetermined sources $X$ and $Y$ are equivalent ($X\eqsim Y$) if $\mathcal H(XZ)=\mathcal H(YZ)$ for any source $Z$. The source $X$ is not weaker than $Y$ ($X\succsim Y$) if $XY\eqsim X$. For the underdetermined source $X$ and a natural $s$, we assign to each $T\in\mathcal T$ some vector $\lambda_T\in\{0,1,*\}^s$. If the component $i$ $(i=1,\dots,s)$ of the vector is considered as the output value of some source $X_i$, then the product $X_1\dots X_s$ of underdetermined binary sources arises. It's called decomposition associated with the source $X$. The decomposition $X_1\dots X_s$ is considered to be exact if $X_1\dots X_s\eqsim X$. The decomposition is called (lower) approximation of the source $X$ if $X_1\dots X_s\precsim X$ and, for any connected with $X$ decomposition $Z_1\dots Z_t$ such that $Z_1\dots Z_t\precsim X$, the relation $X_1\dots X_s\succsim Z_1\dots Z_t$ 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 $X_1\dots X_s$ is represented by a matrix $\Lambda$ consisting of the columns $\lambda_T$, $T\in\mathcal T$. For the matrix $\Lambda$, we construct a graph $G_\chi(\Lambda)$ with the set of vertices $\mathcal T$. The graph is called the characteristic graph of $\Lambda$. In it, the vertices $T$ and $T'$ are connected by the edge $(T,T')$ if and only if the vectors $\lambda_T$ and $\lambda_{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_\chi^\mathrm{app}(X)$ is also defined. The graph $G_\chi^\mathrm{app}(X)$ is formed by all edges $(T,T')$ such that $T\cap T'=\varnothing$. 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_\chi$ with complete bipartite subgraphs. In particular, the approximate decompositions of the least complexity correspond to minimal coverings of $G_\chi^\mathrm{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.

Détail

Keywords: underdetermined source, approximation, characteristic graph of approximation, NP-completeness.
Mots-clés : decomposition, invariant of equivalent transformations, biclique

Bibliographie

[1] Sholomov L. A., “On the concept of underdetermined alphabets of equal strength”, Prikladnaya Diskretnaya Matematika, 2014, no. 3(25), 40–57 (in Russian)

[2] Sholomov L. A., “Decomposition of underdetermined data”, J. Appl. Industr. Math., 7:1 (2013), 100–116 | DOI | MR

[3] Gallager R. G., Information Theory and Reliable Communication, Wiley, New York, 1968, 608 pp.

[4] Sholomov L. A., “Elements of the underdetermined information theory”, Prikladnaya Diskretnaya Matematika. Prilozhenie, 2009, no. 2, 18–42 (in Russian)

[5] Potapov V. N., Introduction to Information Theory, RHD, Izhevsk, 2014, 152 pp. (in Russian)

[6] Sholomov L. A., “Transformations of fuzzy data preserving information properties”, Diskretniy Analiz i Issledovanie Operatsiy, Ser. 1, 12:3 (2005), 85–104 (in Russian) | MR | Zbl

[7] Sholomov L. A., “On the reducibility of alfabets for problems of underdetermined data coding”, Doklady Mathematics, 91:1 (2015), 117–120 | DOI | DOI | MR

[8] Harary F., Graph Theory, Addison-Wesley, London, 1969, 274 pp. | MR | MR

[9] Orlin J., “Contentment in graph theory: Coverings graphs with cliques”, Nederlandce Akademie Wetenschappen Proc. Ser. A 80. Indiagationes Mathematcae, 39:5 (1977), 406–424 | MR

[10] Muller J., “On edge perfectness and classes of bipartite graphs”, Discrete Mathematics, 149:1–3 (1996), 159–187 | DOI | MR

[11] Flischner H, Majuni E, Paulusma D., Szeider S., “Covering graphs with few complete bipartite subgraphs”, Theor. Computer Sci., 410 (2009), 2045–2053 | DOI | MR

[12] Chegis I. A., Yablonski S. V., “Logic methods for the electrical networks testing”, Trudy MIAN im. V. A. Steklova, 51, 1958, 270–360 (in Russian) | MR | Zbl

[13] Nigmatullin R. G., A Complexity of Boolean Functions, Nauka, Moscow, 1991, 240 pp. (in Russian) | MR