Leírás
Low-rank matrix approximation is a minimisation problem, in which the objective function measures the discrepancy between a given matrix and its approximating matrix, subject to the constraint that the approximating matrix has reduced rank. Low-rank approximation methods for matrices over the real numbers have been studied extensively, but there is a lack of algorithms designed to obtain optimal low-rank approximations for Boolean matrices.
We generalise the problem of obtaining an optimal rank-k approximation for a given n\times m matrix over the real field to the Boolean semiring by the aid of some fundamental concepts from Boolean linear algebra, such as the Boolean factor rank. We illustrate that the problem obtained is NP-hard using the one-to-one correspondence between the Boolean factor rank of Boolean matrices and the biclique cover number of bipartite graphs, which is a result due to Orlin, 1977.
We introduce two novel integer programming models for optimal low-rank Boolean matrix approximation. One of these relies on a trick of using McCormick envelopes and can be regarded as a completely new approach to obtain low-rank Boolean matrix approximates. We explore this model computationally via Cplex. The formulation of our other model is not completely novel, but a Benders-decomposition inspired methodology that we developed for its solution, resembles no other methods available. This methodology relies on a Lagrangian relaxation based branch and bound algorithm, and allows for very efficient parallelisation.
Joint work with Prof Raphael Hauser and Dr Oktay Gunluk.