Algorithms for Boolean Matrix Factorization using Integer Programming

• URL: http://arxiv.org/abs/2305.10185v1
• Date: Wed, 17 May 2023 13:09:23 GMT
• Title: Algorithms for Boolean Matrix Factorization using Integer Programming
• Authors: Christos Kolomvakis, Arnaud Vandaele, Nicolas Gillis
• Abstract summary: We propose an alternating optimization (AO) strategy that solves the subproblem in one factor matrix in BMF. We show how several solutions of BMF can be combined optimally using another IP. Experiments show that our algorithms outperform the state of the art on medium-scale problems.
• Score: 20.13379783488932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Boolean matrix factorization (BMF) approximates a given binary input matrix as the product of two smaller binary factors. As opposed to binary matrix factorization which uses standard arithmetic, BMF uses the Boolean OR and Boolean AND operations to perform matrix products, which leads to lower reconstruction errors. BMF is an NP-hard problem. In this paper, we first propose an alternating optimization (AO) strategy that solves the subproblem in one factor matrix in BMF using an integer program (IP). We also provide two ways to initialize the factors within AO. Then, we show how several solutions of BMF can be combined optimally using another IP. This allows us to come up with a new algorithm: it generates several solutions using AO and then combines them in an optimal way. Experiments show that our algorithms (available on gitlab) outperform the state of the art on medium-scale problems.

Related papers

• Randomized Algorithms for Symmetric Nonnegative Matrix Factorization [2.1753766244387402]
  Symmetric Nonnegative Matrix Factorization (SymNMF) is a technique in data analysis and machine learning. We develop two randomized algorithms for its computation. We show that our methods approximately maintain solution quality and achieve significant speed ups for both large dense and large sparse problems.
  arXiv  Detail & Related papers  (2024-02-13T00:02:05Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Boolean and $\mathbb{F}_p$-Matrix Factorization: From Theory to Practice [3.658952625899939]
  We develop new algorithms for $mathbbF_p$-Matrix Factorization. EPTAS for BMF is a purely theoretical advance. We also use this strategy to develop new algorithms for related $mathbbF_p$-Matrix Factorization.
  arXiv  Detail & Related papers  (2022-07-25T06:05:12Z)
• Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
  We propose two more efficient variants to compute the differentiable matrix square root and the inverse square root. For the forward propagation, one method is to use Matrix Taylor Polynomial (MTP), and the other method is to use Matrix Pad'e Approximants (MPA) A series of numerical tests show that both methods yield considerable speed-up compared with the SVD or the NS iteration.
  arXiv  Detail & Related papers  (2022-01-29T10:00:35Z)
• Binary Matrix Factorisation and Completion via Integer Programming [3.4376560669160394]
  We present a compact and two exponential size integer programs (IPs) for the rank-k binary matrix factorisation problem (k-BMF) We show that the compact IP has a weak LP relaxation, while the exponential size LPs have a stronger equivalent LP relaxation.
  arXiv  Detail & Related papers  (2021-06-25T05:17:51Z)
• Boolean Matrix Factorization with SAT and MaxSAT [6.85316573653194]
  We show that our approaches allow a better factorization than existing approaches while keeping reasonable times. Our methods also allow the handling of incomplete matrices with missing entries.
  arXiv  Detail & Related papers  (2021-06-18T12:57:46Z)
• Boolean Matrix Factorization via Nonnegative Auxiliary Optimization [0.5459797813771498]
  Instead of solving the BMF problem directly, this approach solves a nonnegative optimization problem with the constraint over an auxiliary matrix. We provide the proofs for the equivalencies of the two solution spaces under the existence of an exact solution. Experiments on synthetic and real datasets are conducted to show the effectiveness and complexity of the algorithm.
  arXiv  Detail & Related papers  (2021-06-08T21:55:49Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Self-supervised Symmetric Nonnegative Matrix Factorization [82.59905231819685]
  Symmetric nonnegative factor matrix (SNMF) has demonstrated to be a powerful method for data clustering. Inspired by ensemble clustering that aims to seek better clustering results, we propose self-supervised SNMF (S$3$NMF) We take advantage of the sensitivity to code characteristic of SNMF, without relying on any additional information.
  arXiv  Detail & Related papers  (2021-03-02T12:47:40Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm. We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
  arXiv  Detail & Related papers  (2021-01-19T04:24:23Z)
• Positive Semidefinite Matrix Factorization: A Connection with Phase Retrieval and Affine Rank Minimization [71.57324258813674]
  We show that PSDMF algorithms can be designed based on phase retrieval (PR) and affine rank minimization (ARM) algorithms. Motivated by this idea, we introduce a new family of PSDMF algorithms based on iterative hard thresholding (IHT)
  arXiv  Detail & Related papers  (2020-07-24T06:10:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.