Optimal triangular decompositions of matrices with entries from residuated lattices (Q962936): Difference between revisions

Let \(I\) be an \(n \times m\) object-attribute matrix whose entries \(I_{ij}\) are elements from a residuated lattice \(L=\langle L, \otimes ,\rightarrow , \wedge ,\vee , 0, 1\rangle\). The author searches for a decomposition \(I=A\triangleleft B\) of the matrix \(I\) into a so-called triangular product \(A\triangleleft B\) of an \(n\times k\) object-factor matrix \(A\) and a \(k\times m\) factor-attribute matrix \(B\) with entries \(A_{il},B_{lj}\in L\), such that the number \(k\) of factors is the smallest possible. The composition operator is well-known in fuzzy set theory and is defined by \((A\triangleleft B)_{ij}=\bigwedge _{l=1}^{k} A_{il}\rightarrow B_{lj}\), where \(\bigwedge \) denotes the infimum in \(L\). The entries of \(I, A\) and \(B\) represent grades to which objects have attributes, factors apply to objects, and attributes are particular manifestations of factors, respectively. Thus the decomposition provides a model for factor analysis of graded data. Theorem 1 of the paper says that the following are equivalent: (a) \(I=A\triangleleft B\) for \(n \times k\) and \(k \times m\) matrices \(A\) and \(B\), (b) \(I\) is a \(\wedge\)-superposition of \(k\) \(I\)-beam matrices \(J_1,\dots ,J_k\), i.e. \(J=J_1\wedge \dots \wedge J_k\). It is proved that optimal decompositions, i.e. those with the smallest number of factors, can be attained by using fixpoints of the isotone Galois connection associated with the input matrix. These fixpoints are known as formal concepts in formal concept analysis and can be computed by existing algorithms. Another important topic of the paper is the description of transformations between the \(m\)-dimensional space of original attributes and the \(k\)-dimensional space of factors. Moreover, there are some illustrative examples and remarks on the problem of computing the optimal decomposition. Though the results are presented for matrices, i.e. for relations between finite sets in terms of relations, it should be noted that the arguments behind are also valid for relations between infinite sets.