| 总结: | <p>For a binary matrix <strong>X</strong>, the Boolean rank <em><strong>br</em></strong>(<strong>X</strong>) is the smallest integer for which <strong>X</strong> can be factorised into the Boolean matrix product of two binary matrices <strong>A</strong> and <strong>B</strong> with inner dimension <em><strong>br</em></strong>(<strong>X</strong>). The isolation number <em><strong>i</em></strong>(<strong>X</strong>) of <strong>X</strong> is the maximum number of 1s no two of which are in a same row, column or a 2 x 2 submatrix of all 1s.</p>
<br>
<p>In Part I. of this thesis, we continue Anna Lubiw's study of firm matrices. <strong>X</strong> is said to be firm if <em><strong>i</em></strong>(<strong>X</strong>)=<em><strong>br</em></strong>(<strong>X</strong>) and this equality holds for all its submatrices. We show that the stronger concept of superfirmness of <strong>X</strong> is equivalent to having no odd holes in the rectangle cover graph of <strong>X</strong>, the graph in which <em><strong>br</em></strong>(<strong>X</strong>) and <em><strong>i</em></strong>(<strong>X</strong>) translate to the clique cover number and the independence number, respectively. A binary matrix is minimally non-firm if it is not firm but all of its proper submatrices are. We introduce a matrix operation that leads to generalised binary matrices and, under some conditions, preserves firmness and superfirmness. Then we use this matrix operation to derive several infinite families of minimally non-firm matrices. To the best of our knowledge, minimally non-firm matrices have not been studied before and our constructions provide the first infinite families of them.</p>
<br>
<p>In Part II. of this thesis, we explore rank-<em>k</em> binary matrix factorisation (<em>k</em>-BMF). In <em>k</em>-BMF, we are given an <em>m</em> x <em>n</em> binary matrix <strong>X</strong> with possibly missing entries and need to find two binary matrices <strong>A</strong> and <strong>B</strong> of dimension <em>m</em> x <em>k</em> and <em>k</em> x <em>n</em> respectively, which minimise the distance between <strong>X</strong> and the Boolean matrix product of <strong>A</strong> and <strong>B</strong> in the squared Frobenius norm. We present a compact and two exponential size integer programs (IPs) for <em>k</em>-BMF and show that the compact IP has a weak LP relaxation, while the exponential size IPs have a stronger equivalent LP relaxation. We introduce a new objective function, which differs from the traditional squared Frobenius objective in attributing a weight to zero entries of the input matrix that is proportional to the number of times a zero is erroneously covered in a rank-<em>k</em> factorisation. For one of the exponential size IPs we describe a computational approach based on column generation. Experimental results on synthetic and real word datasets suggest that our integer programming approach is competitive against available methods for <em>k</em>-BMF and provides accurate low-error factorisations.</p>
|
|---|