Binary Matrix Factorisation and Completion via Integer Programming

• URL: http://arxiv.org/abs/2106.13434v1
• Date: Fri, 25 Jun 2021 05:17:51 GMT
• Title: Binary Matrix Factorisation and Completion via Integer Programming
• Authors: Reka A. Kovacs, Oktay Gunluk, Raphael A. Hauser
• Abstract summary: 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.
• Score: 3.4376560669160394
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Binary matrix factorisation is an essential tool for identifying discrete patterns in binary data. In this paper we consider the rank-k binary matrix factorisation problem (k-BMF) under Boolean arithmetic: we are given an n x m binary matrix X with possibly missing entries and need to find two binary matrices A and B of dimension n x k and k x m respectively, which minimise the distance between X and the Boolean product of A and B in the squared Frobenius distance. We present a compact and two exponential size integer programs (IPs) for k-BMF and show that the compact IP has a weak LP relaxation, while the exponential size LPs 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 the zero is erroneously covered in a rank-k 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 k-BMF and provides accurate low-error factorisations.

Related papers

• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  We derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues. We validate our theory with an empirical study of a collection of synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2024-05-23T12:26:25Z)
• Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares [0.8702432681310401]
  We propose a new algorithm for recovering data that adheres to multiple, heterogeneous low-dimensional structures from linear observations. We show that the IRLS method favorable in identifying low/comckuele state measurements.
  arXiv  Detail & Related papers  (2023-06-08T06:35:47Z)
• Algorithms for Boolean Matrix Factorization using Integer Programming [20.13379783488932]
  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.
  arXiv  Detail & Related papers  (2023-05-17T13:09:23Z)
• 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)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• 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)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• 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)
• 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)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Binary Matrix Factorisation via Column Generation [6.445605125467574]
  We consider the problem of low-rank binary matrix factorisation (BMF) under arithmetic. We formulate the problem as a mixed integer linear program and use a large scale optimisation technique of column generation to solve it. Experimental results on real world datasets demonstrate that our proposed method is effective at producing highly accurate factorisations.
  arXiv  Detail & Related papers  (2020-11-09T14:27:36Z)

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.