On the formalization of tasks searching dense submatrices in boolean sparse matrice

In a significant part of data mining applications such as microbiology, gene expression data, text and web information, market baskets, customer environments, input information is represented as a two-dimensional matrix “subjects–objects” (“clients–services”). The main goal of such problems is biclustering of data, based on the selection of groups in a certain sense of similar rows and columns. A lot of such problems is characterized by strong sparseness of the corresponding matrices. An important aspect of biclustering is the search in some sense of dense submatrices in boolean matrices, which is the main purpose of this research. The author formalizes subject area within the framework of algebraic approach, describes the systems of universal and local constraints, proposes and proves the corresponding criteria for solvability of the problems under consideration.