Boolean Matrix Factorization with SAT and MaxSAT

• URL: http://arxiv.org/abs/2106.10105v1
• Date: Fri, 18 Jun 2021 12:57:46 GMT
• Title: Boolean Matrix Factorization with SAT and MaxSAT
• Authors: Florent Avellaneda, Roger Villemaire
• Abstract summary: 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.
• Score: 6.85316573653194
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The Boolean matrix factorization problem consists in approximating a matrix by the Boolean product of two smaller Boolean matrices. To obtain optimal solutions when the matrices to be factorized are small, we propose SAT and MaxSAT encoding; however, when the matrices to be factorized are large, we propose a heuristic based on the search for maximal biclique edge cover. We experimentally demonstrate that our approaches allow a better factorization than existing approaches while keeping reasonable computation times. Our methods also allow the handling of incomplete matrices with missing entries.

Related papers

• Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and Eigenvector Disjunctions [6.537257913467247]
  Low-rank matrix completion consists of a matrix of minimal complexity that recovers a given set of observations as accurately as possible. New convex relaxations decrease the optimal by magnitude compared to existing methods.
  arXiv  Detail & Related papers  (2023-05-20T22:04:34Z)
• Bounding Real Tensor Optimizations via the Numerical Range [0.0]
  We show how the numerical range of a matrix can be used to bound the optimal value of certain optimization problems over real tensor product vectors. Our bound is stronger than the trivial bounds based on eigenvalues, and can be computed significantly faster than bounds provided by semidefinite programming relaxations.
  arXiv  Detail & Related papers  (2022-12-24T20:03:06Z)
• Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
  We propose quantum algorithms for matrix operations using the "Sender-Receiver" model. These quantum protocols can be used as subroutines in other quantum schemes.
  arXiv  Detail & Related papers  (2022-02-10T08:12:20Z)
• Identifiability in Exact Two-Layer Sparse Matrix Factorization [0.0]
  Sparse matrix factorization is the problem of approximating a matrix Z by a product of L sparse factors X(L) X(L--1). This paper focuses on identifiability issues that appear in this problem, in view of better understanding under which sparsity constraints the problem is well-posed.
  arXiv  Detail & Related papers  (2021-10-04T07:56:37Z)
• Sparse Factorization of Large Square Matrices [10.94053598642913]
  In this paper, we propose to approximate a large square matrix with a product of sparse full-rank matrices. In the approximation, our method needs only $N(log N)2$ non-zero numbers for an $Ntimes N$ full matrix. We show that our method gives a better approximation when the approximated matrix is sparse and high-rank.
  arXiv  Detail & Related papers  (2021-09-16T18:42:21Z)
• 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)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Adversarially-Trained Nonnegative Matrix Factorization [77.34726150561087]
  We consider an adversarially-trained version of the nonnegative matrix factorization. In our formulation, an attacker adds an arbitrary matrix of bounded norm to the given data matrix. We design efficient algorithms inspired by adversarial training to optimize for dictionary and coefficient matrices.
  arXiv  Detail & Related papers  (2021-04-10T13:13:17Z)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  Multi-view spectral clustering can effectively reveal the intrinsic cluster structure among data. This paper proposes a multi-view spectral clustering algorithm that learns a high-order optimal neighborhood Laplacian matrix. Our proposed algorithm generates the optimal Laplacian matrix by searching the neighborhood of the linear combination of both the first-order and high-order base.
  arXiv  Detail & Related papers  (2020-08-31T12:28:40Z)
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method [47.80060761046752]
  Robust low-rank matrix completion (RMC) has been studied extensively for computer vision, signal processing and machine learning applications. This problem aims to decompose a partially observed matrix into the superposition of a low-rank matrix and a sparse matrix, where the sparse matrix captures the grossly corrupted entries of the matrix. A widely used approach to tackle RMC is to consider a convex formulation, which minimizes the nuclear norm of the low-rank matrix (to promote low-rankness) and the l1 norm of the sparse matrix (to promote sparsity). In this paper, motivated by some recent works on low-
  arXiv  Detail & Related papers  (2020-08-18T04:46:22Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

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.